Adjazenzmatrix & Features
Zur Definition der Adjazenzmatrix $A_G$ eines Graphen $G = (V,E)$ verweisen wir vorweg auf GraphenIntro. Wenn man das quadratische Speicherschema Adjazenzmatrix als Matrix interpretiert, erhält man aus den Potenzen von $A_G$ Matrizenmultiplikation, sprich aus den Matrizen
\[ A_G^0 = I, ~ A_G^1 = A_G, ~ A_G^2 = A_G \cdot A_G, ~ A_G^3 = A_G^2 \cdot A_G, ~ \ldots \]
detailliertere Informationen über die Struktur von $G$.
Behauptung/Aussage
Für jedes gibt der $i,j$-te Eintrag von $A_G^r$ die Anzahl der $(i,j)$-Wege/Pfade der Länge $r$ an. Ein $(i,j)$-Weg/Pfad der Länge $r$ ist eine Folge von Knoten $v_0, v_1, \ldots, v_r \in V$, wobei für alle $k \in {0, \ldots, r - 1}: ~ v_k E v_{k + 1}$.
Beweis
Einen Beweis der obigen Aussage erhält man durch vollständige Induktion über $r \in \mathbb{N}_0$. Der Induktionsanfang $r = 0$ ist dabei offensichtlich, da $A_G^0 = I$ (Einheitsmatrix der Dimension $|V|$) gilt und es für jeden Knoten $i \in V$ genau einen $(i,i)$-Weg der Länge $0$ gibt und keinen $(i,j)$-Weg der Länge $0$, falls $i \neq j$. Sei also nun die Aussage für $r \in \mathbb{N}_0$ bereits bewiesen. Nach Definition gilt
\[ (A_G^{r+1})_{i,j} = \sum_{k = 1}^{|V|} (A_G^r)_{i,k} (A_G)_{k,j}. \]
Wenn wir gemäß Julius Plücker “in den Gleichungen lesen” ergibt sich nach obiger Formel der $i,j$-te Eintrag von $A_G^{r + 1}$ wie folgt: Nach Induktionsannahme entspricht der Anzahl von $(i,k)$-Wegen der Länge $r$. Steht also in eine $1$, so wird in der obigen Summe diese Zahl mit aufsummiert. In diesem Fall gibt es aber genau $(i,j)$-Wege der Länge $r + 1$, so dass $k$ der vorletzte Knoten im Weg ist. Sofern gilt, gibt es keinen $(i,j)$-Weg der Länge $r + 1$, so dass $k$ der vorletzte Knoten des Weges ist, weshalb $(A_G^r)_{i,k}$ in diesem Fall in der Summe nicht berücksichtigt wird. Da die Summation über alle möglichen “vorletzten” Knoten $k$ läuft, ist die Aussage damit bewiesen.
Features & Applet
Wie die obige Aussage zeigt, kann man mittels der Adjazenzmatrix $A_G$ verschiede Features von $G$ detektieren:
- Existenz/Anzahl von $(i,j)$-Wegen der Länge $r \in \mathbb{N}_0$ (Einträge von $A_G^r$)
- Existenz/Anzahl von $(i,j)$-Wegen mit einer Maximallänge (Einträge von $\sum_{k = 0}^r A_G^k$)
- Zusammenhang (Existiert ein Nulleintrag in $\sum_{k = 0}^{|E|} A_G^k$ ?)
- Dreiecke (Suche Indexpaar $(i,j)$ mit $(A_G)_{i,j} = 1$ und $(A_G^2)_{i,j} > 0$ .)
- etc.
Im nachfolgenden Applet kann man einen beliebigen ungerichteten bzw. gerichteten Graphen graphisch eingeben/manipulieren. Zeitgleich dazu werden die Matrizen $A_G^r$ (obere Matrix) bzw. $\sum_{k = 0}^r A_G^k$ (untere Matrix) ausgegeben.
Zur Bedienung des Applets:
- Analog zum Applet auf Was ist ein Graph?.
- Über den weiß/grauen Slider kann man $r \in {0, \ldots, |E|}$ einstellen.
GraphMatrix.cdy (Dieses Applet kann in Cinderella ausgeführt werden.)