Zählen Sie alle nicht-isomorphen Graphen einer bestimmten Größe auf

30

Ich möchte alle ungerichteten Graphen der Größe auflisten $n$ , benötige aber nur eine Instanz jeder Isomorphismusklasse . Mit anderen Worten, ich möchte alle nicht-isomorphen (ungerichteten) Graphen auf Eckpunkten aufzählen . Wie kann ich das machen? $n$

Genauer gesagt, ich möchte einen Algorithmus, der eine Folge ungerichteter Graphen mit der folgenden Eigenschaft erzeugt: Für jeden ungerichteten Graphen an Eckpunkten existiert ein Index so dass isomorph zu . Ich möchte, dass der Algorithmus so effizient wie möglich ist. Mit anderen Worten, die Metrik, die mir wichtig ist, ist die Laufzeit, die zum Generieren und Durchlaufen dieser Liste von Diagrammen benötigt wird. Ein sekundäres Ziel ist, dass es schön wäre, wenn der Algorithmus nicht zu komplex zu implementieren wäre. $G_1,G_2,\dots,G_k$ $G$ $n$ $i$ $G$ $G_i$

Beachten Sie, dass ich mindestens einen Graphen aus jeder Isomorphismusklasse haben muss, aber es ist in Ordnung, wenn der Algorithmus mehr als eine Instanz erzeugt. Insbesondere ist es in Ordnung, wenn die Ausgabesequenz zwei isomorphe Graphen enthält, wenn dies das Auffinden eines solchen Algorithmus erleichtert oder effizientere Algorithmen ermöglicht, sofern alle möglichen Graphen abgedeckt sind.

Meine Anwendung lautet wie folgt: Ich habe ein Programm, das ich auf allen Diagrammen der Größe testen möchte . Ich weiß, dass wenn zwei Graphen isomorph sind, sich mein Programm für beide gleich verhält (entweder für beide richtig oder für beide falsch). Es reicht also aus, mindestens einen Vertreter aus jeder Isomorphismusklasse aufzulisten und dann die zu testen Programm auf diesen Eingängen. In meiner Anwendung ist ziemlich klein. $n$ $n$

Einige mögliche Algorithmen, die ich in Betracht gezogen habe:

Ich könnte alle möglichen Adjazenzmatrizen aufzählen, dh alle symmetrischen 0-or-1-Matrizen, die alle Nullen auf den Diagonalen haben. Dies erfordert jedoch die Aufzählung von Matrizen. Viele dieser Matrizen stellen isomorphe Graphen dar, so dass dies anscheinend eine Menge Aufwand bedeutet. $n\times n$ $2^{n(n-1)/2}$
Ich könnte alle möglichen Adjazenzmatrizen auflisten und für jede testen, ob sie zu einem der zuvor ausgegebenen Graphen isomorph ist. Wenn es zu keiner vorherigen Ausgabe isomorph ist, geben Sie es aus. Dies würde die Ausgabeliste erheblich verkürzen, erfordert jedoch immer noch mindestens Berechnungsschritte (auch wenn wir davon ausgehen, dass die Prüfung der Graphisomorphie superschnell ist) meine Metrik. $2^{n(n-1)/2}$
Es ist möglich, eine Teilmenge von Adjazenzmatrizen aufzulisten. Insbesondere wenn ein Graph auf Eckpunkten , kann ich ohne Verlust der Allgemeinheit davon ausgehen, dass die Eckpunkte so angeordnet sind, dass . Mit anderen Worten, jeder Graph ist isomorph zu einem, bei dem die Scheitelpunkte in der Reihenfolge ihres nicht abnehmenden Grades angeordnet sind. Es genügt also, nur die Adjazenzmatrizen aufzulisten, die diese Eigenschaft haben. Ich weiß nicht genau, wie viele solcher Adjazenzmatrizen es gibt, aber es sind viel weniger als , und sie können mit viel weniger als aufgezählt werden $G$ $n$ $V=\{v_1,\dots,v_n\}$ $\deg v_1 \le \deg v_2 \le \cdots \le \deg v_n$ $2^{n(n-1)/2}$ $2^{n(n-1)/2}$ Rechenschritte. Dies hinterlässt jedoch immer noch viel Redundanz: Viele Isomorphismusklassen werden immer noch viele Male behandelt, daher bezweifle ich, dass dies optimal ist.

