Satz von Tutte < Sonstiges < Hochschule < Mathe < Vorhilfe
|
Hallo,
ich verstehe eine Sache beim Satz von Tutte nicht so richtig und bräuchte da mal Hilfe.
Der Satz von Tutte besagt, dass in einem Graphen $G$ genau dann ein perfektes Matching existiert, wenn jede Knotenteilmenge $X$ von $G$ in der Mächtigkeit größer-gleich als die Anzahl der Zusammenhangskomponenten mit ungerader Knotenanzahl von [mm] $G\backslash [/mm] X$ ist.
Soweit so gut. Der Beweis dazu leuchtet mir auch irgendwie ein. Nur hab ich leider ein Gegenbeispiel gefunden:
Nimmt man nämlich einen Graphen $G$ mit ungerader Knotenzahl, so kann für $G$ ja kein perfektes Matching existieren, weil immer mindestens ein ungematchter Knoten übrig bleibt. Dies leuchtet auch ein wenn man z.B. den vollständigen Graphen mit 3 Knoten [mm] $K_3$ [/mm] (Dreieck) betrachtet. Der besitzt sicher kein perfektes Matching, da 2 Kanten miteinander inzidieren und eine Kante nicht alle Knoten abdeckt. Nun müsste also nach dem Satz von Tutte eine Knotenteilmenge $X$ von [mm] $K_3$ [/mm] existieren, so dass die Mächtigkeit von $X$ kleiner ist als die Anzahl der Zusammenhangskomponenten von $G [mm] \backslash [/mm] X$ mit ungerader Knotenanzahl. Sowas gibt es aber meiner Meinung nach nicht!
Hab ich da jetzt einen Denkfehler oder fehlt bei dem Satz eine Voraussetzung?
Ich hoffe ich habe mich verständlich ausgedrückt. Sonst bitte nochmal nachfragen.
Vielen Dank für eure Antworten!
P.S Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 08:35 Mi 10.03.2010 | | Autor: | felixf |
Moin!
> ich verstehe eine Sache beim Satz von Tutte nicht so
> richtig und bräuchte da mal Hilfe.
>
> Der Satz von Tutte besagt, dass in einem Graphen [mm]G[/mm] genau
> dann ein perfektes Matching existiert, wenn jede
> Knotenteilmenge [mm]X[/mm] von [mm]G[/mm] in der Mächtigkeit größer-gleich
> als die Anzahl der Zusammenhangskomponenten mit ungerader
> Knotenanzahl von [mm]G\backslash X[/mm] ist.
>
> Soweit so gut. Der Beweis dazu leuchtet mir auch irgendwie
> ein. Nur hab ich leider ein Gegenbeispiel gefunden:
> Nimmt man nämlich einen Graphen [mm]G[/mm] mit ungerader
> Knotenzahl, so kann für [mm]G[/mm] ja kein perfektes Matching
> existieren, weil immer mindestens ein ungematchter Knoten
> übrig bleibt. Dies leuchtet auch ein wenn man z.B. den
> vollständigen Graphen mit 3 Knoten [mm]K_3[/mm] (Dreieck)
> betrachtet. Der besitzt sicher kein perfektes Matching, da
> 2 Kanten miteinander inzidieren und eine Kante nicht alle
> Knoten abdeckt. Nun müsste also nach dem Satz von Tutte
> eine Knotenteilmenge [mm]X[/mm] von [mm]K_3[/mm] existieren, so dass die
> Mächtigkeit von [mm]X[/mm] kleiner ist als die Anzahl der
> Zusammenhangskomponenten von [mm]G \backslash X[/mm] mit ungerader
> Knotenanzahl. Sowas gibt es aber meiner Meinung nach nicht!
Doch: nimm $X = [mm] \emptyset$. [/mm] Dann hat $G [mm] \setminus [/mm] X$ genau eine Zusammenhangskomponente mit 3 Knoten (naemlich $G$ selber).
LG Felix
|
|
|
| |
|
Hallo Felix,
oh mann, da hätte ich auch selbst drauf kommen können. Ich glaube das Problem ist, dass das Skript, das ich da habe so schlecht ist und so von Fehlern wimmelt, dass ich schon anfange jede Formulierung zu hinterfragen. Jedenfalls vielen Dank!!! Das hat mir echt weiter geholfen.
LG
|
|
|
|
