Algorithmus für die Bestimmung, wenn 2 Graphen sind isomorph,
Disclaimer: ich bin ein total Neuling auf der graph-Theorie und ich bin mir nicht sicher, ob dies gehört ALSO an, Mathematik SE, etc.
Gegeben 2 angrenzens Matrizen A und B, wie kann ich ermitteln, ob A und B sind isomorph.
Beispielsweise, A und B sind nicht isomorph, und C und D sind isomorph.
A = [ 0 1 0 0 1 1 B = [ 0 1 1 0 0 0
1 0 1 0 0 1 1 0 1 1 0 0
0 1 0 1 0 0 1 1 0 1 1 0
0 0 1 0 1 0 0 1 1 0 0 1
1 0 0 1 0 1 0 0 1 0 0 1
1 1 0 0 1 0 ] 0 0 0 1 1 0 ]
C = [ 0 1 0 1 0 1 D = [ 0 1 0 1 1 0
1 0 1 0 0 1 1 0 1 0 1 0
0 1 0 1 1 0 0 1 0 1 0 1
1 0 1 0 1 0 1 0 1 0 0 1
0 0 1 1 0 1 1 1 0 0 0 1
1 1 0 0 1 0 ] 0 0 1 1 1 0 ]
(sorry for this ugly notation, I'm not quite sure how to draw matrices on SO)
Hier ist, wie ich angefangen habe, meinen Algorithmus (verzeihen Sie meine fehlende mathematische strenge) helfen Sie mir bitte vervollständigen/korrigieren!
- Wenn die Größe (Anzahl der Kanten, in diesem Fall die Menge des 1s) von A != Größe B => Graphen sind nicht isomorph,
- Für jeden vertex Eines, zählen Grad und suchen nach einem passenden vertex in B, welche den gleichen Grad und nicht angepasst worden, früher. Wenn keine übereinstimmung vorhanden ist => Graphen sind nicht isomorph.
- Jetzt, wir können schnell beweisen, dass A und B sind nicht isomorph, was ist der nächste Schritt?
Würde es richtig sein versuchen jede permutation von Zeilen, bis Eine entspricht B? Wirklich nicht sicher, über diese ein...
- Ich bin sicher, es ist schrecklich, aber man konnte immer brute-force es: halten Sie die Knoten in Einer Reihenfolge, gehen Sie dann durch jede permutation der Beschriftung der Knoten in B, bis Sie passen, oder gibt es keine mehr. Natürlich, es ist fast sicher der bessere Weg... so...
- en.wikipedia.org/wiki/... scheint, dass niemand weiß, Polynom-Zeit-Algorithmus. Also es ist ok nur brute-force. versuchen Sie jede permutation der Knoten von gleichem Grad etc.
- dieser Algorithmus kann die Antwort sein Ihr suchen. link für einen polynomialzeit-Algorithmus für Graphen isomorph, Prüfung und Zuordnung
Schreibe einen Kommentar
Du musst angemeldet sein, um einen Kommentar abzugeben.
Ist ein ziemlich schwieriges problem zu lösen. Es ist eine Wikipedia Seite über ihn:
Laut dieser Seite gibt es eine Reihe von speziellen Fällen, die gelöst werden können, effiziente polynomieller Zeit Lösungen, aber die Komplexität der optimalen Lösung ist noch unbekannt.
Mein Projekt - Griso - bei sf.net: http://sourceforge.net/projects/griso/ mit dieser Beschreibung:
Griso ist ein graph-Isomorphismus-Testprogramm in C++ geschrieben und basiert auf meinen eigenen algo.
Sehen Griso ' s sample-Eingang/Ausgang auf diese Seite: http://funkybee.narod.ru/graphs.htm
Gut, es ist sehr einfach, schnell zu sagen, dass Sie NICHT isomorph sind, indem Sie die folgenden.
areIsomorphic(G1, G2):
if(G1.num_verticies != G2.num_verticies)
return False
if(G1.num_total_edges != G2.num_total_edges)
return False
for each vertex v in G1:
if( G2.find(v).edges != v.edges):
return False;
//Try and find a property in graph G1 that does not exist in G2.
//Use a heuristic. ie- try and find nonmutually adjacenct sets.