Skip to content

Welche Bedingung muss an das Havel-Hakimi-Theorem gestellt werden, um nach zusammenhängenden Graphen zu suchen?

Lösung:

Vielleicht findet jemand eine bessere Antwort oder erklärt die Details, aber ich habe beschlossen, meinen zweiten Kommentar zu einer Antwort zu machen.

Nach kurzem googeln habe ich folgendes gefunden:

Aufgabe 8.2.8 auf S. 8 127 in Melnikov: Übungen zur Graphentheorie:

Beweisen Sie, dass eine echte grafische n-Folge ohne Nullstellen potentiell zusammenhängend ist, wenn und nur $sum_{i=1}^n d_i ge 2(n-1)$.

Seite 117:

Eine Folge $d$ heißt $d$-grafisch, wenn es einen Graphen gibt, dessen Gradfolge $d$ ist. Ein solcher Graph wird als Realisierung der Folge $d$ bezeichnet.

Eine nicht ansteigende $n$-Folge $d$ heißt richtig wenn seine Summe gerade ist und $d_1le n-1$

EIN potentiell grafische Sequenz ist eine Graphenfolge, die über einen zusammenhängenden Graphen realisiert wird.

Seite 286:

Hinweis: Die Suffizienz kann durch Induktion über $n$ bewiesen werden. Der Induktionsschritt kann auf dem Havel-Hakimi-Theorem basieren.

Der Satz von Havel-Hakimi wird in diesem Buch wie folgt formuliert:

Für eine richtige $n$-Folge, $n>1$, ist die abgeleitete Sequenz $d^i$, $1le ile n$ ist wie folgt definiert. Das Element $d_i$ wird aus $d$ gelöscht und die ersten $d_i$ verbleibenden Elemente werden um 1 verringert.

Satz 8.1.3 (V. Havel, S. Hakimi) Eine echte $n$-Folge $dne(0^n)$ ist genau dann grafisch, wenn jede abgeleitete Folge $d^i$, $1le ile n$, grafisch ist.

Dieses Papier erwähnt Folgendes:

In [4] es wird behauptet, dass für eine graphische und potentiell verbundene Folge notwendig und ausreichend ist, dass $$sum_{i=1}^k d_i le k(k-1) + sum_{i=k+1}^ n min(k,d_i)$$ gilt und die Gradsumme beträgt mindestens $2(n-1)$, dh es gibt mindestens genug Grade, um einen aufspannenden Baum zu erzeugen. Es wird jedoch kein anderer Algorithmus angegeben, als einen Spannbaum zu erzeugen und dann den Havil-Hakimi-Algorithmus auf den Restgraphen anzuwenden.

[4] M. Mihail und NK Vishnoi. Über das Generieren von Graphen mit vorgeschriebenen Vertexgraden für die Modellierung komplexer Netzwerke. In ARACNE 2002, Seiten 1-12, 2002.

(Die obige Bedingung ist die Bedingung aus dem Satz von Erdős-Gallai.)

Eine Modifikation des Havel-Hakimi-Algorithmus, um einen zusammenhängenden Graphen zu erhalten, wird in der Arbeit Fabien Viger und Matthieu Latapy beschrieben: Effiziente und einfache Erzeugung von zufälligen einfachen zusammenhängenden Graphen mit vorgeschriebener Gradfolge. Diese Arbeit erwähnt jedoch keine Bedingungen für die Existenz eines zusammenhängenden Graphen.

BEARBEITEN

Endlich habe ich ein Buch gefunden, das auch einen vollständigen Beweis liefert. Der Beweis ist ein anderer als der im Hinweis in Melnikovs Buch vorgeschlagene. (Ich habe einige Zeit über diesen Hinweis nachgedacht und konnte die Lösung nicht vervollständigen. Ich bin mit Graphentheorie nicht besonders erfahren, aber ich vermute, dass der Autor des Buches dort einen Fehler macht. Oder - wahrscheinlicher - ich habe ihn falsch verstanden Hinweis.) Die Grundidee des Beweises in diesem Buch besteht darin, zunächst einen Graphen aus der Gradfolge zu konstruieren und wenn er nicht mehrfach mit Wechselkanten verbunden ist, bis er zusammenhängend wird.

