Operations Research

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?

Inzidenzmatrix: Geeignet für Graphen mit vielen Knoten und wenig Kanten
direkt ins Video springen
Inzidenzmatrix: Beziehung zwischen Knoten und Kanten

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.

Formale Schreibweise der Inzidenzmatrix

Ist V die Menge der Knoten und E die Menge der Kanten , so kann die Inzidenzmatrix B formal folgendermaßen dargestellt werden:

Inzidenzmatrix formal formuliert
direkt ins Video springen
Formale Schreibweise der Inzidenzmatrix

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:

Inzidenzmatrix: ungerichteter Graph
direkt ins Video springen
Inzidenzmatrix bei ungerichteten Graphen

Jede Kante verbindet immer genau zwei Knoten. Daher muss die Summe jeder Spalte 2 ergeben.

Beispiel Inzidenzmatrix: Gerichteter Graph

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:

Inzidenzmatrix: gerichtete Graphen
direkt ins Video springen
Inzidenzmatrix bei gerichteten Graphen

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.

Von der Inzidenzmatrix zum gerichteten Graphen
direkt ins Video springen
Inzidenzmatrix in Graphen umwandeln

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:

Graphen in Inzidenzlisten speichern
direkt ins Video springen
Speicherung in Inzidenzlisten

Nun weißt du, wie kinderleicht man Graphen mit einer Inzidenzliste oder einer Inzidenzmatrix darstellen kann. Super!

Hallo, leider nutzt du einen AdBlocker.

Auf Studyflix bieten wir dir kostenlos hochwertige Bildung an. Dies können wir nur durch die Unterstützung unserer Werbepartner tun.

Schalte bitte deinen Adblocker für Studyflix aus oder füge uns zu deinen Ausnahmen hinzu. Das tut dir nicht weh und hilft uns weiter.

Danke!
Dein Studyflix-Team

Wenn du nicht weißt, wie du deinen Adblocker deaktivierst oder Studyflix zu den Ausnahmen hinzufügst, findest du hier eine kurze Anleitung. Bitte lade anschließend die Seite neu.