====== 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. {{ :schule:graphen:sechseck.jpg?nolink |Isomorphe Sechsecke}} ===== Zeilen- und Spaltentausch ===== **Adjazenzmatrizen:** | ^A^B^C^D^E^F^ ^A|0|1|0|1|0|1| ^B|1|0|1|0|1|0| ^C|0|1|0|1|0|1| ^D|1|0|1|0|1|0| ^E|0|1|0|1|0|1| ^F|1|0|1|0|1|0| | ^K^L^M^N^Q^P^ ^K|0|0|0|1|1|1| ^L|0|0|0|1|1|1| ^M|0|0|0|1|1|1| ^N|1|1|1|0|0|0| ^Q|1|1|1|0|0|0| ^P|1|1|1|0|0|0| 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. | ^A^**B**^C^D^**E**^F^ ^A|0|**1**|0|1|**0**|1| ^B|1|**0**|1|0|**1**|0| ^C|0|**1**|0|1|**0**|1| ^D|1|**0**|1|0|**1**|0| ^E|0|**1**|0|1|**0**|1| ^F|1|**0**|1|0|**1**|0| ~~leftright~~ Spalten B und E getauscht | ^A^**E**^C^D^**B**^F^ ^A|0|**0**|0|1|**1**|1| ^B|1|**1**|1|0|**0**|0| ^C|0|**0**|0|1|**1**|1| ^D|1|**1**|1|0|**0**|0| ^E|0|**0**|0|1|**1**|1| ^F|1|**1**|1|0|**0**|0| ~~leftright~~ | ^A^E^C^D^B^F^ ^A|0|0|0|1|1|1| ^**B**|**1**|**1**|**1**|**0**|**0**|**0**| ^C|0|0|0|1|1|1| ^D|1|1|1|0|0|0| ^**E**|**0**|**0**|**0**|**1**|**1**|**1**| ^F|1|1|1|0|0|0| ~~leftright~~ Zeilen B und E getauscht | ^A^E^C^D^B^F^ ^A|0|0|0|1|1|1| ^**E**|**0**|**0**|**0**|**1**|**1**|**1**| ^C|0|0|0|1|1|1| ^D|1|1|1|0|0|0| ^**B**|**1**|**1**|**1**|**0**|**0**|**0**| ^F|1|1|1|0|0|0| ===== 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: - auf der Hauptdiagonale wird "-w" ergänzt, - die Determinante der ergänzten Matrix wird berechnet. === Determinante === Die Determinante einer 2x2-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 == 1. Schritt: ~~matrix{4}{4}{1 1 1 0 1 0 0 1 1 0 1 0 0 1 0 0} ~~~~right~~~~ matrix{4}{4}{1-w 1 1 0 1 0-w 0 1 1 0 1-w 0 0 1 0 0-w} 2. Schritt: ~~delim{|}{matrix{4}{4}{1-w 1 1 0 1 0-w 0 1 1 0 1-w 0 0 1 0 0-w}}{|} ~=~ (1-w)delim{|}{matrix{3}{3}{0-w 0 1 0 1-w 0 1 0 0-w}}{|} ~-~1~*~delim{|}{matrix{3}{3}{1 0 1 1 1-w 0 0 0 0-w}}{|} ~+~1~*~delim{|}{matrix{3}{3}{1 0-w 1 1 0 0 0 1 0-w}}{|} ~-~0~*~delim{|}{matrix{3}{3}{1 0-w 0 1 0 1-w 0 1 0}}{|} ~=~ (1-w)(-w~delim{|}{matrix{2}{2}{1-w 0 0 0 - w}}{|} ~-~0~+~delim{|}{matrix{2}{2}{0 1 - w 1 0}}{|}) ~-~(delim{|}{matrix{2}{2}{1-w 0 0 0-w}}{|} ~-~0~+~delim{|}{matrix{2}{2}{1 1-w 0 0 }}{|}) ~~~~~+~(delim{|}{matrix{2}{2}{0 0 1 0 - w}}{|} ~-~(- w)~ delim{|}{matrix{2}{2}{1 0 0 0-w}}{|} ~+~ delim{|}{matrix{2}{2}{1 0 0 1}}{|}) ~=~(1 - w)(- w(1 - w)(- w) ~+~ 0 -(1 - w))~-~((1 - w)(- w) +0) ~+~(0 ~-~(- w)(- w)~+~1) ~=~(1 - w)(w^2 - w^3 -~1~ +~ w)~-~(- w ~+~ w^2) ~+~(- w^2 + ~1) ~=~w^2 - w^3 -~1~ +~ w~ -w^3+w^4 +~w~ -~ w^2 ~+~w ~- w^2 - w^2+~1 ~=~w^4~-~2w^3~-~2w^2~+~3w {{tag>Graphentheorie Isomorphie Adjazenzmatrix charakteristisches_Polynom Determinante mathpublisher}}