Adjazenzmatrix

Beschreibung

Die Adjazenzmatrix ist ein definierendes Element eines Untershift endlichen Typs. Es handelt sich um eine $n\times n$-Matrix, die aus $0$ und $1$ besteht. Sie ist zugleich eine Adjazenzmatrix eines Graphen

Die Adjazenzmatrix wird genutzt, um eine Markov-Zerlegung graphentheoretisch zu untersuchen.

Konstruktion durch Markow-Zerlegung

Sei $(X,f)$ ein Dynamisches System, sei $\mathcal{P}=\{P_0,...\}$ eine Markow-Zerlegung. D.h. das Bild jedes Elements $P_i$ ist eine Vereinigung von anderen Elementen: $f(P_i)=P_{j_1}\cup P_{j_2}\cup ...$ Wir bilden daraus einen Graphen bzw. Adjazenzmatrix, indem wir eine gerichtete Kante (mit Wert 1) zwischen den Knoten $j_1,j_2,...$ und $i$ setzen. Alle anderen Felder der Adjazenzmatrix werden mit dem Wert $0$ besetzt.

Eigenschaften

Potenz von Adjazenzmatrizen.

Sei $A$ eine Adjazenzmatrix mit Werten $\{0,1\}$. Der Wert $a_{ij}$ besagt, ob es einen Pfad zwischen $i$ und $j$ gibt. Betrachte nun $A^2$. Die Einträge sind von der Form $\sum a_{ik}{a}_{kj}$. Sie zählen alle Pfade von Länge $2$ zwischen $i$ und $j$ (über einen Knoten $k$) auf. Analog gibt $(A^n{)}_{ij}$ an, wie viele Pfade von Länge $n$ es zwischen dem Knoten $i$ und $j$ gibt.