Adjazenzmatrix

Beispiel: Adjazenzmatrix für ungerichteten Graphen

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

A ist mit B und mit C verbunden (z. B. durch eine Bahnstrecke). Ungerichtet bedeutet, die Knoten / Städte sind mit Kanten verbunden, nicht mit Pfeilen (das hieße gerichteter Graph). Ungerichtet bedeutet, 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 (z. B 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:

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

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:

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