Claude Berge: Graphen und Hypergraphen, Satz 9, p. 117-118:

Sei $d_1ge d_2 ge ldots ge d_n$ eine Folge von ganzen Zahlen, $nge 2$. Eine notwendige und hinreichende Bedingung für die Existenz eines einfachen zusammenhängenden Graphen $G$ mit Grad $d_G(x_i)=d_i$ ist, dass $$begin{gather*} d_n ge 1\ sum_{i=1}^n d_i ge 2(n-1)\ sum_{i=1}^n d_itext{ ist gerade }\ sum_{i=1}^k d_i le sum_{i=1}^k overline d_i end{gather*}$$

Zu den Bedingungen aus dem Satz, der Gradfolgen für einfache Graphen charakterisiert, werden hier nur die Bedingungen $d_nge 1$ und $sum_{i=1}^n d_i ge 2(n-1)$ addiert. Es ist nur eine andere Formulierung des Satzes von Erdős-Gallai.

Die Bedeutung von $overline d_i$ (die der Autor nennt korrigiertes Konjugat der Folge $d_i$) wird auf Seite 111 erklärt.

Ich habe erst vor ein paar Stunden von grafischen Sequenzen erfahren und (unabhängig) die Havel-Hakimi-Lösung durch das Spiel hier entdeckt: http://jacquerie.github.io/hh/. Ich empfehle wirklich, mindestens ein paar "Runden" zu spielen, um zu sehen, wie gut Sie verstehen (oder lernen), wie Havel-Hakimi funktioniert.

Mein Unterricht in Graphentheorie ist ein paar Jahrzehnte her, daher habe ich nur einen intuitiven und keinen rigorosen Beweis, sondern biete die folgende Beobachtung (Lemma):

Zwei grafische Sequenzen können zu einer neuen grafischen Sequenz verkettet werden.

Logische Folge:

Wenn eine grafische Sequenz in zwei (oder mehr) grafische Sequenzen unterteilt werden kann, existiert eine nicht verbundene Graphlösung.

Die einfachste nicht-leere grafische Sequenz ist 1,1. Sie können dies an jede grafische Sequenz anhängen, um eine neue grafische Sequenz zu erhalten, die einen nicht zusammenhängenden Graphen als Lösung hat. Dies zeigt jedoch nicht, dass es keine zusammenhängende Lösung gibt.

Betrachten Sie 2,2,2,1,1. Dies kann in 2,2,2 und 1,1 unterteilt werden, und die Verwendung der "traditionellen" Implementierung des Havel-Hakimi-Algorithmus ergibt diesen Graphen (wenn Sie jedes Mal ein Subtrahieren als Zeichnen einer Linie zu einem Knoten betrachten).

Wenn die Zahlen jedoch so neu angeordnet sind:

1 2 2 2 1
- 1 2 2 1
- - 1 2 1
- - - 1 1
- - - - 0

dann erhalten wir einen Pfad von fünf Knoten (ein Graph wie: ooooo ).

Ich habe die strenge Ordnung durchbrochen, wie sie im Havel-Hakimi-Theorem angegeben ist. Hier funktioniert es, aber die meisten willkürlichen Neuordnungen werden nicht (spielen Sie das Spiel und sehen Sie).

Für Ihr erstes Beispiel (3,3,1,1,1,1,1,1) gibt es zwei Partitionierungen: 3,3,1,1,1,1|1,1 und 3,1,1,1| 3,1,1,1.

Teilweise konstruierter Graph mit zwei möglichen Lösungen

Hier sehen Sie einen teilweise konstruierten Graphen mit zwei möglichen Lösungen, wobei 2,1,1 zu einem separaten Graphen werden oder mit dem Hauptgraphen verbunden werden können. (Nicht das einfachste Beispiel, sondern eines, das jacquerie.github.io/hh/ gerade generiert hat.)

Click to rate this post!
[Total: 0 Average: 0]



Anderer Beitrag

Blazor mit Database First

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht.