www.wikidata.de-de.nina.az

Satz von Vizing Der ist ein 1964 von Vadim G Vizing publizierter mathematischer Lehrsatz aus der Graphentheorie Er liefe

Satz von Vizing

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 Bearbeiten

Weblinks Bearbeiten

wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele
Veröffentlichungsdatum:
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 fur den chromatischen Index eines Graphen Sei G displaystyle G ein Multigraph d h ein Graph mit Mehrfachkanten aber ohne Schlingen mit dem chromatischen Index x G displaystyle chi prime G und dem Maximalgrad D G displaystyle Delta G Weiterhin bezeichne h displaystyle h die maximale Anzahl von Kanten die zwei Ecken verbinden Dann gilt die folgende Ungleichung D G x G D G h displaystyle Delta G leq chi prime G leq Delta G h Diese Ungleichung ist optimal die Gleichung x G D G h displaystyle chi prime G Delta G h wird von Shannon Multigraphen realisiert Im Falle eines einfachen Graphen d h eines Graphen ohne Mehrfachkanten vereinfacht sich die obige Ungleichung dann zu D G x G D G 1 displaystyle Delta G leq chi prime G leq Delta G 1 Literatur BearbeitenLutz 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 Lutz Volkmann Vizing theorem In Michiel Hazewinkel Hrsg Encyclopedia of Mathematics Springer Verlag und EMS Press Berlin 2002 ISBN 1 55608 010 7 englisch encyclopediaofmath org Weblinks BearbeitenMarijke van Gans Vizing s theorem In PlanetMath englisch Lutz Volkmann Graphen an allen Ecken und Kanten PDF 3 51 MB Vorlesungsskript 2006 S 239 241 Satz 13 2 und Satz 13 3 Abgerufen von https de wikipedia org w index php title Satz von Vizing amp oldid 234614926