Inzidenzmatrix

Definition

Eine Inzidenzmatrix ist eine Matrix bzw. Tabelle, die

in den Zeilen die Knoten eines Graphen (zum Beispiel Städte) und
in den Spalten die Kanten bzw. Pfeile (zum Beispiel 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.

Beispiele

Beispiel 1: 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.

$$\begin{array}{c c}
& \begin{array}{c c} 1 & 2 \\ \end{array} \\
\begin{array}{c c c} A \\ B \\ C \end{array} &
\left( \begin{array}{cc} 1&0 \\ 1&1 \\ 0&1 \end{array} \right) \end{array}$$

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 2: 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):

$$\begin{array}{c c}
& \begin{array}{c c} 1 & 2 \\ \end{array} \\
\begin{array}{c c c} A \\ B \\ C \end{array} &
\left( \begin{array}{cc} 1&0 \\ -1&-1 \\ 0&1 \end{array} \right) \end{array}$$

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.