Inzidenzmatrix
Inzidenzmatrix Definition
Eine Inzidenzmatrix ist eine Matrix bzw. Tabelle, die in den Zeilen die Knoten eines Graphen (z. B. Städte) und in den Spalten die Kanten bzw. Pfeile (z. B. Bahnstrecken zwischen Städten) abbildet.
Man muss dann unterscheiden zwischen einem ungerichteten Graphen (die Knoten / Städte sind mit Kanten verbunden, die in beide Richtungen befahrbar sind) und gerichteten Graphen, bei denen die Verbindung nur in Pfeilrichtung befahrbar ist.
Beispiel
Beispiel: Inzidenzmatrix für ungerichteten Graphen
Es gibt einen ungerichteten Graphen mit 3 Knoten / Städten A, B und C.
A ist mit B durch eine Bahnstrecke verbunden (Kante 1) und B mit C (Kante 2).
Nun wird in die Inzidenzmatrix als Element jeweils eine 1 eingetragen, wenn der jeweilige Knoten auf der jeweiligen Kante liegt und 0, wenn nicht.
Dabei stellen die 3 Zeilen jeweils von oben nach unten die Städte A, B und C dar, die 2 Spalten stellen von links nach rechts die Kanten / Verbindungen 1 (zwischen A und B) und 2 (zwischen B und C) dar.
$$A = \left( \begin{array}{cc} 1&0 \\ 1&1 \\ 0&1 \end{array} \right)$$
Lesebeispiel:
Das erste, linke Element "1" in der ersten Zeile bedeutet, dass A auf der Kante 1 liegt, also Teil der Verbindung zwischen A und B ist.
Das erste, linke Element "0" in der dritten Zeile bedeutet, dass C nicht auf der Kante 1 liegt, also nicht Teil der Verbindung zwischen A und B ist.
Beispiel: Inzidenzmatrix für gerichteten Graphen
Ändern wir den obigen Graphen leicht so ab, dass von A ein Pfeil nach B geht und von C ein Pfeil nach B.
In der Inzidenzmatrix werden dann die Ausgangsknoten eines Pfeils mit 1 und die Endknoten mit -1 kodiert (und alles andere mit 0):
$$A = \left( \begin{array}{cc} 1&0 \\ -1&-1 \\ 0&1 \end{array} \right)$$
Lesebeispiel:
Das erste, linke Element "1" in der ersten Zeile bedeutet, dass A der Anfangsknoten der Pfeilverbindung 1 ist; das erste, linke Element "-1" in der zweiten Zeile bedeutet, dass B der Endknoten der Pfeilverbindung 1 ist.