Können wir es besser machen? Wenn ich es richtig verstehe, gibt es ungefährÄquivalenzklassen nicht-isomorpher Graphen. Können wir einen Algorithmus finden, dessen Laufzeit besser ist als die obigen Algorithmen? Wie nah können wir uns demUntergrenze? Mir geht es in erster Linie um die Traktierbarkeit für kleine (etwa oder ; klein genug, um einen solchen Algorithmus plausibel vollständig ausführen zu können), nicht so sehr um die Asymptotik für große . $2^{n(n-1)/2}/n!$ $\sim 2^{n(n-1)/2}/n!$ $n$ $n=5$ $n=8$ $n$

Siehe auch: Konstruktion von inequivalenten binären Matrizen (obwohl man leider keine gültige Antwort erhalten zu haben scheint).

1

Afaik, selbst die Anzahl der Graphen der Größe bis zum Isomorphismus ist unbekannt, daher halte ich es für unwahrscheinlich, dass es einen Algorithmus (ohne Brute-Force) gibt. Beachten Sie hinsichtlich Ihrer Algorithmen, dass wir keinen Polynom-Zeit-Algorithmus zur Überprüfung des Graph-Isomorphismus (afaik) kennen. Daher sollte jeder Algorithmus, der in soll, dies vermeiden müssen auf Isomorphie prüfen (oft / dumm). (Auch .)

n

$n$

O (| output |)

$O(|\text{output}|)$

| output | = Ω (n \cdot | classes |)

$|\text{output}| = \Omega(n \cdot |\text{classes}|)$

Raphael

@Raphael, (1) Ich weiß, dass wir die genaue Anzahl der Graphen der Größe

bis zum Isomorphismus nicht kennen , aber dieses Problem erfordert nicht unbedingt, dass ich das weiß (z. B. weil ich mit Wiederholungen einverstanden bin). Ich weiß nicht, warum das bedeuten würde, dass es unwahrscheinlich ist, dass es einen besseren Algorithmus gibt als den, den ich gegeben habe. (2) Ja, ich weiß, dass es keinen bekannten Polynom-Zeit-Algorithmus für die Isomorphie von Graphen gibt, aber wir werden hier über Werte von

wie

sprechen , daher werden existierende Algorithmen wahrscheinlich schnell sein - und trotzdem habe ich nur erwähnt der Kandidat Algorithmus, um es abzulehnen, so ist es trotzdem strittig.

n

$n$

n

$n$

n = 6

$n=6$

DW

Für

höchstens 6 glaube ich, dass es, nachdem Sie die Anzahl der Scheitelpunkte und die Anzahl der Kanten gewählt und die Scheitelpunktbeschriftungen, wie Sie vermuten, nicht abnehmend nach Grad geordnet haben, nur sehr wenige mögliche Isomorphismusklassen geben wird. An dieser Stelle könnte es möglich sein, die verbleibenden Fälle durch eine Brute-Force-Isomorphismusprüfung zu sortieren, beispielsweise mit NAUTY oder BLISS.

n

$n$

Simon

19

Der wahrscheinlich einfachste Weg, alle nicht-isomorphen Graphen für kleine Scheitelpunktzahlen aufzulisten, besteht darin, sie aus Brendan McKays Sammlung herunterzuladen . Der Aufzählungsalgorithmus ist in einem Artikel von McKay [1] beschrieben und erweitert Nichtisomorphe der Größe n-1 auf alle möglichen Arten und überprüft, ob der neue Scheitelpunkt kanonisch war. Es ist wie gengin McKays Graph Isomorphism Checker implementiert nauty.

