Isomorphie planarer Graphen

Ein effizienter Algorithmus


Dieser Algorithmus entstand als ich für ein Computerspiel, in dem planare Graphen vorkommen, einen schnellen Isomorphie Test benötigte.
Er testet die Isomorphie von in die Ebene oder Kugeloberfläche eingebetter Graphen.
Bei Testdurchläufen (eher kleinerer Graphen) ergab sich ein Laufzeitverhalten im durchschnittlichen Fall von ca. k hoch 1,25  (k = Anzahl der Kanten)

Er erzeugt eine normalisierte Darstellung eines Graphen, so dass alle zueinader isomorphen Graphen zur gleichen Normaldarstellung führen und nicht isomorphe Graphen zu verscheidenen Normaldarstellung führen. Die Normaldarstellung kann wahlweise ein Graph oder eine Zeichenkette sein.
Dadurch ist es möglich einen Graphen schnell mit einer grossen Menge bereits bekannter Graphen zu vergleichen. (indem deren Normaldarstellung z.B. in einer Hashtabelle abgelegt wird).

Der Algorithmus geht davon aus, dass die Graphen schon explizit in planarer Darstellung vorliegen, z.B dass zu jeder Kante gespeichert ist, welche Fläche links und rechts dieser Kante liegt.  Er verwendet Pfade, das sind geschlossene Wege entlang der Kanten, die entstehen, wenn man an jedem Punkt rechts abbiegt.
In der beschriebenen Form funktioniert er für Graphen ohne Mehrfachkanten und Schlingen (=kante von einem Punkt zu sich selbst). Mit einer kleinen Änderung funktioniert er auch mit Mehrfachkanten und Schlingen.

