Satz von König (Graphentheorie)

Satz von König (Graphentheorie)

Der Satz von König ist ein mathematischer Satz aus der Graphentheorie, der für bipartite Graphen einen Zusammenhang zwischen einer größten Paarung und einer minimalen Knotenüberdeckung aufzeigt. Er lautet:[1]

In einem bipartiten Graphen ist die Größe einer größten Paarung gleich der Größe einer minimalen Knotenüberdeckung.

Der Satz ist nach dem ungarischen Mathematiker Dénes Kőnig benannt.

Inhaltsverzeichnis

Beispiel

Ein Beispiel eines bipartiten Graphen, mit größter Paarung (blau) und minimaler Knotenüberdeckung (rot):

Ein Beispiel eines bipartiten Graphen, mit größter Paarung (blau) und minimaler Knotenüberdeckung (rot)

Algorithmus

Dieser Algorithmus beschreibt wie man aus einer größten Paarung die minimale Knotenüberdeckung erhält. Die beiden Knotenmengen des bipartiten Graphen werden in Folge mit O (oben) und U (unten) bezeichnet.

  1. Größte Paarung berechnen.
  2. Alle nicht in der Paarung enthaltenen Knoten aus O werden in T eingefügt.
  3. Auf nicht in der Paarung enthaltenen Kanten gehen wir von diesen Knoten nach U. Alle besuchten Knoten werden in T eingefügt.
  4. Von den so erreichten Knoten in U gehen wir auf in der Paarung enthaltenen Knoten wieder nach O. Alle besuchten Knoten werden in T eingefügt.
  5. Die minimale Knotenüberdeckung ergibt sich aus (O \setminus T) \cup (U \cap T)

Einzelnachweise

  1. Klaus Wagner: Graphentheorie. Bibliographisches Institut Hochschultaschenbücher, Mannheim 1970, ISBN 3-411-00248-4, Satz 9.9

Weblinks


Wikimedia Foundation.

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Satz von König — Es gibt in Mathematik und Physik mehrere „Sätze von König“, die nach unterschiedlichen Wissenschaftlern benannt wurden, nämlich: nach Gyula Kőnig (1849–1913), einem ungarischen Mathematiker: in der Mengenlehre den Satz von König, nach Dénes Kőnig …   Deutsch Wikipedia

  • Satz von Hall — Eine Paarung (Matching) ist in der Graphentheorie eine Teilmenge der Kanten eines Graphen, in der keine zwei Kanten einen gemeinsamen Knoten besitzen. Paarungen haben innerhalb der Graphentheorie einen weiten Anwendungsbereich. Inhaltsverzeichnis …   Deutsch Wikipedia

  • Satz von Dilworth — Der Satz von Dilworth (nach Robert Palmer Dilworth) ist ein mathematischer Lehrsatz, welcher sowohl der Ordnungstheorie als auch der Diskreten Mathematik zuzuordnen ist. Er stellt einen Zusammenhang zwischen Ketten und Antiketten in einer… …   Deutsch Wikipedia

  • Lemma von König — Das Lemma von König oder Königslemma ist ein Theorem der Graphentheorie von Dénes Kőnig (1936). Die Berechenbarkeit des Lemmas wurde gründlich in der Mathematischen Logik erforscht. Dénes Kőnig wird korrekterweise mit Doppelakut geschrieben. Das… …   Deutsch Wikipedia

  • König (Begriffsklärung) — König bezeichnet einen Monarchen, siehe König, auch König (Spanien) einen Familiennamen, siehe König (Familienname) eine Schachfigur, siehe König (Schach) eine Spielkarte, siehe König (Spielkarte) ein Kartenspiel, siehe König (Kartenspiel) den… …   Deutsch Wikipedia

  • Kőnig — Dénes Kőnig (* 21. September 1884 in Budapest; † 19. Oktober 1944 ebenda) war ein ungarischer Mathematiker, der im Bereich der Graphentheorie arbeitete. Er war Sohn des Mathematikers Gyula Kőnig. Inhaltsverzeichnis 1 Leben 2 Dénes Kőnig Preis …   Deutsch Wikipedia

  • Graphentheorie — Ungerichteter Graph mit sechs Knoten. Die Graphentheorie ist ein Teilgebiet der Mathematik, das die Eigenschaften von Graphen und ihre Beziehungen zueinander untersucht. Dadurch, dass einerseits viele algorithmische Probleme auf Graphen… …   Deutsch Wikipedia

  • Abstand (Graphentheorie) — Dieses Stichwortverzeichnis enthält kurze Definitionen und Erklärungen zu den wichtigsten graphentheoretischen Begriffen. A Abstand Siehe: Distanz. Achromatische Zahl Die achromatische Zahl ψ(G) eines Graphen G ist die größte Zahl k, für die G… …   Deutsch Wikipedia

  • Adjazenz (Graphentheorie) — Dieses Stichwortverzeichnis enthält kurze Definitionen und Erklärungen zu den wichtigsten graphentheoretischen Begriffen. A Abstand Siehe: Distanz. Achromatische Zahl Die achromatische Zahl ψ(G) eines Graphen G ist die größte Zahl k, für die G… …   Deutsch Wikipedia

  • Benachbart (Graphentheorie) — Dieses Stichwortverzeichnis enthält kurze Definitionen und Erklärungen zu den wichtigsten graphentheoretischen Begriffen. A Abstand Siehe: Distanz. Achromatische Zahl Die achromatische Zahl ψ(G) eines Graphen G ist die größte Zahl k, für die G… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”