Beziehung (Matrixindex)

Beschreibung

Mit dem Konzept einer Beziehung ist es möglich, Stark zusammenhängende Komponenten in Graphen zu finden. Wir werden diese später nutzen, um den Graph in solche maximalen Komponenten zu zerlegen.

Definition

Sei $A$ eine nicht-negative, Quadratische Matrix. Sei $I_A$ die Indexmenge der Zeilen und Spalten. Definiere eine Relation durch $i\sim j$, wenn es $k,l>0$ mit $(A^k{)}_{ij}>0$ und $(A^l{)}_{ji}>0$ gibt. Beobachte, dass dies keine Äquivalenzrelation ist, da ein Transienter Index Index nicht notwendigerweise mit sich selbst in Relation stehen muss.

Graphentheoretische Charakterisierung

$i\sim j$ genau dann, wenn es einen Pfad von $i$ zu $j$ und von $j$ zu $i$ gibt.

Eigenschaften

Eigenschaft

lit_kitchensSymbolicDynamicsOnesided2012