Beweis Satz von Menger < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 13:42 Do 01.03.2012 | | Autor: | oby |
| Aufgabe | Satz von Menger:
Sei [mm] G=(V,E)[/mm] ein Graph und [mm]A,B\subseteq\ V[/mm]. Die kleineste Anzahl einer
[mm]A,B[/mm] trennenden Eckenmenge ist gleich der größten Anzahl einer Menge
disjunkter [mm]A,B[/mm] Wege.
Beweis: (aus dem Buch von Reinhard Diestel: Graphentheorie)
Wir verwenden Induktion nach Kanten. Hat [mm]G[/mm] keine Kante, so ist
[mm]|A\cap B|=k[/mm] und wir haben [mm]k[/mm] triviale [mm]A,B[/mm] Wege. [mm] (\*)
[/mm]
Hat [mm]G[/mm] eine Kante [mm]e=(xy)[/mm]
aber keine [mm]k[/mm] disjunkten [mm]A,B[/mm] Wege, so enthält auch [mm]G|_e[/mm] keine solchen Wege
(wobei wir [mm]v_e[/mm] als Ecke in [mm]A[/mm] bzw [mm]B[/mm] auffassen, wenn [mm]x[/mm] oder [mm]y[/mm] in [mm]A[/mm]
bzw [mm]B[/mm] liegt). [mm] (\*\*)
[/mm]
Nach Induktionsannahme (Es gibt [mm]k[/mm] disjunkte [mm]A,B[/mm] Wege.) enthält
[mm]G|_e[/mm] dann eine [mm]A,B[/mm] Trenner [mm]Y[/mm] von weniger als [mm]k[/mm] Ecken; [mm] (\*\*\*)
[/mm]
unter diesen
ist [mm]v|_e[/mm], da sonst [mm]Y\subseteq V[/mm] ein [mm]A,B[/mm] Trenner in [mm]G[/mm] wäre. Dann
ist [mm]X:=(Y\setminus{v_e })\cup \{x,y\}[/mm] ein [mm]A,B[/mm] Trenner in [mm]G[/mm] aus genau [mm]k[/mm] Ecken. [mm] (\*\*\*\*)
[/mm]
Wir betrachten nun den Graphen [mm]G-e[/mm]. Wegen [mm]x,y\in\ X[/mm] trennt jeder
[mm]A,X[/mm] Trenner in [mm]G-e[/mm] auch [mm]A[/mm] und [mm]B[/mm] in [mm]G[/mm] und enthält somit mindestens
[mm]k[/mm] Ecken. [mm] (\*\*\*\*\*) [/mm]
Nach Induktionsannahme enthält [mm]G-e[/mm] daher [mm]k[/mm] disjunkte [mm]A,X[/mm] Wege. Analog
enthält [mm]G-e[/mm] auch [mm]k[/mm] disjunkte [mm]X,B[/mm] Wege, und da [mm]X[/mm] ein [mm]A,B[/mm] Trenner ist,
treffen diese die [mm]A,X[/mm] Wege nur in [mm]X[/mm]. Zusammen bilden die beiden
Wegesysteme die gesuchten [mm]A,B[/mm] Wege in [mm]G[/mm]. |
Hallo Matheraum,
Ich sitze nun schon über 3 Stunden an dem Beweis und kapier ihn einfach nicht. Ich hoffe mir kann hier jemand weiterhelfen.
Soweit ich weiß ist eigentlich folgendes zu zeigen:
Braucht man $k$ Knoten um $A$ und $B$ zu trennen, dann gibts $k$ disjunkte $A,B$-Wege.
Ich versuch mal, alle meine Unklarheiten aufzulisten:
[mm] (\*) [/mm] OK, das ist der Induktionsanfang, den hab ich verstanden.
[mm] (\*\*) [/mm] Hm, warum? Weil die Anzahl der Kanten verringert wird und sich somit eher weniger disjunkte $A-B$-Wege ergeben?
[mm] (\*\*\*) [/mm] Warum kann ich hier überhaupt Induktion anwenden? Klar, die Anzahl der Kanten ist kleiner, aber was garantiert mir, dass man auch in [mm] $G_e$ [/mm] die Mengen $A$ und $B$ mit genauso $k$ Kanten trennen kann? Vielleicht würden doch auch weniger als $k$ Kanten reichen??
[mm] (\*\*\*\*) [/mm] Hier streike ich völlig. Ein Satz drüber steht, dass $Y$ weniger als $k$ Ecken besitzt. $X$ soll jetzt aber genau $k$ Ecken haben?? Das würde doch bedeuten, dass $Y$ genau $k-1$ Ecken besitzt, es könnten doch aber auch z.B. $k-2$ Ecken in $Y$ enthalten sein??
[mm] (\*\*\*\*\*) [/mm] Woher weiß ich jetzt überhaupt etwas über einen $A$-$X$-Trenner? Die Rede ist doch eigentlich von einem $A$-$B$-Trenner? Zumal ich dann vom $AX$-Trenner wieder Eigenschaften auf den $AB$-Trenner schließe??? Da versteh ich gar nix.
Der Rest scheint dann noch die erhaltenen Aussagen ''zusammen zu wurschteln'' und schwupps ist die Aussage da?
Wäre für jeden Tipp (wie immer) dankbar. Ich hänge hier total fest! Vielleicht kann mir auch jemand schon bei einem der fünf Probleme helfen! Das wäre super.
MfG Oby
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 14:20 Fr 09.03.2012 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
