0 Daumen
42 Aufrufe

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.

von

1 Antwort

0 Daumen
 
Beste Antwort

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.

von 3,3 k

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community