Adjazenzmatrix

Beispiel: Adjazenzmatrix für ungerichteten Graphen

Es gibt einen ungerichteten Graphen mit 3 Knoten A, B und C (das könnten Städte sein).

A ist mit B und mit C verbunden (zum Beispiel durch eine Bahnstrecke).

Ungerichtet bedeutet, die Knoten / Städte sind mit Kanten verbunden, nicht mit Pfeilen (das hieße gerichteter Graph).

Das heißt, man kann von A nach B fahren und von B nach A, während bei einem gerichteten Graphen die Verbindung nur in Pfeilrichtung befahrbar ist (zum Beispiel nur von A nach B, nicht aber von B nach A).

In dem Graphen kann man die Knoten und die Verbindungen zwischen ihnen schön sehen:

Ein Computer kann aber schlecht sehen, deshalb überführt man die Informationen in eine Matrix.

Dabei wird als Element in die Matrix eine 1 eingetragen, wenn zwischen 2 Knoten eine Verbindung besteht und 0, wenn nicht:

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

Die 3 Zeilen stellen dabei jeweils von oben nach unten die Städte A, B und C dar, die 3 Spalten ebenso von links nach rechts.

Lesebeispiel:

Das zweite, mittlere Element "1" in der ersten Zeile bedeutet, dass von A nach B eine Kante / Verbindung besteht.

Das dritte, letzte Element "0" in der zweiten Zeile bedeutet, dass von B nach C keine Kante / Verbindung besteht.

Beispiel: Adjazenzmatrix 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 A:

In der Adjazenzmatrix werden dann nur ausgehende Pfeile mit einer "1" abgebildet:

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