zurück zu Grundbegriffe I
Grundbegriffe I
3 Isomorphie von Graphen
Unterschiedliche Graphen (z.B. bei anderer Bezeichnung der Knoten) können die gleiche Struktur und Abbildung aufweisen.
* Definition: Gegeben seien X1 = (V1,E1) und X2 = (V2,E2)
Eine bijektive Abbildung φ: V1→V2 heißt ein ISOMORPHISMUS von X1 auf X2, wenn gilt: [x,y] ⇔ [φ(x), φ(y)] ∈ E2; X1 ≈ X2
3.1 Eigenschaften fon Abbildungen
Die Abbildung f:X→Y kann folgende Eigenschaften haben:
- injektiv: x1∧y2(x1 ≠ x2 → f(x1) ≠ f(x2)) |B| ≥ |A|
jedes Element der Urmenge wird genau einmal in der Zielmenge abgebildet, wobei Elemente in der Zielmenge möglich sind die kein Urbild haben; - surjektiv: x∧y∨(f(x)=y) |B| ≤ |A|
jedes Element der Urmenge wird einmal oder öfter in der Zielmenge abgebildet, wobei Elemente in der Zielmenge ohne Urbild nicht möglich sind; - bijektiv: a ∧ b |B| = |A|
Jedes Element der Zielmenge hat genau ein Urbild und umgekehrt, d.h. bijektiv ist injektiv verknüpft mit surjektiv z.B.:
φ (a ◦ b) = φ (a) ∧ φ (b) → φ (a * b) = φ (a) + φ (b)
log (a*b) = log (a) + log (b)operationentreue Abbildung
z.B.: log(a*b) = log a + log b
bijektive Abbildung der Elemente und der Funktionen
p ∧ q ⇔ ¬( ¬p v ¬q)
Entsprechungen:
∩∪‘
∧∨¬
- isomorph
(bijektiv + strukturerhaltende Abbildung)
Urbildmenge – Bildmenge:- Gleiche Anzahl von Elementen (Knoten u. Kanten)
- Gleicher Knotengrad
- Strukturerhaltung, Nachbarschaften (Abbildungen können unterschiedlich sein)
Bijektive Abblidung zwischen 2er Graphen:
- 1.Abbildung muß umkehrbar eindeutig sein
- 1.wenn ein Knoten im 1. Graphen existiert, genau dann muß er auch im 2. Graphen existieren
3.2 Vorraussetzung
Die Anzahl der Knoten, Knotengrade und Kanten ist gleich.
Der gleiche Graph und doch nicht der selbe (gleiche Struktur). Wegen bijektiver Abb. folgt, daß die gleiche Anzahl an Knoten vorhanden sein müssen.
x y z
X ≈ Y
X und Y sind isomorph.
Beispiel 2:
X1 = ({1,2,3,4,5,6,7}, {[1,2],[1,4],[1,5],[2,3],[2,6],[3,4],[3,7],[4,5],[5,6],[5,7],[6,7]})
X2=({A,B,C,D,E,F,G},[G,F],[E,F],[G,D],[D,E],[C,F],[E,B],[B,C],[A,G], A,D],[A,C],[A,B]})
Der Knoten 5 bzw. A hat den Grad 4.
Permutation – wenn Nachbarschaftsbeziehungen bekannt sind kann nähere Auswahl getroffen werden.
.) Knoten betrachten die bes. Grad aufweisen.
.) Knoten mit best. Grad müssen gleich sein.
.) Knoten mit bes. Grad suchen und dann die Nachbarschaftsbeziehungen feststellen.
Tabelle:
1 | D | G | D | G |
2 | E | E | F | F |
3 | F | F | E | E |
4 | G | D | G | D |
5 | A | A | A | A |
6 | B | B | C | C |
7 | C | C | B | B |
Aufgabe:
a | ||
b | k | k |
c | j | l |
d | ||
e | ||
f | ||
g | o | o |
h |
daher: X¬≅Y
a | u | |
b | t | |
c | s | |
d | r | |
e | q | |
f | x | |
g | w | |
h | v |
daher: X≅Z
→ Z¬≅Y
weiteres Beispiel zur Isomorphie:
Bei isomorphen Graphen gilt, dass für alle Verknüpfungen der Urbildmenge auch die Verknüpfungen der Bildmenge dasselbe Ergebnis ergeben.
3.2.1 Notwendige Bedingungen für Isomorphismus
- Anzahl Kanten gleich
- Anzahl Knoten gleich
- gleicher Knotengrad
Diese Bedingungen sind notwendig, aber noch nicht hinreichend für einen Isomorphismus.
3.2.2 Algrorithmus für Feststellung von Isomorphismus
- beginnend bei einem, aufgrund seines Knotengrades, eindeutigen Knoten, abbilden
- fortsetzend, unter Einhaltung der Nachbarschaftsbeziehung, abbilden
- Lösung von Isomorphismus mit kurzen Stichworten beschreiben
- wenn ein Graph x nicht isomorph mit einem von 2 miteinander isomorphen Graphen ist, so kann er es auch nicht mit dem 2. Graphen sein
3.2.3 Adjazenzmatrix A(x) (Nachbarschaftsmatrix)
wenn der Knoten i mit dem Knoten j über eine Kante verbunden ist, dann erfolgt der Eintrag 1 ansonst 0.
Bei der Adjazenzmatrix-Darstellung werden die Knoten als Indexwerte einer 2-dimensionalen Matrix A aufgefasst.
Wenn der Knoten v adjazent zum Knoten w ist, wird das Feld A[v,w] in der Matrix gesetzt (z.B. 1 als „true-Wert“, etc.).
Die Adjazenzmatrix ist:
- gut für kleine Graphen oder Graphen mit vielen Kanten
- gut für die Überprüfung von Adjazenzeigenschaft
- dfs schlecht, Rechenaufwand O(|V|2)
- quadratischer Speicheraufwand O(|V|2)
3.2.4 Verschiedene Matrizenformen und deren Bedeutung
Hauptdiagonale 0 – Graph weist keine Schlingen auf
Hauptdiagonale 1 – von einem Knoten kommt man über eine spezielle Kante wieder auf den selben Knoten
Symetrische Matrix – wenn die Matrix über die Hauptdiagonale gespiegelt werden kann, handelt es sich um einen ungerichteten Graphen
Asymetrische Matrix – es liegt ein gerichteter Graph vor
3.2.5 Anordnung und Prüfung auf Isomorphismus zweier Matrizen
- ordnen beider Matrizen nach Knotengrad der Knoten, höchste Knotengrade zuerst
- prüfen ob Isomorphismus nachgewiesen werden kann und ausgeben wenn Isomorphismus besteht
- vertauschen der Indizes (gleichweiser Spalten- u. Zeilentausch) der 2. Matrix innerhalb der Knotengrade
- inklusive der letzten möglichen Vertauschung, weiter bei Pkt. 2, ansonst ENDE
|
|
Der Index der Matrix A(z) wird nun solange vertauxcht, bis alle Möglichkeiten ausgeschöpft sind.
A2(z) | M | N | O | P | Q | R |
M | 0 | 0 | 0 | 1 | 0 | 0 |
N | 0 | 0 | 0 | 1 | 1 | 0 |
O | 0 | 0 | 0 | 1 | 0 | 0 |
P | 1 | 1 | 1 | 0 | 0 | 0 |
Q | 0 | 1 | 0 | 0 | 0 | 1 |
R | 0 | 0 | 0 | 0 | 1 | 0 |
3.2.6 Mehrfach-ISOMORPHISMUS
Mehrfach-Isomorphismus liegt dann vor, wenn mehrere Graphen
eindeutig umkehrbar abbildbar sind.
Die beiden Graphen scheinen sehr unterschiedlich zu sein,
dennoch sind sie im Sinne der Graphentheorie strukturgleich. Man kann bijektive
Abb. der Eckenmenge angegeben, die die Inzidenzbeziehungen
respektiert. Man spricht von isomorphen Graphen. Das top. Bild eines top.
Graphen führt stets zu einem isomorphen Graphen.