Ich möchte fragen, ob es dazu bereits ein veröffentlichtes Ergebnis gibt:
Wir nehmen alle möglichen unterschiedlichen Pfade zwischen jedem Knotenpaar zweier verbundener regulärer Graphen (mit dem Grad , sagen wir, und der Anzahl der Knoten ) und schreiben ihre Längen auf. Natürlich ist diese Anzahl unterschiedlicher Pfade exponentiell. Meine Frage ist, wenn wir die Längen sortieren und vergleichen (die von den beiden Diagrammen erhaltenen Listen) und sie genau gleich sind, können wir dann sagen, dass die beiden Diagramme isomorph sind?n
Selbst wenn dies ein Ergebnis ist, können wir es natürlich nicht verwenden, um auf den Graphisomorphismus zu antworten, da die Anzahl der unterschiedlichen Pfade wie gesagt exponentiell ist
Mit unterschiedlichen Pfaden beziehe ich mich offensichtlich auf Pfade mit mindestens einem unterschiedlichen Knoten.
Vielen Dank von vornherein für Ihre Hilfe.
Antworten:
Ich glaube, die Antwort auf Ihre Frage lautet "Nein", da eine äquivalente Bedingung eine polynomielle Zeitlösung für GI implizieren würde.
Für , den Adjazenzmatrix des Graphen , zu beachten , dass die Anzahl der Pfade von zu der Länge ist (mit Wiederholung von Eckpunkten und Kanten erlaubt). Für zwei Graphen und (mit Adjazenzmatrizen und ) und , wenn Sie die Elemente geordnet und dann um zu isomorph sein , ist es eine notwendige Bedingung , dass Die Listen sind für alle identisch .G i j k ( A k ) i , j G 1 G 2 A 1 A 2 k ≥ 1 A k 1 A k 2 G 1 G 2 kEIN G ich j k ( A.k)ich , j G1 G2 EIN1 EIN2 k ≥ 1 EINk1 EINk2 G1 G2 k
Ich glaube, Ihre Vermutung ist gleichbedeutend mit:
Wenn die sortierten Listen der Elemente von und für bis identisch sind (oben auf dem längsten Pfad mit sich nicht wiederholenden Eckpunkten), sind und isomorph. A d 2 k = 1 n - 1 G 1 G 2EINk1 EINd2 k = 1 n - 1 G1 G2
Um GI zu lösen, muss man nur Multiplikationen von Matrizen durchführen (und ein wenig mehr Zeit, um Elemente zu sortieren und zu vergleichen ). Dies würde weniger als Stunden dauern .n × n n 2 n 4n - 1 n × n n2 n4
Ich gebe zwei mögliche Fehler in meiner Argumentation zu. Erstens ist es durchaus möglich, dass GI einen Polynom-Zeitalgorithmus hat und dass wir ihn gerade zusammen entdeckt haben (Hurra, wir sind berühmt!). Ich finde das höchst unwahrscheinlich. Zweitens (und viel wahrscheinlicher) entspricht das, was ich vorgeschlagen habe, nicht Ihrer Vermutung.
Letzter Gedanke. Haben Sie dies für alle ausprobiert, beispielsweise für 3-reguläre Diagramme für Größe 8 oder so? Ich würde denken, wenn Ihre Vermutung falsch ist, sollte es ein Gegenbeispiel in 3-regulären Graphen von ziemlich kleiner Größe geben.
quelle
Da Sie nur die Längen der Pfade vergleichen (und in der Zwischenzeit vergessen, welchem Knotenpaar sie entsprechen, wenn ich Sie gut verstanden habe), sollten sehr ähnliche Diagramme ein Gegenbeispiel darstellen: Am Ende zählen Sie nur die Anzahl der Pfade mit fester Länge und unabhängig von den Scheitelpunkten, die sie verbinden. Zum Beispiel denke ich, dass diese Grafiken ein Gegenbeispiel sind: http://www.mathe2.uni-bayreuth.de/markus/REGGRAPHS/GIF/06_3_3-2.gif und http://www.mathe2.uni-bayreuth.de/ markus / REGGRAPHS / GIF / 06_3_3-1.gif
Wenn ich mich nicht irre (das Zählen von Pfaden ist mühsam), haben beide 9 Pfade der Länge 1, 18 Pfade der Länge 2, 48 Pfade der Länge 3, 30 Pfade der Länge 4 und 36 Pfade der Länge 5
quelle
quelle