Algorithmus zur Bestimmung, ob 2 Graphen isomorph sind

8

Disclaimer: Ich bin ein absoluter Neuling in der Graphentheorie und ich bin mir nicht sicher, ob das auf SO, Mathe SE, etc.

gehört

Wie kann ich, wenn zwei Adjazenzmatrizen A und B gegeben sind, feststellen, ob A und B isomorph sind?

Zum Beispiel A und B, die nicht isomorph sind, und C und D, die isomorph sind.

%Vor%

Hier ist, wie ich meinen Algorithmus gestartet habe (entschuldige meinen Mangel an mathematischer Strenge), bitte hilf mir, zu vervollständigen / zu korrigieren!

  1. Wenn Größe (Anzahl der Kanten, in diesem Fall 1s) von A! = Größe von B = & gt; Graphen sind nicht isomorph
  2. Zählen Sie für jeden Stützpunkt von A seinen Grad und suchen Sie nach einem übereinstimmenden Stützpunkt in B, der den gleichen Grad hat und nicht früher gefunden wurde. Wenn es keine Übereinstimmung gibt = & gt; Graphen sind nicht isomorph.
  3. Nun, da wir nicht schnell beweisen können, dass A und B nicht isomorph sind, was ist der nächste Schritt? Wäre es richtig, probiere alle Permutationen der Linien in A aus, bis A zu B passt? Wirklich nicht sicher über dieses ...
Olivier Lalonde 06.10.2010, 19:58
quelle

3 Antworten

7

Das ist ein ziemlich schwer zu lösendes Problem. Es gibt eine Wikipedia-Seite darüber:

Nach dieser Seite gibt es eine Reihe von Sonderfällen, die mit effizienten Polynomzeitlösungen gelöst wurden, aber die Komplexität der optimalen Lösung ist noch unbekannt.

    
Mark Byers 06.10.2010, 20:08
quelle
4

Mein Projekt - Griso - auf sf.net: Ссылка mit dieser Beschreibung:
Griso ist ein Graphisomorphismus-Testprogramm, das in C ++ geschrieben wurde und auf meinem eigenen Algorithmus basiert.
Sehen Sie Grisos Beispiel-Eingabe / Ausgabe auf dieser Seite: Ссылка

    
trg787 11.04.2011 20:29
quelle
0

Nun, es ist sehr einfach, schnell zu erkennen, dass sie NICHT isomorph sind, indem Sie Folgendes tun. 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.

    
Alex Spencer 10.12.2014 04:52
quelle

Tags und Links

Django: Verwenden von Annotate, Count und Distinct in einem Queryset Automatische Aktualisierung von C # -Programmen