[1]: BD McKay, Applications of a technique for labelled enumeration , Congressus Numerantium, 40 (1983) 207-221.

David Eisenstat
quelle

Ich habe ein Problem. Ich nehme ein Diagramm der Größe n-1und erweitere es, wie Sie sagten, um einen Scheitelpunkt auf alle möglichen Arten. Dann überprüfe ich, ob der Scheitelpunkt eine kanonische Bezeichnung hat, sagen wir 1(kanonischer Scheitelpunkt ?!). Was ist jedoch, wenn der Graph nur isomorph zur kanonischen Form ist und der Scheitelpunkt eine andere Bezeichnung hat? Ich habe versucht, die Automorphismen zu überprüfen, um festzustellen, ob sich der Scheitelpunkt mit der Bezeichnung 1in derselben Umlaufbahn befindet, aber dann lande das Diagramm zweimal in meiner Liste. Das Papier hilft mir nicht wirklich. Außerdem ist der Quellcode von geng aufgrund all dieser binären Optimierungen und kaum vorhandener Kommentare nicht lesbar.

Alex

1

@Alex Sie möchten auf jeden Fall die Version der Prüfung, die bestimmt, ob sich der neue Scheitelpunkt in derselben Umlaufbahn wie 1 befindet. Können Sie ein Beispiel nennen, in dem dies zwei isomorphe Graphen erzeugt? Vielleicht wäre das besser als eine neue Frage.

David Eisenstat

Okay, ich danke Ihnen sehr! Ich denke in diesem Fall muss "auf alle möglichen Arten erweitern" irgendwie Automorphismen des Graphen mit n-1Eckpunkten berücksichtigen ? zB n = 3 und mein vorheriger Graph war P2. Dann ergeben die beiden Fälle, in denen ich den dritten Scheitelpunkt mit einem der vorherigen Scheitelpunkte verbinde, natürlich denselben Graphen P3. Könnten Sie kurz erklären, wie man richtig "auf alle möglichen Arten erweitert", oder sollte ich dies als eine andere Frage stellen? (Manchmal bin ich auch verwirrt darüber, was passiert, da mein Programm Nicht-Isomorphismen eines bestimmten Diagrammtyps finden muss, was die Dinge etwas komplizierter macht.)

Alex

@Alex Ja, es scheint, dass die Erweiterung selbst kanonisch sein muss. Wahrscheinlich eine neue Frage wert, da ich mich nicht mehr daran erinnere, wie das von Kopf bis Fuß funktioniert.

David Eisenstat

1

Nauty Homepage

Guy Coder

4

Ich schlage eine Verbesserung Ihrer dritten Idee vor: Füllen Sie die Adjazenzmatrix zeilenweise aus, und verfolgen Sie dabei Scheitelpunkte, die hinsichtlich Grad und Adjazenz den zuvor ausgefüllten Scheitelpunkten gleichwertig sind. Die Äquivalenzklassen bestehen also zunächst aus allen Knoten mit dem gleichen Grad.
Wenn ein neu gefüllter Scheitelpunkt nur einigen der äquivalenten Knoten benachbart ist, führt jede Auswahl zu Repräsentanten aus denselben Isomrphismusklassen. Daher wird nur die Zuweisung berücksichtigt, bei der der aktuell gefüllte Eckpunkt neben den entsprechenden Eckpunkten mit der höchsten Nummer liegt (und die Äquivalenzklasse für den verbleibenden Prozess in zwei geteilt wird).

$n<6$
$(1,2)$ $(3,4)$ $n=6$

