Grundlagen

Graphisomorphismus

 aufwärts

Zwei ungerichtete Graphen G = (V, E) und G' = (V', E') sind gleich, wenn sie dieselbe Knotenmenge und dieselbe Kantenmenge haben, d.h. wenn V = V' und E = E' gilt.

Die beiden folgenden Graphen G und G' sehen zwar gleich aus, sie sind aber nicht gleich (Bild 1). Denn in G sind z.B. die Knoten 0 und 4 durch eine Kante verbunden, während dies in G' nicht der Fall ist.

Bild 1: Zwei gleich aussehende Graphen
Bild 1: Zwei gleich aussehende Graphen

Zwei Graphen, die man so zeichnen kann, dass sie gleich aussehen, werden als isomorph (von gleicher Gestalt) bezeichnet. Formal ist die Isomorphie zwischen zwei Graphen wie folgt definiert.

Definition:  Zwei ungerichtete Graphen G = (V, E) und G' = (V', E') sind isomorph, wenn es eine bijektive Abbildung

f : V Pfeil nach rechts V'

gibt, derart dass

(u, vElement E  genau dann wenn  (f(u), f(v)) Element E'

gilt. Eine solche Abbildung heißt Iso­morphismus zwischen den Graphen G und G'.

Im Folgenden setzen wir der Einfachheit halber voraus, dass V = V' ist. Die Abbildung f ist dann eine Permutation der Knotenmenge V.

Bei den beiden Graphen in Bild 1 ist die Permutation der Knotenmenge implizit dadurch gegeben, dass die einander zugeordneten Knoten jeweils an ent­sprechende Stellen gezeichnet sind (z.B. die 3 und die 0 oben usw.). Die ent­sprechende Abbildung ist

v:  0  1  2  3  4 
 f(v): 43102

Wenn die Abbildung zwischen den Knoten nicht bekannt ist, so ist es nicht ohne weiteres möglich, die einander zugeordneten Knoten an ent­sprechende Stellen zu zeichnen. Es bleibt dann nichts anderes übrig, als die Knoten von G' in irgendeiner Anordnung zu zeichnen, z.B. in derselben Anordnung wie die Knoten von G. Dann ist es weitaus weniger offen­sichtlich, dass die Graphen isomorph sind (Bild 2).

Bild 2: Zwei isomorphe Graphen
Bild 2: Zwei isomorphe Graphen

Jeder Kante (u, v) in G entspricht die Kante (f(u), f(v)) in G' und umgekehrt.

Beispiels­weise entspricht der blau dar­gestellten Kante(1, 4) in G die Kante (f(1), f(4)) = (3, 2) in G'. Der grün dar­gestellten Kante (2, 3) in G entspricht die Kante (f(2), f(3)) = (1, 0) in G'.

 

Ein Graph­isomorphismus ist ein anschau­liches Beispiel für eine Einweg­funktion. Es ist leicht, zu einem gegebenen Graphen G einen isomorphen Graphen G' zu konstruieren (indem einfach die Knotenmenge von G permutiert wird). Umgekehrt dagegen ist es jedoch schwer, zu zwei gegebenen isomorphen Graphen G und G' einen Iso­morphismus zu rekonstruieren. Es bleibt im allgemeinen nicht viel anderes übrig, als alle möglichen Permutationen der Knotenmenge auszuprobieren. Jedenfalls ist zur Zeit kein wesentlich schnellerer Algorithmus bekannt.

Die Graphen dürfen allerdings nicht wie in obigem Beispiel beschaffen sein. Im Beispiel hat G nur einen einzigen Knoten, von dem 4 Kanten ausgehen, also vom Grad 4, nämlich den Knoten 4. Es ist klar, dass ein Iso­morphismus zwischen G und G' Knoten 4 auf Knoten 2 abbildet, nämlich den ent­sprechenden einzigen Knoten vom Grad 4 in G'.

Weiterhin gibt es je zwei Knoten vom Grad 3 und zwei Knoten vom Grad 2. Auch diese müssen jeweils aufeinander abgebildet werden. Es brauchen also bei diesen Graphen längst nicht alle möglichen Permutationen ausprobiert werden, sondern nur sehr viel weniger.

Wenn jedoch in den beiden Graphen alle Knoten denselben Grad haben, dann helfen derartige Überlegungen nicht weiter.

 

Weiter mit:   up

 

homeH.W. Lang   Hochschule Flensburg   lang@hs-flensburg.de   Impressum   ©   Created: 22.11.2003   Updated: 11.06.2016
Valid HTML 4.01 Transitional


Campus Flensburg

Informatik in Flensburg studieren...

 

Neu gestaltetes Studienangebot:

Bachelor-Studiengang
Angewandte Informatik

mit Schwerpunkten auf den Themen Software, Web, Mobile, Security und Usability.

Ihr Abschluss
nach 7 Semestern:
Bachelor of Science

 

Ebenfalls ganz neu:

Master-Studiengang
Angewandte Informatik

Ein projektorientiertes Studium auf höchstem Niveau mit den Schwerpunkten Internet-Sicherheit, Mobile Computing und Human-Computer Interaction.

Ihr Abschluss
nach 3 Semestern:
Master of Science

 

Weitere Informatik-Studienangebote an der Hochschule Flensburg:

Medieninformatik

Wirtschaftsinformatik