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

Graph mit eingezeichneten Knotengraden und der Gradfolge 0,1,2,2,3,3,3

Definition

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 einfacher Graph existiert, der diese Gradfolge aufweist.

Beispiele

Bearbeiten
 
Haus vom Nikolaus mit Knotennummerierung

Gradfolge

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

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

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