Gradfolge

aus Wikipedia, der freien Enzyklopädie
(Weitergeleitet von Gradsequenz)
Wechseln zu: Navigation, Suche
Graph mit eingezeichneten Knotengraden und der Gradfolge 0,1,2,2,3,3,3

Als Gradfolge (oder auch Valenzsequenz bzw. Gradsequenz) eines einfachen Graphen bezeichnet man in der Graphentheorie die aufsteigende Folge der Knotengrade aller Knoten eines Graphen.

Definition[Bearbeiten | Quelltext bearbeiten]

Die Gradfolge eines einfachen Graphen mit den Knoten und Knotengraden ist die Folge natürlicher Zahlen

,

wobei für alle jeweils den Grad des Knotens angibt. Eine aufsteigende Folge natürlicher Zahlen heißt graphisch, wenn mindestens ein Graph existiert, der diese Gradfolge aufweist.

Beispiele[Bearbeiten | Quelltext bearbeiten]

Haus vom Nikolaus mit Knotennummerierung

Gradfolge[Bearbeiten | Quelltext bearbeiten]

Das Haus vom Nikolaus hat mit der Knotennummerierung im nebenstehenden Bild die Knotengrade und . Eine Sortierung nach dem Grad ergibt dann die zugehörige Gradfolge .

Graphische Folgen[Bearbeiten | Quelltext bearbeiten]

Die Folge ist graphisch, da der eingangs gezeigte Graph genau diese Grade hat. Die Folge ist aber beispielsweise nicht graphisch, da kein einfacher Graph mit drei Ecken existieren kann, der einen Knoten mit Grad vier hat.

Verwendung[Bearbeiten | Quelltext bearbeiten]

Gradfolgen werden in der Graphentheorie beim Hamiltonkreisproblem betrachtet, insbesondere bei einem Satz von Vašek Chvátal, der Aussagen über die Existenz von Hamiltonkreisen durch die Betrachtung von Gradfolgen folgert.

Literatur[Bearbeiten | Quelltext bearbeiten]