Gradfolge
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]
Die Gradfolge eines einfachen Graphen <math>G = (V, E)</math> mit den Knoten <math>v_1, v_2, \ldots, v_n \in V</math> und Knotengraden <math> d(v_1) \leq d(v_2) \leq \dots \leq d(v_n) </math> ist die Folge natürlicher Zahlen
- <math>d_1, d_2, \ldots, d_n</math>,
wobei <math>d_i = d(v_i)</math> für alle <math>i = 1, 2, \dots, n</math> jeweils den Grad des Knotens <math>v_i</math> angibt. Eine aufsteigende Folge natürlicher Zahlen heißt graphisch, wenn mindestens ein einfacher Graph existiert, der diese Gradfolge aufweist.
Beispiele[Bearbeiten]
Gradfolge[Bearbeiten]
Das Haus vom Nikolaus hat mit der Knotennummerierung im nebenstehenden Bild die Knotengrade <math> d(1)=d(2)=3 , d(3)=d(4)=4</math> und <math> d(5)=2 </math>. Eine Sortierung nach dem Grad ergibt dann die zugehörige Gradfolge <math>2,3,3,4,4</math>.
Graphische Folgen[Bearbeiten]
Die Folge <math> 0,1,2,2,3,3,3 </math> ist graphisch, da der eingangs gezeigte Graph genau diese Grade hat. Die Folge <math> 1,3,4</math> 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]
- Skriptfehler: Ein solches Modul „Vorlage:Literatur“ ist nicht vorhanden.