Satz von Tutte < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 11:51 Mo 07.02.2011 | | Autor: | Willey |
Moin moin!
Ich beiße mir jetzt seit ca. einer Woche die Zähne am sog. "Satz von Tutte" aus und ich verstehe einfach nicht, was genau er aussagt, bzw. ergibt meine Auslegung nicht den geringsten Sinn.
Laut unserem Prof besagt der Satz:
"G besitzt einen linearen Faktor (1-Faktor / perfektes Matching) genau dann, wenn für jede Teilmenge x1 der Knotenmenge V gilt, dass die Anzahl der Komponenten mit ungerader Knotenanzahl, von den Komponenten, in die G bei Wegnahme der Knoten von x1 zerfällt, nicht größer als die Anzahl der Elemente von x1 ist"
Verständlich ausgedrückt heißt das für mich
- Ich habe den Graphen G
- Daraus wähle ich eine Menge an Knoten x1 aus
- Ich entferne diese Knoten und die anliegenden Kanten
- Es bleiben diverse Komponenten übrig
- Ich prüfe, ob die Anzahl der Komponenten mit ungerader Knotenanzahl geringer ist, als die Menge meiner Knoten x1
- Ist dies der Fall, hat der Graph keinen 1-Faktor
Soweit so gut, aber es macht einfach keinen Sinn. Der K5 z.B. (vollständiger Graph mit 5 Knoten) hat keinen 1-Faktor, da die Anzahl der Knoten ungerade ist. Egal wie viele Knoten ich aber aus dem K5 entferne, er "zerfällt" immer nur in 1 einzige Komponente, was ja auch logisch ist, da bei einem vollständigen Graphen jeder mit jedem verbunden ist, und beim Entfernen eines Knoten immer noch alle restlichen Knoten miteinander verbunden sind. Also besitzt der K5 doch laut Tutte einen 1-Faktor?
Also wo liegt mein Denkfehler?
Was genau sind in diesem Falle Komponenten?
Wikipedia ist in diesem Falle auch nicht aufschlussreicher.
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 12:14 Mo 07.02.2011 | | Autor: | cycore |
Hallo Willey,
> "G besitzt einen linearen Faktor (1-Faktor / perfektes
> Matching) genau dann, wenn für jede Teilmenge x1 der
> Knotenmenge V gilt, dass die Anzahl der Komponenten mit
> ungerader Knotenanzahl, von den Komponenten, in die G bei
> Wegnahme der Knoten von x1 zerfällt, nicht größer als
> die Anzahl der Elemente von x1 ist"
Das stimmt soweit schonmal, auch wenn ich zugeben muss, dass es dazu verständlichere Versionen gibt...
> Verständlich ausgedrückt heißt das für mich
> - Ich habe den Graphen G
> - Daraus wähle ich eine Menge an Knoten x1 aus
> - Ich entferne diese Knoten und die anliegenden Kanten
> - Es bleiben diverse Komponenten übrig
> - Ich prüfe, ob die Anzahl der Komponenten mit ungerader
> Knotenanzahl geringer ist, als die Menge meiner Knoten x1
> - Ist dies der Fall, hat der Graph keinen 1-Faktor
Vorsicht: An sich stimmt die idee und vielleicht meinst du das ja auch so, aber das soll für jede Teilmenge x1 gelten!
> Soweit so gut, aber es macht einfach keinen Sinn. Der K5
> z.B. (vollständiger Graph mit 5 Knoten) hat keinen
> 1-Faktor, da die Anzahl der Knoten ungerade ist.
Richtig
> Egal wie
> viele Knoten ich aber aus dem K5 entferne, er "zerfällt"
> immer nur in 1 einzige Komponente, was ja auch logisch ist,
> da bei einem vollständigen Graphen jeder mit jedem
> verbunden ist, und beim Entfernen eines Knoten immer noch
> alle restlichen Knoten miteinander verbunden sind. Also
> besitzt der K5 doch laut Tutte einen 1-Faktor?
Was ist mit dem Fall [mm]x1 = \emptyset[/mm] der leeren menge ?
Dann ist ist [mm]|\emptyset|=0<1 =[/mm] Anzahl der Zusammenhangskomponenten von [mm] K_5 [/mm] ungerader Mächtigkeit.
Somit kann tutte nicht angewendet werden.
Gruß Cycore
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 13:51 Mo 07.02.2011 | | Autor: | Willey |
Ahhhhhh super da war also mein Denkfehler. Ja so leere Mengen lasse ich gern mal unter den Tisch fallen. *g*
Vielen Dank!
|
|
|
|