Die Isomorphie kann wahlweise für eine feststehende Aussenfläche untersucht werden (das sind dann die Graphen, die sich durch verzerren in der Ebene ineinander überführen lassen), oder ohne feststehende Aussenfläche (das sind dann die Graphen, die sich durch verzerren auf einer Kugeloberfläche ineinander überführen lassen.

Es folgt der Algorithmus in der Grundform, danach folgen Details zur Verbesserung der Effiizienz.
Hier ohne feststehene Aussenfläche, Ergebniss ist ein String.
 normalisiere_graph(g):
fuer alle flaechen a in g:
normalisiere_flaeche_ohne_pfad(a,kein pfad)
ergebins = kleinster wert.

normalisiere_flaeche_ohne_pfad(a,oph):
fuer alle pfade ph an a, ausser oph:
normalisiere_netz_von_pfad_aus(ph)
ergebnis = sortierte folge der ergebnisse, getrennt durch ';'.
gefolgt von '.' fuer jeden kantenlosen Punkt an a

normalisiere_netz_von_pfad_aus(ph)
fuer alle kanten c in ph:
normalisiere_netz_von_kante_aus(c)
ergebnis = kleinster wert.

normalisiere_netz_von_kante_aus(stc)
merke kante stc vor.
fuer alle (jetzt oder spaeter) vorgemerkten kanten c
in reihenfolge der vormerkungen
ph ist der pfad von c.
wenn ph noch nicht bearbeitet:
laufe den pfad entlang, beginnend mit c;
liste alle punktnamen auf, merke an jedem punkt die vom pfad
links abzweigende kante vor.
wenn c nicht stc ist, und an der flaeche von c noch weitere pfade liegen:
fuege in '[' ']' eingeschlossen hinzu:
normalisiere_flaeche_ohne_pfad(ph).
ergebnisse getrennt durch ','.
im ergebnis nummeriere die punktnamen ausserhalb [] so um,
dass der zuerst genannte punkt A heisst, der als zweites genannte B , usw.

Wenn die Aussenflächen feststehen soll, dann wird in normalisiere_graph nur die Aussenfläche verwendet.

Effizienzverbesserungen:

Dort wo verschiedene Varianten durchprobiert werden müssen, lässt sich die Verabeitungsgeschwindig keit deutlich erhöhen, wenn bei offensichtlich verschiedenen Varianten nach einem willkürlichen Verfahren eine ausgewählt wird. Z.B beim durchtesten aller potentiellen "Aussenflächen" in normalisiere_graph brauchen nur diejenigen berücklsichtigt zu werden, die die meisten und längsten Pfade enthalten. In normalisiere_netz_von_pfad_aus brauchen nur etwa nur kanten ausgewählt werden, deren startpunkte die grösste Anzahl von Kanten haben.
normalisiere_flaeche_ohne_pfad wird innerhalb von normalisier_graph (indirekt) möglicherweise mehrmals mit den selben parametern aufgerufen. Einmal berechnete Werte können dann zwischengespeichert und beim nächsten Aufruf direkt zurückgegeben werden.

Die gute Effizienz im durchschnittliche Fall kommt daher, dass es an vielen Stellen oft möglich ist eine triviale Vorauswahl zu treffen, anstatt alle Varianten durchzuprobieren. Z.B liegen meistens nicht an allen Flächen gleich viele Kanten.

Korrekteitsbeweis Teil1 (für zusammenhängende Graphen)
Der Algorithmus arbeitet auf einer Datenstruktur, die die kombinatorische Beziehung zwischen Punkten, Kanten und Gebieten darstellt.
Wir beweisen hier nicht, dass diese Struktur den Graphen bis auf topologische Isomorphie eindeutig darstellt; sondern nur dass der Algoritmus, angewendet auf zwei solche Strukturen genau dann das selbe Resultat liefert, wenn diese Isomorph sind.
Wir betrachten zuerst nur zusammenhängende Graphen.
Bei einer Einbettung eines Graphen in die Ebene oder Kugeloberfläche gehen die Kanten an einem Punkt sternförmig von diesem ab, d.h. sie haben eine zyklische Ordnung. Diese Ordnung bleibt unter stetigen Deformationen ohne Überschneidungen erhalten.
Wir stellen den Graphen (weil es praktischer ist) als Graphen mit gerichtetn Kanten dar. Für jede Linie im Graph haber wir dann 2 gerichtete Kanten.
Wir schreiben k.p und k.q für den Anfangs- und Endpunkt einer Kante; Da die Graphen keine Schlingen und Mehrfachkanten enthalten ist eine Kante eindeutig durch die Angabe von Start- und Endpunkt bestimmt. Weiter schreiben wir o(k) für die Rückwärts-Kante zu k, und l(k) für die Kante, die von k.p gegen den Uhrzeigersin abgeht.  Also
o(o(k)) = k;  o(k1)=k2 ↔ k1.p=k2.q ∧ k1.q=k2.p  (1)
l(k).p = k.p;     ln(k) = k, mit n=Anzahl der abgehenden Kanten an k.p. (2)
Wenn wir die Kanten so entlang laufen, dass wir an jedem Punkt immer rechts abbiegen, dann ergeben sich geschlossenen Pfade. Wir definieren s(k) als die Nachfolgerkante im Pfad von k mit
s(k) := l(o(k));         (⇒ l(k) = s(o(k)) ).       (⇒s(k).p = k.q)             (3)
Die Pfadnachfolgerfunktion s ergibt sich also eindeutig aus l und umgekehrt lässt sich l aus s rekonstruieren.
Für unsere Datenstruktur ist es daher ausreichend, eine dieser beiden Beziehungen zu codieren.
Wir wollen ausserdem noch die Pfade, die sich aus s(k) ergeben, durchnummerieren und schreiben ph(k) für die Pfadnummer der Kante k.
ph(k1) = ph(k2) ↔ ∃ n∊N:sn(k1)=k2;     (⇒ ph(k) = ph(s(k));) (4)
Wenn wir die Isomorphie in der Ebene (statt auf der Kugel) untersuchen wollen, muss markiert sein, welcher Pfad am Aussengebiet liegt; wir können auch festlegen, das dieser immer die Nummer 0 bekommt.
In den Programmfragmenten kodieren wir Punkte , Kanten, Pfade als Zahlen jeweils 0,1,2,.... Für die Beweise stellen wir uns aber vor dass die einzelnen Objekttypen disjunkte Grundmengen benutzen)

