imported>Aka: https

2023-06-14T20:32:57Z

https

Neue Seite

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 [[Chromatischer Index|chromatischen Index]] eines Graphen.

Sei <math>G</math> ein [[Multigraph]], d. h. ein Graph mit Mehrfachkanten aber ohne Schlingen, mit dem chromatischen Index <math> \chi^{\prime}(G)</math> und dem [[Maximalgrad]] <math>\Delta(G)</math>. Weiterhin bezeichne <math>h</math> die maximale Anzahl von Kanten, die zwei Ecken verbinden. Dann gilt die folgende Ungleichung:

:<math>\Delta(G)\le\chi^{\prime}(G)\le\Delta(G)+h.</math>

Diese Ungleichung ist optimal, die Gleichung <math>\chi^{\prime}(G)=\Delta(G)+h</math> wird von [[Shannon-Multigraph]]en realisiert.

Im Falle eines [[Einfacher Graph|einfachen Graphen]], d. h. eines Graphen ohne Mehrfachkanten, vereinfacht sich die obige Ungleichung dann zu:

:<math>\Delta(G)\le\chi^{\prime}(G)\le\Delta(G)+1</math>

== 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 ([https://diestel-graph-theory.com/index.html Online-Version der englischen Ausgabe]).
* {{EoM| Autor = Lutz Volkmann| Titel = Vizing theorem| Url = https://www.encyclopediaofmath.org/index.php/Vizing_theorem| id = }}

== Weblinks ==
* {{PlanetMath
| id = VizingsTheorem
| title = Vizing's theorem
| author = Marijke van Gans
}}
* Lutz Volkmann: ''[https://www.math2.rwth-aachen.de/files/gt/buch/graphen_an_allen_ecken_und_kanten.pdf Graphen an allen Ecken und Kanten] (PDF; 3,51 MB)'', Vorlesungsskript 2006, S. 239, 241, Satz 13.2 und Satz 13.3

[[Kategorie:Satz (Graphentheorie)|Vizing, Satz von]]

Satz von Vizing - Versionsgeschichte

imported>Aka: https