Graphentheorie, Satz von Tutte

15/01/2009 - 19:09 von Christof Kluß | Report spam
Hallo,

der Satz von Tutte:
Ein endlicher Graph besitzt genau dann einen 1-Faktor, wenn o(G-S) <=
|S| für alle S Teilmenge der Knotenmenge.

Wie ist das für Graphen mit ungerader Knotenanzahl zu verstehen, die
haben doch keinen 1-Faktor. Aber für den vollstàndigen Graphen mit 3
Knoten gilt o(G-S) <= |S|.

Sieht jemand meinen Denkfehler?

Gruß,
Christof
 

Lesen sie die antworten

#1 Stefan Kirchner
15/01/2009 - 20:26 | Warnen spam
On Thu, 15 Jan 2009, Christof Kluß wrote:

Hallo,

der Satz von Tutte:
Ein endlicher Graph besitzt genau dann einen 1-Faktor, wenn o(G-S) <=
|S| für alle S Teilmenge der Knotenmenge.

Wie ist das für Graphen mit ungerader Knotenanzahl zu verstehen, die haben
doch keinen 1-Faktor. Aber für den vollstàndigen Graphen mit 3 Knoten gilt
o(G-S) <= |S|.

Sieht jemand meinen Denkfehler?



Nimm S = {}. Dann gilt o(G-S) = o(G) = 1 > 0 = |S|, hat also alles seine
Richtigkeit.


Gruß Stefan

Ähnliche fragen