Eine naive Implementierung dieses Algorithmus stößt auf Sackgassen, bei denen sich herausstellt, dass die Adjazenzmatrix nicht mit den angegebenen Gradzahlen und vorherigen Zuordnungen gefüllt werden kann. Es kann sich lohnen, diese frühzeitig zu erkennen / zu filtern. Einige Ideen:

Wenn die Summe der Grade ungerade ist, bilden sie niemals ein Diagramm
Füllen Sie Einträge für Scheitelpunkte, die sofort mit allen / keinem der verbleibenden Scheitelpunkte verbunden werden müssen.

FrankW
quelle

3

Diese Papiere könnten von Interesse sein.

"Über die prägnante Darstellung von Graphen", György Turan, Discrete Applied Mathematics, Band 8, Ausgabe 3, Juli 1984, S. 289-294 http://www.sciencedirect.com/science/article/pii/0166218X84901264

"Prägnante Darstellung allgemeiner unbeschrifteter Graphen", Moni Naor, Discrete Applied Mathematics, Band 28, Ausgabe 3, September 1990, S. 303-307 http://www.sciencedirect.com/science/pii/0166218X9090011Z

Sie bieten Codierungs- und Decodierungsfunktionen für die Codierung eines vertex-markierten Graphen, sodass zwei solcher Graphen genau dann auf dasselbe Codewort abgebildet werden, wenn eines davon durch die Permutation der vertex-Labels des anderen resultiert.

Darüber hinaus ist nachgewiesen, dass die Codierungs- und Decodierungsfunktionen effizient sind.

Der erste Artikel befasst sich mit ebenen Graphen. Im zweiten Aufsatz wird die Planaritätsbeschränkung aufgehoben.

EDIT: Dieses Papier könnte auch relevant sein:

Graph Isomorphism in Quasi-Polynomial Time, Laszlo Babai, Universität Chicago, Preprint auf arXiv, 9. Dezember 2015 http://arxiv.org/pdf/1512.03547v1.pdf

Babais Bekanntgabe seines Ergebnisses brachte die Nachricht: https://www.sciencenews.org/article/new-algorithm-cracks-graph-problem

Aber vielleicht irre ich mich, die OP-Frage mit diesen drei Papieren zu verwechseln? Das OP möchte nicht-isomorphe Graphen aufzählen, aber es kann dennoch hilfreich sein, über effiziente Methoden zu verfügen, um zu bestimmen, wann zwei Graphen isomorph sind.

Simon
quelle

Ich schätze den Gedanken, aber ich fürchte, ich frage nicht, wie ich feststellen soll, ob zwei Graphen isomorph sind. Ich frage mich wirklich, wie man nicht-isomorphe Graphen aufzählt. Algorithmen zu beschreiben, um zu testen, ob zwei Graphen isomorph sind, hilft mir leider nicht wirklich - danke, dass Sie es trotzdem versucht haben!

DW

Turan und Naor (in den oben erwähnten Abhandlungen) konstruieren Funktionen des von Ihnen beschriebenen Typs, dh, die einen Graphen in einen kanonischen Repräsentanten der Äquivalenzklasse abbilden, zu der dieser Graph gehört. Wenn Sie diese kanonischen Vertreter aufzählen könnten, wäre Ihr Problem anscheinend gelöst.

Simon

Babai widerrief die Behauptung der quasipolynomialen Laufzeit . Anscheinend gab es einen Fehler in der Analyse.

Raphael

1

Es gibt einen Artikel aus den frühen neunziger Jahren, der genau diese Frage behandelt:

Effiziente Algorithmen zur Auflistung unbeschrifteter Grafiken von Leslie Goldberg.

Der Ansatz garantiert, dass genau ein Repräsentant jeder Isomorphismusklasse gezählt wird und dass zwischen der Erzeugung zweier aufeinanderfolgender Graphen nur eine polynomielle Verzögerung besteht.

$n$

Pascal Welke
quelle

Zählen Sie alle nicht-isomorphen Graphen einer bestimmten Größe auf

Antworten: