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