Isomorphe Adjazenzmatrizen

Um die Isomorphie von Graphen zu zeigen, kann man die Adjazenzmatrizen (Verknüpfungstabellen) vergleichen. Sind diese identisch, so sind die Graphen isomorph.

Manchmal kann man aber auch zwei Tabellen, die auf den ersten Blick nicht identisch erscheinen durch das Vertauschen von Zeilen und Spalten so umwandeln, dass sie schließlich doch gleich sind.

Isomorphe Sechsecke

Zeilen- und Spaltentausch

Adjazenzmatrizen:

ABCDEF
A010101
B101010
C010101
D101010
E010101
F101010
KLMNQP
K000111
L000111
M000111
N111000
Q111000
P111000

Hier sind in beiden Tabellen in jeder Spalte und in jeder Zeile genau dreimal „1“ und dreimal „0“ vorhanden, auf der Diagonale stehen nur Nullen.

Vertauscht man die Zeilen und Spalten von B und E, so erhält man exakt die rechte Matrix. Ein Tausch muss immer sowohl Zeilen als auch die entsprechenden Spalten tauschen - wird nur eines von beiden getauscht, so ändert sich die Aussage der Adjazenzmatrix.

ABCDEF
A010101
B101010
C010101
D101010
E010101
F101010

~~leftright~~

Spalten B und E getauscht

AECDBF
A000111
B111000
C000111
D111000
E000111
F111000

~~leftright~~

AECDBF
A000111
B111000
C000111
D111000
E000111
F111000

~~leftright~~

Zeilen B und E getauscht

AECDBF
A000111
E000111
C000111
D111000
B111000
F111000

Charakteristisches Polynom

Man kann die Isomorphie auch durch das Berechnen des charakteristischen Polynoms der Adjazenzmatrix zeigen - nur bei identischen Polynomen sind die Verknüpfungstabellen gleich, die ursprünglichen Graphen also ismorph.

Da die Berechnung bei größeren Tabellen schnell etwas umfangreich werden kann, ist es hilfreich, dass z.B. Derive das charakteristische Polynom einer Matrix mit dem Befehl charpoly(A) bestimmen kann, wobei A die zu untersuchende Matrix ist.

Das charakteristische Polynom beider Matrizen ist w^6 - 9w^4, also sind die Graphen isomorph.

Berechnung von Hand

Die Berechnung des charakteristischen Polynoms ist nicht schwierig, nur umso aufwändiger, je größer die Matrix ist.

Man folgt einem eindeutigem Algorithmus, daher kann die Berechnung auch leicht ein programmierter Computer übernehmen:

  1. auf der Hauptdiagonale wird „-w“ ergänzt,
  2. die Determinante der ergänzten Matrix wird berechnet.

Determinante

Die Determinante einer 2×2-Matrix berechnet man, indem man das Produkt der Elemente der Hauptdiagonale bildet und davon das Produkt der Elemente der Nebendiagonale subtrahiert.

delim{|}{matrix{2}{2}{a b c d}}{|} ~=~ ad ~-~ bc

Bei größeren Matrizen denkt man sich in der ersten Spalte ein +-+-+-… Muster und bildet dann eine Summe von Subdeterminanten, die jeweils mit dem Element der oberen Zeile multipliziert werden. In der Subdeterminante stehen dann alle Elemente, die nicht in der oberen Zeile und nicht in der Spalte des gerade betrachteten Elementes stehen.

Ist die Subdeterminante zweireihig, kann man im nächsten Schritt die Determinante bestimmen - ist die Subdeterminante größer, werden davon wieder Summen von Subdeterminanten gebildet.

delim{|}{matrix{3}{3}{a b c d e f g h j}}{|} ~=~ a~delim{|}{matrix{2}{2}{e f h j}}{|} ~-~b~delim{|}{matrix{2}{2}{d f g j}}{|} ~+~ c~delim{|}{matrix{2}{2}{d e g h}}{|}

delim{|}{matrix{4}{4}{a b c d e f g h j k l m}}{|} ~=~ a~delim{|}{matrix{3}{3}{f g h k l m}}{|} ~-~b~delim{|}{matrix{3}{3}{e g h j l m}}{|} ~+~c~delim{|}{matrix{3}{3}{e f h j k m}}{|} ~-~d~delim{|}{matrix{3}{3}{e f g j k l}}{|}

Charakteristisches Polynom im Beispiel

Beispiel 1

1. Schritt: ~~matrix{2}{2}{0 1 1 1} ~~~~right~~~~ matrix{2}{2}{0-w 1 1 1-w}

2. Schritt: ~~delim{|}{matrix{2}{2}{0-w 1 1 1-w}}{|} ~=~ (0-w)(1-w)~-~1~*~1 ~=~ -w(1-w)~-~1 ~=~ w^2~-~w~-~1

Beispiel 2
schule/graphen/isomorph.txt · Zuletzt geändert: 2018/06/09 15:30 von ahrens
CC Attribution-Noncommercial-Share Alike 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0