Graphen-Gradsequenz-Prüfer
Erdős–Gallai Theorem · Havel-Hakimi Algorithm · Graph Realization
Gib eine Folge von ganzen Zahlen ein, um mit dem Erdős-Gallai-Theorem zu prüfen, ob es eine gültige grafische Gradsequenz ist. Konstruiert dann eine Realisierung via Havel-Hakimi.
Schnellbeispiele
Prüfungen & Eigenschaften
Erdős-Gallai-Bedingungstabelle
Für jedes k muss die Ungleichung ∑i=1k di ≤ k(k−1) + ∑i=k+1n min(di, k) erfüllt sein.
| k | Links: ∑ di | Rechts: k(k-1)+∑min | Erfüllt? |
|---|
Havel-Hakimi-Konstruktionsschritte
Absteigend sortieren, den Knoten mit dem höchsten Grad mit den nächsten d Knoten verbinden, entfernen, wiederholen.
| Schritt | Aktuelle Sequenz | Kanten hinzugefügt | Verbleibend |
|---|
Graphenrealisierung — Kantenliste
Graph-Visualisierung
Was ist eine Gradsequenz?
In der Graphentheorie ist eine Gradsequenz die Liste der Grade aller Knoten in einem Graphen, meist in absteigender Reihenfolge. Der Grad eines Knotens ist die Anzahl der mit ihm verbundenen Kanten.
Gradsequenzen dienen als kompakter Fingerabdruck für Graphen. Sie kodieren wichtige strukturelle Informationen über Konnektivität und mögliche Topologien.
Grafische Sequenzen: Was macht eine Sequenz gültig?
Eine Folge nicht-negativer ganzer Zahlen heißt grafisch, wenn sie als Gradsequenz eines einfachen Graphen realisiert werden kann (ohne Schleifen und Mehrfachkanten).
Nicht jede Sequenz qualifiziert sich. Zum Beispiel ist [3, 3, 2] nicht grafisch.
Das Erdős–Gallai-Theorem
Das Erdős-Gallai-Theorem (1960) bietet eine vollständige Charakterisierung grafischer Sequenzen. Eine nicht-aufsteigende Folge ist genau dann grafisch, wenn:
- Gerade Summe: Die Summe ist gerade (Handschlag-Lemma).
- Erdős-Gallai-Ungleichungen: Für jedes k = 1, 2, …, n:
∑i=1k di ≤ k(k−1) + ∑i=k+1n min(di, k)
Die rechte Seite zählt die maximal möglichen Kanten.
Der Havel-Hakimi-Algorithmus
Der Havel-Hakimi-Algorithmus bietet einen konstruktiven Ansatz: Er prüft nicht nur die grafische Eigenschaft, sondern baut auch den Graphen auf.
Der Algorithmus geht iterativ vor:
- Gradsequenz absteigend sortieren.
- Wenn das erste Element 0 ist, ist die Sequenz [0, 0, ..., 0] trivialerweise grafisch.
- Nimm das erste Element d₁. Verbinde Knoten 1 mit den nächsten d₁ Knoten.
- Reduziere die Grade dieser d₁ Knoten um 1. Entferne Knoten 1.
- Wenn ein Grad negativ wird, ist die Sequenz nicht grafisch.
- Wiederhole dies mit der reduzierten Sequenz.
Das Havel-Hakimi-Theorem garantiert die Korrektheit.
Spezielle Graphen-Gradsequenzen
| Graphentyp | Gradsequenz-Muster | Beispiel (n=5) |
|---|---|---|
| Vollständiger Graph Kₙ | Alle n−1 | [4,4,4,4,4] |
| Kreis Cₙ | Alle 2en | [2,2,2,2,2] |
| Pfad Pₙ | Zwei 1en, Rest 2en | [2,2,2,1,1] |
| Stern K₁,₄ | Eine (n-1), Rest 1en | [4,1,1,1,1] |
| Leerer Graph | Alle 0en | [0,0,0,0,0] |
| Regulärer Graph | Alle gleich k | [3,3,3,3,3,3] |
Anwendungen von Gradsequenzen
Gradsequenzen und Tests auf grafische Eigenschaften kommen in vielen realen Kontexten vor:
- Netzwerkdesign: Überprüfung von Netzwerktopologien anhand von Konnektivitätsanforderungen.
- Molekularchemie: Die Valenzsequenz von Atomen bestimmt mögliche Molekülstrukturen.
- Analyse sozialer Netzwerke: Gradsequenzen modellieren die Verteilung von Verbindungen in sozialen Netzwerken.
- Bioinformatik: Protein-Interaktionsnetzwerke werden durch Gradsequenzen analysiert.
- Kombinatorik und extremale Graphentheorie: Gradsequenzen untermauern Beweise für die Existenz von Graphen.
Das Handschlag-Lemma
Die Bedingung, dass die Summe der Grade gerade sein muss, ist eine direkte Folge des Handschlag-Lemmas: In jedem Graphen ist die Summe aller Knotengrade gleich der doppelten Kantenanzahl.