Aufgabe 43:
Wir definieren die folgenden drei Graphen:
$$ \begin{array}{l} {V\left(G_{1}\right):=\left\{P_{1}, P_{2}, P_{3}, P_{4}, P_{5}\right\}} \\ {E\left(G_{1}\right):=\left\{\left(P_{1}, P_{2}\right),\left(P_{2}, P_{3}\right),\left(P_{3}, P_{4}\right),\left(P_{4}, P_{5}\right),\left(P_{5}, P_{1}\right)\right\}} \\ {V\left(G_{2}\right):=\left\{P_{1}, P_{2}, P_{3}\right\}} \\ {E\left(G_{2}\right):=\left\{\left(P_{1}, P_{2}\right),\left(P_{1}, P_{3}\right)\right\}} \\ {V\left(G_{3}\right):=\left\{P_{1}, P_{2}, P_{3}\right\}} \\ {E\left(G_{3}\right):=\left\{\left(P_{1}, P_{2}\right),\left(P_{2}, P_{3}\right)\right\}} \end{array} $$
a) Geben Sie die drei Nachbarschaftsmatrizen der obigen Graphen an.
b) Die Graphen \( G_{2} \) und \( G_{3} \) sind isomorph. Geben Sie einen Isomorphismus an.
c) Erläutern Sie wie man anhand der Nachbarschaftsmatrizen von \( G_{2} \) und \( G_{3} \) hätte sehen können, dass \( G_{2} \) und \( G_{3} \) isomorph sind.
Hinweis: Was hat das Vertauschen von Punkten der Graphen mit dem Vertauschen von Zeilen bzw. Spalten der Matrizen zu tun?
Aufgabe 44:
Gegeben seien folgende beiden Matrizen:
$$ M_{1}:=\left(\begin{array}{llll} {0} & {1} & {1} & {1} \\ {1} & {0} & {1} & {1} \\ {1} & {1} & {0} & {1} \\ {1} & {1} & {1} & {0} \end{array}\right), M_{2}:=\left(\begin{array}{llll} {0} & {1} & {0} & {1} \\ {1} & {0} & {1} & {0} \\ {0} & {1} & {0} & {1} \\ {1} & {0} & {1} & {0} \end{array}\right) $$
a) Zeichnen Sie die beiden Graphen mit den Nachbarschaftsmatrizen \( M_{1} \) bzw. \( M_{2} \)
-Sei nun \( G \) ein Graph mit Nachbarschaftsmatrix \( M . \) Ferner seien \( v, w \in V(G) \) und \( k \in \mathbb{N} \)
b) Wie können Sie mit Hilfe von \( M \) bestimmen ob es einen Weg der länge kleiner gleich \( k \) bzw. gleich \( k \) von \( v \) nach \( w \) gibt?
c) Wie können Sie \( d(v) \) mit Hilfe von \( M \) bestimmen?
