Rekonstruktion von Graphen aus der Gradverteilung

Wie schnell können wir bei einer gegebenen Gradverteilung ein Diagramm erstellen, das der gegebenen Gradverteilung folgt? Eine Link- oder Algorithmus-Skizze wäre gut. Der Algorithmus sollte ein "Nein" melden, wenn kein Diagramm erstellt werden kann, und ein beliebiges Beispiel, wenn mehrere Diagramme erstellt werden können.

Wenn Sie damit meinen, wie man einen so einfachen Graphen konstruiert (keine Selbstschleifen und keine parallelen Kanten), ist Havel-Hakimi-Theorem vielleicht das, wonach Sie suchen. Sie können es selbst googeln und die Wikipedia-Seite Grad (Graphentheorie) ist ebenfalls hilfreich.

Wenn der Grad Verteilung als eine Liste von Grad gegeben ist, dann können Sie folgendes tun, da Knoten mit Grad d 1 , . . . , d n :$n$$d_1, ... ,d_n$

Erstellen Sie einen vollständigen Graphen auf n -Vertizes. Für jeden Scheitelpunkt v i in K n , spaltete es in d i Kopien. Teilen bedeutet hier, dass eine Anzahl von Kopien mit Kanten zu jedem Scheitelpunkt erstellt wird, zu dem v i eine Kante hat, aber keine Kanten zu anderen Kopien von v i . Wenn d i = $K_n$$n$$v_i$$K_n$$d_i$$v_i$$v_i$$d_i = 0$ dann entfernen Sie einfach den Scheitel. Nennen Sie in der neuen Grafik diese Eckpunkte für 1 ≤ j ≤ d i .$v_{ij}$$1 \leq j \leq d_i$

Sobald Sie fertig sind, haben Sie einen sehr dichten Graphen für Ecken; nennen dieses Graphen H . Wählen Sie Ihren Lieblingsalgorithmus für maximale Übereinstimmung (da der Graph so dicht ist, sollten Sie wahrscheinlich einen der schnellen Algorithmen auf der Basis der Matrixmultiplikation verwenden) und führen Sie ihn auf H aus . Dies gibt ein passendes M zurück . Wenn die Übereinstimmung nicht perfekt ist (dh nicht alle Scheitelpunkte abdeckt), war Ihre Gradverteilung unmöglich. so kehre nicht zurück .$N = d_1 + ... + d_n$$H$$H$$M$

Wenn Sie eine perfekte Abstimmung haben , entfernen dann alle Kanten nicht in M aus H , und dann für jedes 1 ≤ i ≤ n fusionieren die d i vielen Eckpunkten v i 1 , . . . , v i d i in einen Eckpunkt u i . Beim Zusammenführen zweier Scheitelpunkte werden diese zu einem zusammengefasst, sodass der resultierende Scheitelpunkt Kanten zu jedem Scheitelpunkt aufweist, zu dem mindestens einer der ursprünglichen Scheitelpunkte eine Kante hatte. Nenne den resultierenden Graphen G ; es hat die gewünschte gradverteilung.$M$$M$$H$$1 \leq i \leq n$$d_i$$v_{i1}, ... , v_{id_i}$$u_i$$G$

Die resultierende Laufzeit ist mit $O(N^\omega)$$\omega$ die Konstante für die schnellste Matrix-Multiplikationsalgorithmus (der zum Zeitpunkt des Schreibens ist etwa ). In Bezug auf die Anzahl der Scheitelpunkte im resultierenden Graphen haben wir im schlimmsten Fall, wenn die Gradverteilung dicht ist, O ( n 2 & ohgr; ) .$2.373$$O(n^{2\omega})$