Satz von Vizing

aus Wikipedia, der freien Enzyklopädie
Dies ist die aktuelle Version dieser Seite, zuletzt bearbeitet am 4. März 2019 um 06:49 Uhr durch imported>Kmhkmh(355724).
(Unterschied) ← Nächstältere Version | Aktuelle Version (Unterschied) | Nächstjüngere Version → (Unterschied)

Der Satz von Vizing ist ein 1964 von Vadim G. Vizing publizierter mathematischer Lehrsatz aus der Graphentheorie. Er liefert sowohl eine Untergrenze als auch eine Obergrenze für den chromatischen Index eines Graphen.

Sei ein Multigraph, d. h. ein Graph mit Mehrfachkanten aber ohne Schlingen, mit dem chromatischen Index und dem Maximalgrad . Weiterhin bezeichne die maximale Anzahl von Kanten, die zwei Ecken verbinden. Dann gilt die folgende Ungleichung:

Diese Ungleichung ist optimal, die Gleichung wird von Shannon-Multigraphen realisiert.

Im Falle eines einfachen Graphen, d. h. eines Graphen ohne Mehrfachkanten, vereinfacht sich die obige Ungleichung dann zu:

Literatur

  • Lutz Volkmann: Fundamente der Graphentheorie, Springer (Wien) 1996, ISBN 3-211-82774-9, S. 286, 288, Satz 13.2 und Satz 13.3.
  • Reinhard Diestel: Graphentheorie. Springer 2006, ISBN 3-540-21391-0, S. 103, Theorem 5.3.2 (Online-Version der englischen Ausgabe).

Weblinks