Laufzeit und Idee für Algorithmus um zu prüfen ob zwei Adjazenmatrizen von zwei gerichteten Graphen isomorph sind.

Question

Frage: Laufzeit und Idee für Algorithmus um zu prüfen ob zwei Adjazenmatrizen von zwei gerichteten Graphen isomorph sind.

Aufgabe:

(c) \( G_{1} \) und \( G_{2} \) seien Graphen mit der Knotenmenge \( \{0,1, \ldots, n-1\} . G_{1} \) und \( G_{2} \) heißen isomorph, wenn sich die Knoten von \( G_{2} \) so umnummerieren lassen, dass die Adjazenzmatrizen der beiden Graphen übereinstimmen. Beschreiben Sie die Idee eines Algorithmus um zu prüfen, ob \( G_{1} \) und \( G_{2} \) isomorph sind. Liegt die Laufzeitkomplexität Ihres Algorithmus in \( O\left(n^{k}\right) \) mit \( k \in \mathbb{N} ? \) Begründung?

Ansatz: Ich habe mir einfach mal per Hand ein paar Sachen hingezeichnet und so denken ich einen Ansatz gefunden und zwar muss ich prüfen ob die Summe in jeder Zeile und die Summe jeder Spalte in den zwei Matrizen gleich ist. Ist die Summe ungleich sind die Matrizen nicht isomorph und wenn doch sind sie isomorph. Bin ich auf dem richtigen Weg oder bin ich ganz falsch ? Zudem ist mein Problem auch gerade das ich nicht auf die Laufzeit komme zugegeben liegt mir das Thema aber auch nicht wirklich.

Answer 1

Ein Algorithmus, der lediglich die Summen der Spalten und Zeilen betrachtet, kann nicht funktionieren. In folgendem Beispiel sind \(G_1\) und \(G_2\) nicht isomorph.

Graph \(G_1\): \(\begin{array}{ccccccc} &  &  &  & 1\\ &  &  & \diagup &  & \diagdown\\ &  & 2 &  &  &  & 3\\ & \diagup &  & \diagdown &  & \diagup\\ 4 &  &  &  & 5 \end{array}\)

Adjazenzmatrix von \(G_1\): \(\begin{pmatrix}0 & 1 & 1 & 0 & 0\\ 1 & 0 & 0 & 1 & 1\\ 1 & 0 & 0 & 0 & 1\\ 0 & 1 & 0 & 0 & 0\\ 0 & 1 & 1 & 0 & 0 \end{pmatrix}\)

Spaltensummen von \(G_1\):

Spalte:	4	1	3	5	2
Spaltensumme:	1	2	2	2	3

Graph \(G_2\): \(\begin{array}{ccccccc} &  &  &  & 1\\ &  &  & \diagup &  & \diagdown\\ &  & 2 &  &  &  & 3\\ & \diagup &  & \diagdown\\ 4 &  & - &  & 5 \end{array}\)

Adjazenzmatrix von \(G_2\): \(\begin{pmatrix}0 & 1 & 1 & 0 & 0\\ 1 & 0 & 0 & 1 & 1\\ 1 & 0 & 0 & 0 & 0\\ 0 & 1 & 0 & 0 & 1\\ 0 & 1 & 0 & 1 & 0 \end{pmatrix}\)

Spaltensummen von \(G_2\):

Spalte	3	1	4	5	2
Spaltensumme	1	2	2	2	3

Eine Möglichkeit für einen Algorithmus wäre, alle \(n!\) Permutationen zu prüfen.

Comments

Hallo, da ich mir aktuell das Thema noch einmal anschaue wollte ich mal nachfragen, der Algorithmus müsste doch demnach voraussetzten das die Spaltensummen gleich sind oder ? Also wie hier das es 1 Spaltensumme mit 1 gibt 3 Summen mit 2 und eine mit 3 oder nicht ? Oder spielt es bei dem Übereinstimmen der Adjazentmartizen nur eine Rolle was die Struktur angeht ?

---

der Algorithmus müsste doch demnach voraussetzten das die Spaltensummen gleich sind

Der Algorithmus muss nichts voraussetzen.

Also wie hier das es 1 Spaltensumme mit 1 gibt 3 Summen mit 2 und eine mit 3

Wenn zwei Graphen isomorph sind, dann stimmen die Spaltensummen der Adjazenzmatrix überein.

Das kann man verwenden um schnell Isomorphie auszuschließen. Muss man aber nicht.

Oder spielt es bei dem Übereinstimmen der Adjazentmartizen nur eine Rolle was die Struktur angeht?

Ich weiß nicht, was du genau mit "es" und "Struktur" meinst.