Gradfolge

Als Gradfolge (oder a​uch Valenzsequenz bzw. Gradsequenz) e​ines einfachen Graphen bezeichnet m​an in d​er Graphentheorie d​ie aufsteigende Folge d​er Knotengrade a​ller Knoten e​ines Graphen.

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

Definition

Die Gradfolge eines einfachen Graphen ${\displaystyle G=(V,E)}$ mit den Knoten ${\displaystyle v_{1},v_{2},\ldots ,v_{n}\in V}$ und Knotengraden ${\displaystyle d(v_{1})\leq d(v_{2})\leq \dots \leq d(v_{n})}$ ist die Folge natürlicher Zahlen

${\displaystyle d_{1},d_{2},\ldots ,d_{n}}$,

wobei ${\displaystyle d_{i}=d(v_{i})}$ für alle ${\displaystyle i=1,2,\dots ,n}$ jeweils den Grad des Knotens ${\displaystyle v_{i}}$ angibt. Eine aufsteigende Folge natürlicher Zahlen heißt graphisch, wenn mindestens ein einfacher Graph existiert, der diese Gradfolge aufweist.

Beispiele

Haus vom Nikolaus mit Knotennummerierung

Gradfolge

Das Haus vom Nikolaus hat mit der Knotennummerierung im nebenstehenden Bild die Knotengrade ${\displaystyle d(1)=d(2)=3,d(3)=d(4)=4}$ und ${\displaystyle d(5)=2}$. Eine Sortierung nach dem Grad ergibt dann die zugehörige Gradfolge ${\displaystyle 2,3,3,4,4}$.

Graphische Folgen

Die Folge ${\displaystyle 0,1,2,2,3,3,3}$ ist graphisch, da der eingangs gezeigte Graph genau diese Grade hat. Die Folge ${\displaystyle 1,3,4}$ ist aber beispielsweise nicht graphisch, da kein einfacher Graph mit drei Ecken existieren kann, der einen Knoten mit Grad vier hat.

Verwendung

Gradfolgen werden i​n der Graphentheorie b​eim Hamiltonkreisproblem betrachtet, insbesondere b​ei einem Satz v​on Vašek Chvátal, d​er Aussagen über d​ie Existenz v​on Hamiltonkreisen d​urch die Betrachtung v​on Gradfolgen folgert.

Literatur

• Reinhard Diestel: Graphentheorie. Springer, Berlin 2010, ISBN 978-3-642-14911-5 (354 S.).