Satz von Vizing

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 G ein Multigraph, d.h. ein Graph mit Mehrfachkanten aber ohne Schlingen, mit dem chromatischen Index  \chi^{\prime}(G) und dem maximalen Grad Δ(G). Weiterhin bezeichne h die maximale Anzahl von Kanten, die zwei Ecken verbinden. Dann gilt die folgende Ungleichung:

\Delta(G)\le\chi^{\prime}(G)\le\Delta(G)+h

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

\Delta(G)\le\chi^{\prime}(G)\le\Delta(G)+1

Literatur

Weblinks


Wikimedia Foundation.

Игры ⚽ Поможем сделать НИР

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

  • Färbung von Graphen — Darstellung einer kartographischen Färbung als Graph Eine Färbung eines ungerichteten Graphen ordnet jedem Knoten bzw. jeder Kante im Graphen eine Farbe zu. In der Graphentheorie beschäftigt man sich meist nur mit sogenannten „zulässigen“ oder… …   Deutsch Wikipedia

  • Wadym Wysyng — Wadym G. Wysyng (russisch Вадим Георгиевич Визинг, englische Transkription: Vadim G. Vizing; * 25. März 1937 in Kiew) ist ein ukrainischer Mathematiker, der vor allem für seine Beiträge auf dem Gebiet der Graphentheorie bekannt ist. Bis zu… …   Deutsch Wikipedia

  • Liste mathematischer Sätze — Inhaltsverzeichnis A B C D E F G H I J K L M N O P Q R S T U V W X Y Z A Satz von Abel Ruffini: eine allgemeine Polynomgleichung vom …   Deutsch Wikipedia

  • Bipartition (Graphentheorie) — Darstellung einer kartographischen Färbung als Graph Eine Färbung eines ungerichteten Graphen ordnet jedem Knoten bzw. jeder Kante im Graphen eine Farbe zu. In der Graphentheorie beschäftigt man sich meist nur mit sogenannten „zulässigen“ oder… …   Deutsch Wikipedia

  • Eindeutig k-färbbarer Graph — Darstellung einer kartographischen Färbung als Graph Eine Färbung eines ungerichteten Graphen ordnet jedem Knoten bzw. jeder Kante im Graphen eine Farbe zu. In der Graphentheorie beschäftigt man sich meist nur mit sogenannten „zulässigen“ oder… …   Deutsch Wikipedia

  • Färbungsproblem — Darstellung einer kartographischen Färbung als Graph Eine Färbung eines ungerichteten Graphen ordnet jedem Knoten bzw. jeder Kante im Graphen eine Farbe zu. In der Graphentheorie beschäftigt man sich meist nur mit sogenannten „zulässigen“ oder… …   Deutsch Wikipedia

  • Graphenfärbung — Darstellung einer kartographischen Färbung als Graph Eine Färbung eines ungerichteten Graphen ordnet jedem Knoten bzw. jeder Kante im Graphen eine Farbe zu. In der Graphentheorie beschäftigt man sich meist nur mit sogenannten „zulässigen“ oder… …   Deutsch Wikipedia

  • Graphfärbung — Darstellung einer kartographischen Färbung als Graph Eine Färbung eines ungerichteten Graphen ordnet jedem Knoten bzw. jeder Kante im Graphen eine Farbe zu. In der Graphentheorie beschäftigt man sich meist nur mit sogenannten „zulässigen“ oder… …   Deutsch Wikipedia

  • Gültige Färbung — Darstellung einer kartographischen Färbung als Graph Eine Färbung eines ungerichteten Graphen ordnet jedem Knoten bzw. jeder Kante im Graphen eine Farbe zu. In der Graphentheorie beschäftigt man sich meist nur mit sogenannten „zulässigen“ oder… …   Deutsch Wikipedia

  • Gültige Kantenfärbung — Darstellung einer kartographischen Färbung als Graph Eine Färbung eines ungerichteten Graphen ordnet jedem Knoten bzw. jeder Kante im Graphen eine Farbe zu. In der Graphentheorie beschäftigt man sich meist nur mit sogenannten „zulässigen“ oder… …   Deutsch Wikipedia

Share the article and excerpts

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