Ein Isomorphismus φ von einem Graphen g nach h ist eine Abbildung, die Punkte von g auf Punkte von h sowie Kanten von g auf Kanten von h jeweils bijektiv abbildet, und zusätzlich für alle Kanten k von g folgende Bedingungen erfüllt:
φ(k.p) = φ(k).p;     φ(k.q) = φ(k).q; (⇒ φ(o(k)) = o(φ(k)) )           (I1)
φ(l(k)) = l(φ(k)) (⇔ φ(s(k)) = s(φ(k)) ) (I2)
Die Folgerung bei (I1) gilt, weil p und q eine Kante im Graphen eindeutig festlegen, und o((p,q)) = (q,p)
Bei (I2) haben wir wegen (3) die Wahl, welche beiden der Bediingungen wir fordern.
Wenn wir auch Pfadnummern abbilden wollen definieren wir   φ(ph(k)) := ph(φ(k)). Diese Abbildung ist für einen Isomorphismus wohldefiniert und bijektiv :  ph(k1)=ph(k2) ⇔ ∃n:sn(k1)=k2 ⇔ ∃n: sn(φ(k1)) = φ(k2)  ⇔ ph(φ(k1))=ph(φ(k2))  .
Diese Isomorphie entspricht der Topologischen Isomorphie auf der Kugeloberfläche. Für die Ebene muss dann zusätzlich noch gelten:  
φ(pfad0) = pfad0.    (IE)
Ist φ ein Isomorphismus, so ist auch φ⁻¹ ein Isomorphismus: Ist k' = φ(k),  so ist
φ⁻¹(k'.p) = φ⁻¹(p(k).p) = φ⁻¹(φ(k.p)) = k.p = φ⁻¹(k').p;  analog, mit l,s,o.
g≅h :↔ ∃ isomorphismus g→h; (wenn ohne Zusatzangabe dann: ohne IE)
Ein Graph ist i.A. nicht isomorph zu seinem Spiegelbild, da dort die l()-sequenzen in umgekehrter Reihenfolge sind.

