www.vorkurse.de
Ein Projekt von vorhilfe.de
Die Online-Kurse der Vorhilfe

E-Learning leicht gemacht.
Hallo Gast!einloggen | registrieren ]
Startseite · Mitglieder · Teams · Forum · Wissen · Kurse · Impressum
Forenbaum
^ Forenbaum
Status Mathe-Vorkurse
  Status Organisatorisches
  Status Schule
    Status Wiederholung Algebra
    Status Einführung Analysis
    Status Einführung Analytisc
    Status VK 21: Mathematik 6.
    Status VK 37: Kurvendiskussionen
    Status VK Abivorbereitungen
  Status Universität
    Status Lerngruppe LinAlg
    Status VK 13 Analysis I FH
    Status Algebra 2006
    Status VK 22: Algebra 2007
    Status GruMiHH 06
    Status VK 58: Algebra 1
    Status VK 59: Lineare Algebra
    Status VK 60: Analysis
    Status Wahrscheinlichkeitst

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
Forum "Graphentheorie" - Beweis Satz von Menger
Beweis Satz von Menger < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Graphentheorie"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Beweis Satz von Menger: Frage (überfällig)
Status: (Frage) überfällig Status 
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

        
Bezug
Beweis Satz von Menger: Fälligkeit abgelaufen
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 14:20 Fr 09.03.2012
Autor: matux

$MATUXTEXT(ueberfaellige_frage)
Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Graphentheorie"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.vorkurse.de
[ Startseite | Mitglieder | Teams | Forum | Wissen | Kurse | Impressum ]