Direkt zum Inhalt

Lexikon der Mathematik: Berge-Tutte, Satz von

eine Erweiterung des bekannten Ein-Faktor-Satzes von Tutte, die Berge 1958 gefunden hat. Der Satz lautet:

Es sei G ein Multigraph der Ordnung n und M ein maximales Matching von G.

Dann gilt \begin{eqnarray}n-2|M|=\mathop{\max }\limits_{{\rm{A}}\subseteq E(G)}\{q(G-A)-|A|\},\end{eqnarray}wobei q(G − A) die Anzahl der Zusammenhangskomponenten ungerader Ordnung in GA ist.

Der Spezialfall, daß M ein perfektes Matching ist, also n = 2|M| gilt, liefert gerade den Ein-Faktor-Satz von Tutte.

Lesermeinung

Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.

  • Die Autoren
- Prof. Dr. Guido Walz

Partnervideos