Betrachten wir jetzt folgende Funktion: nnk:  (graph,kante)→string
void nnk(const graph & g, int stk, char * res)   // graph und startkante
{ bool ph_done[MAXPH] = {0}; // merker fuer bearbeitete pfade
int vk[MAXK], nvk=1,i,k; vk[0]=stk; // vk ist liste von kanten
for(i=0;i!=nvk;++i) // arbeite liste ab
{ if(i) *res++=';'; // trenne pfade durch ';'
k = vk[i]; do // durchlaufe pfad an vk[i]
{ *res++= (char) ('A' + g.kp0(k)); // notiere punktnamen
int l=g.l(k); // trage linken abzweig in liste ein
if(!ph_done[g.kph(l)]) // wenn dessen pfad noch nicht vorkam
  { vk[nvk++]=l; ph_done[g.kph(l)=true; }
k=g.s(k);  // naechste kante im pfad
} while(k!=vk[i]); // bis 1* rum
} *res = '\0'; // stringende markieren
}
nnk erzeugt einen string, der für alle Pfade die Punkntamen aufzählt und durch ';' trennt.
Behauptung: aus dem Resultat von nnk lassen sich Graph und Startkante bis auf Isomorphie rekonstruiern bzw. für zwei zusammenhaengende Graphen g und h sowie je eine Kante kg von g und kh von h gilt:
(g,kg) ≅ (h,kh)   ⇔    nnk(g,kg) ≅ nnk(h.kh),                                                  (10)
wobei die linke Seite meint, es gibt einen Isomorphismus von g nach h, der kg auf kh abbildet; und zwei Zeichenketten s1,s2 von Punktnamen isomorph sind, wenn eine Bijektion von Punktnamen existiert, die bei zeichenweiser Anwendung auf s1 s2 ergibt (';' bleiben unverändert).

Beweis. Die Funktion durchläuft den gesamten Graphen, denn:
Zu jeder Kante die bearbeitet wird, wird ihr kompletter Pfad bearbeitet; Zu jeder Kante k wird auch l(k) bearkeitet, d.h. für jeden Startpunkt einer Kante, werden alle Kanten an diesem Punkt bearbeitet, und für jede Kante wird auch die Kante ab k.p1 bearbeitet, denn s(k).p0 = k.p1.
Da der Graph zusammenhängend ist, werden so alle Punkte und Kanten erreicht. Die Ausgabe enthält jede Kante genau einmal, in form zweier hintereinanderstender Buchstaben (bzw. das Paar am Ende und Anfang einer Sequenz).

Seien jetzt g und h zwei Graphen und φ ein Isomorphismus g→h mit φ(kg) = φ(kh) für je eine kante kg aus kh und k aus h.
Die Aufrufe nnk(g,kg) und nnk(hh,kh) verlaufen dann völlig synchron (wenn man sie schrittweise abarbeitet), da im Algorithmus nur die Funktionen l(k) , s(k) , ph(k) benutzt werden und es gilt ja wegen (I2) etwa s(kh) = s(φ(kg)) = φ(s(kg)) ; s(s(kh)) = s(s(φ(pk)) = φ(s(s(kg)), ...
Für die Ergebnisse gilt dann φ(nnk(g,gk)) = nnk(h,hk)), wenn φ angewendet auf einen string von Punktnamen bedeuten soll, dass diese zeichenweise abgebildet werden, und die ';' unverändert bleiben.

Sind jetzt umgekehrt g und h zwei Graphen und kg und kh jeweils eine Kante aus g und aus h, und es existiert eine Bijektion von Punktnamen φ mit  φ(rg:= nnk(g,kg))  =  nnk(h.kh) =: rh.   Dann lässt sich φ znnächst eindeutig zu einer Bijektion auch auf Kanten fortsetzen:
Für einen index i im string r bedeute  i+ den folgenden index, wenn auf diesem ein Punktname steht, oder sonst den beginn der Punktnamenkette.
Wir setzen φ( (rg[i],rg[i+]) := (rh[i],rh[i+]) für alle i mit rg[i]≠';'. (Die Kanten sind durch Angabe von Start- und Endpunkt eindeutig bestimmt, jede Kante kommt genau einmal in den strings vor). Dann gilt automatisch  (I1)  für φ.
Wegen der Arbeitsweise vonn nnk gilt in den strings immer  s((r[i],r[i+])) =  (r[i+],r[i++]) .Damit ist wegen
φ(s(rg[i],rg[i+])) = φ((rg[i+],rg[i++])) = (rh[i+],rh[i++]) = s((rh[i],rh[i+])) = s(φ((rg[i],rg[i+])))
auch I2 erfüllt und φ ist der gesuchte Isomorphismus.☐.

Betrachten wir jetzt folgende Funktion umb: string→string
void umb(char * p)
{ char newname[MAXPTS] = { 0 }; //neue namen fuer c-'A'
char curr = 'A'; char * pstart = p;
for(;*p;++p)
if(*p>='A' && newname[*p-'A']==0)
newname[*p-'A'] = curr++;
for(p=pstart;*p;++p)
if(*p>='A') *p=newname[*p-'A'];
}
Sie ermittelt für jeden Buchstaben im string die Anzahl der verschiedenen Buchstaben vor dem ersten Auftreten, und benennt dann so um, dass der zuerst auftretende Buchstabe 'A' heisst, der zweite 'B', usw. Als mathematische Funktion schreiben wir:  umb(vorher) = nachher.
Es gilt: s1 ≅ s2 ⇔ umb(s1) = umb(s2).                                               (11)
Beweis. ⇐ ist klar , da umb selbst den string bijektiv umbenennt, also umb(s1) ≅ s1 und umb(s2) ≅ s2.  (c1≠c2 → newname[c1-'A']≠newname[c2-'A'], da curr hochgezählt wird)
⇒: ist φ:char→char eine bijektion mit φ(s1)=s2.  rufen wir umb einmal mit s1 und einmal mit φ(s1) auf, dann wird das array 'newname' einmal mit den Zeichen aus s1 angesprochen und einmal mit ihren Bildern, also newname[c] = newname'[φ(c)]. Da newname dann im zweiten Teil der Funktion zeichenweise als bijektion angewendet wird, ist   umb(s1) = newname(s1) und umb(φ(s1)) = newname'(φ(s1)) = newname(s1) = umb(s1). ☐
Wir schreiben nnku(g,k) := umb(nnk(g,k),  und wegen (10) ergibt sich:
  (g,kg) ≅ (h,kh)   ⇔    nnku(g,kg)) = nnku(h.kh)).                                     (12) ☐

Betrachen wir jetzt die Funktion normg: graph→string
void normg(const graph & g, char * res)
{ char * bf[100]; *res='z';
if(g.nedges==0) { res[0]=g.npoints?'.':'\0';
res[1]='\0'; return; }
for(int k=0; k!=g.nedges; ++k)
{ nnk(g,k,bf); umb(bf);
if(strcmp(bf,res)<0) strcpy(res,bf);
}
}
Für Graphen ohne Kanten liefert sie "." bzw "" (ein punkt / kein punkt), sonst ruft sie nnku(g,k) für alle Kanten k auf und liefert den kleinsten Wert zurück.
Es gilt: g≅h ⇔ normg(g) = normg(h)         (13)    (fuer zusammenhängende Graphen)
Beweis. Die Graphen ohne Kante mit 0 bzw 1 Punkt(en) bilden jeweis eine eigene Isomorpieklasse.
Haben g und h also mindestens eine Kante. Sei Mg = { nnku(g,kg) | kg∊g } und Mh = { nnku(h,kh) | kh∊h }
⇒: Sei φ:g≅h.  φ bildet jede Kante von g auf eine Kante von h ab, und φ⁻¹ tut dies umgekehrt.
∀kg∊g ∃kh∊h : (g,kg)≅(h,kh) , und ∀kh∊h ∃kg∊g : (g,kg)≅(h,kh)      ⇒ (wegen (11))
∀kg∊g ∃kh∊h  nnku(g,kg) =  nnku(h,kh)  und  ∀kh∊h ∃kg∊g  nnku(g,kg) = nnku(h,kh).
Also Mg⊆Mh und Mh⊆Mg , ⇒ Mg=Mh ⇒ min(Mg) = min(Mh).
⇐: min(Mg) = min(Mh) ⇒ ∃x∊Mg ∃y∊Mh:x=y  ⇔
∃kg∊g ∃kh∊h : nnku(g,kg) = nnku(h,ku) ⇔
∃kg∊g ∃kh∊h : (g,kg) ≅ (h,kh)    ⇔   g≅h  ☐

normg normalisiert also den zusammenhängenden Graph bzgl. Isomorphie auf der Kugeloberfläche. Um auf Ebene-Isomorphie zu normalisieren brauchen wir uns in normg bloss auf die Kanten zu beschränken, die am Aussenpfad liegen. Das ergibit sich aus der Behauptung:
g≅Ebeneh ⇔ ∃kg an g.pfad0 ∃hk an h.pfad0: (g,kg)≅(h,kh)
⇔ ∀kg an g.pfad0 ∃hk an h.pfad0: (g,kg)≅(h,kh)
, weil wir dann damit  genauso wie im Beweis zu normg argumentieren können. 
Beweis der Behauptung: 3→2: klar, wegen ∀→∃.   2→1: :aus φ: (g,kg)≅(h,kh)  folgt φ(kg)=kh, und damit φ(g.ph(kg)) = h.ph(kh), also φ(g.pfad0)=h.pfad0.   1→3:  Sei φ:g≅h mit φ(g.pfad0)=h.pfad0, dann ist für alle Kanten kg mit g.ph(kg) = g.pfad0 :  h.ph(φ(kg)) = φ(g.ph(kg)) = φ(g.pfad0) = h.pfad0, also φ(kg) ist die gesuchte Kante an h.pfad0. ☐

www.reisz.de