Beweis Line-Graph < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 09:09 Di 29.03.2011 | | Autor: | Loko |
| Aufgabe | H ist ein zusammenhängender Graph, L(H) ist regulär
[mm] \Rightarrow [/mm] H ist regulär oder semi-regulär bipartite |
Ich habe mich jetzt an dem Beweis versucht, bin mir aber bei manchen Schritten noch nicht sicher:
L(H) ist regulär [mm] \Rightarrow \forall uv\in [/mm] V(L(H)) d(uv) = r (Grad der Ecke).
Ist uv [mm] \in [/mm] E(H) (Kantenmenge), so hat uv mit r anderen Kanten eine Ecke gemeinsam. (Es treffen r andere Kanten an u oder v).
[mm] \Rightarrow [/mm] d(u) + d(v) = r+2 (Da auch die Kante uv jeweils auf u und v trifft)
[mm] \gdw [/mm] d(u) = r+2 - d(v).
Diese Gleichung gilt für jede bel. Kante (hier weiß ich nicht genau wieso ich das behaupten kann. Reicht es, dass L(H) regulär ist, oder muss auch hierher, dass H zusammenhängend ist?)
Da H zusammenhängend gibt es einen Kantenzug durch jede Ecke in H: [mm] v_{1},v_{2},v_{3}, [/mm] ..., [mm] v_{n}
[/mm]
mit [mm] d(v_{1}) [/mm] = 2+r - [mm] d(v_{2}), [/mm] und
[mm] d(v_{2}) [/mm] = 2+r - [mm] d(v_{1}).
[/mm]
Beh.: [mm] \forall [/mm] i gerade: [mm] d(v_{i}) [/mm] = [mm] d(v_{2}) [/mm] und
[mm] d(v_{i+}) [/mm] = [mm] d(v_{1}).
[/mm]
Dazu Vollständige Induktion über i: (Dabei bin ich mir auch nicht so sicher, dass die stimmt)
I.A.: [mm] d(v_{3}) [/mm] = 2+r - [mm] d(v_{2}) [/mm] = 2+r - 2-r + [mm] d(v_{1}) [/mm] = [mm] d(v_{1})
[/mm]
[mm] d(v_{4}) [/mm] = 2+r - [mm] d(v_{3}) [/mm] = 2+r - [mm] d(v_{1}) [/mm] = [mm] d(v_{2})
[/mm]
I.S: [mm] d(v_{i}) \to d(v_{i+1}):
[/mm]
i gerade: [mm] d(v_{i}) [/mm] = [mm] d(v_{2}) [/mm] (I.V) [mm] \Rightarrow
[/mm]
[mm] d(v_{i+1}) [/mm] = 2+r - [mm] d(v_{i}) [/mm] = 2+r - [mm] d(v_{2}) [/mm] = [mm] d(v_{1})
[/mm]
i ungerade: [mm] d(v_{i}) [/mm] = [mm] d(v_{1}) [/mm] (I.V) [mm] \Rightarrow
[/mm]
[mm] d(v_{i+1}) [/mm] = 2+r - [mm] d(v_{i}) [/mm] = 2+r - [mm] d(v_{1}) [/mm] = [mm] d(v_{2}).
[/mm]
Also [mm] \forall [/mm] Ecken im Kantenzug ist (mit i ungerade):
[mm] d(v_{i}) [/mm] = [mm] d(v_{1}) [/mm] und [mm] d(v_{i+1}) [/mm] = [mm] d(v_{2})
[/mm]
Damit ist H regulär falls [mm] d(v_{1}) [/mm] = [mm] d(v_{2}) [/mm] und semi-regulär bipartite sonst.
(Hier noch eine Frage, warum weiß ich, dass H bipartit ist. Kann nicht auch die Ecke ungeraden Grades mit der geraden Grads benachbart sein? Oder wodurch ist das ausgeschlossen?)
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 09:20 Do 31.03.2011 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 12:28 Mi 06.04.2011 | | Autor: | Loko |
Nur für alle die auf diesen Beweis stoßen, nach dem Vortrag meinte der Dozent der wäre richtig so. Es muss nur statt Kantenzug Kantenfolge heißen.
Lg Loko
|
|
|
|
