Inzidenzmatrix und Inzidenzliste
Einen Graphen komplett in eine Inzidenzmatrix oder eine Inzidenzliste schreiben? Wie das geht zeigen wir dir hier!
Inhaltsübersicht
Definition der Inzidenzmatrix
Die Inzidenzmatrix eines Graphen speichert die Beziehungen zwischen Knoten und Kanten. Es wird in jeder Zelle der Matrix notiert, ob ein Knoten eine Kante berührt. Doch wie können wir das sinnvoll darstellen?
Wir benötigen eine Matrix mit so vielen Zeilen, wie der Graph Knoten, und so vielen Spalten, wie er Kanten hat. Somit eignet sich die Inzidenzmatrix, anders als die sogenannte Adjazenzmatrix , speziell für Graphen mit vielen Knoten und wenig Kanten. Liegt ein Knoten nicht an einer Kante an, dann schreiben wir in die zugehörige Zelle einfach eine 0. Ist der Graph ungerichtet, und ein Knoten liegt an einer Kante, dann schreiben wir eine 1 in die Zelle.
Beim gerichteten Graphen müssen wir entscheiden, ob der Knoten der Start oder das Ende der jeweiligen Kante ist. Beginnt eine Kante an einem Knoten, notieren wir eine 1, endet sie am Knoten schreiben wir eine minus 1 in die Zelle.
Zur Erinnerung: bei ungerichteten Graphen kann jede Kante in beide Richtungen genutzt werden – bei gerichteten Graphen hingegen ist die Richtung einer Kante festgelegt.
Beispiel Inzidenzmatrix: ungerichteter Graph
Schauen wir uns zunächst einen ungerichteten Graphen an.
Als erstes müssen wir die Knoten und Kanten durchnummerieren. In diesem Fall sind die Knoten schon mit passenden Buchstaben versehen, also sparen wir uns ein wenig Arbeit und übernehmen diese direkt.
Aber Vorsicht: die Zahlen auf den Kanten sind keine Gewichte, sondern nur die Nummerierung!
Unser Graph hat 5 Knoten und 6 Kanten. Wir erstellen uns also eine Matrix mit 5 Zeilen und 6 Spalten.
Nun beginnen wir mit dem Befüllen. Die erste Zelle stellt dar, ob der Knoten A an der Kante mit der Nummer 1 anliegt. Wir stellen fest, dass dies der Fall ist und schreiben in die erste Zelle also eine 1.
Schauen wir, wenn wir schon dabei sind, doch einfach nach, mit welchen Kanten der Knoten A noch verbunden ist. Wir sehen, dass Kante 4 ebenfalls am Knoten A anliegt, also schreiben wir eine 1 in die passende Zelle.
Nun liegen keine weiteren Kanten am Knoten. Wir können den Rest der Zeile also mit Nullen füllen.
Wenn wir das für alle Knoten und Kanten wiederholen, erhalten wir dieses Ergebnis:
Jede Kante verbindet immer genau zwei Knoten. Daher muss die Summe jeder Spalte 2 ergeben.
Beispiel Inzidenzmatrix: Gerichteter Graph [[ jump_to_video 02:58]]
Jetzt schauen wir uns den selben Graphen, nur mit gerichteten Kanten, an.
Wie bereits erklärt schreiben wir also für jeden Knoten eine 1 für ausgehende, und eine -1 für eingehende Kanten in die Matrix. Für unseren Graphen würde das also folgendermaßen aussehen:
Zum Verständnis: die Kante 1 beginnt im Knoten A und endet im Knoten B, daher schreiben wir beim Knoten A eine 1 und im Knoten B eine minus 1. Dass wir alles richtig gemacht haben erkennst du daran, dass die Summe jeder Spalte 0 ergibt. Das muss so sein, da jede Kante genau einen Startknoten, also plus 1, und einen Endknoten, also minus 1 hat.
Von der Inzidenzmatrix zum gerichteten Graphen
Wir versuchen also jetzt eine Inzidenzmatrix in den dazu passenden Graphen umzuwandeln.
Da die gerichteten Kanten immer an einem Knoten beginnen und bei einem anderen enden muss jede Spalte der Inzidenzmatrix in Summe 0 ergeben. So weit so gut.
Noch gibt es nur 4 unverbundene Knoten.
Sehen wir uns zuerst an welche Kanten Knoten A anliegen. Direkt in der ersten Zelle können wir erkennen, dass von Knoten A eine gerichtete Kante ausgeht. Wir suchen in derselben Spalte nach dem Zielknoten, und finden die minus 1 eingetragen für den Knoten D. Unsere erste Kante kann nun hinzugefügt werden.
Als nächstes sehen wir, dass Kante 2 beim Knoten B beginnt, und im Knoten A endet. Außerdem beginnt Kante 5 im Knoten C und endet ebenfalls in Knoten A. Auch diese Kante kann eingetragen werden.
Das wiederholen wir für alle Knoten und erhalten so nach und nach unseren Graphen.
Inzidenzliste
Alternativ kann die Matrix mit einer Inzidenzliste dargestellt werden. Hierbei werden für jeden Knoten genau die Knoten abgespeichert, zu denen von sich selbst aus eine Kante führt.
Von Knoten A gehen Kanten nach B und C, also speichern wir B und C in die Inzidenzliste von Knoten A. Das gleiche machen wir für die anderen Knoten und erhalten diese Listen:
Nun weißt du, wie kinderleicht man Graphen mit einer Inzidenzliste oder einer Inzidenzmatrix darstellen kann. Super!