Du weißt einfach nicht wie du darstellen sollst, zwischen welchen Knoten Kanten existieren und dann auch noch zu welchen Kosten? Das erklären wir dir jetzt!
Das Wort Adjazenz bedeutet so viel wie Nachbarschaft. Es geht also um die Beziehung der Knoten eines Graphen zueinander.
Bei der Adjazenzmatrix handelt es sich um eine Matrix, aus der du ablesen kannst, ob du von einem Knoten
zu einem anderen Knoten gehen kannst und welche Kosten
damit verbunden sind. N ist hierbei die Anzahl der Knoten, die der Graph enthält.
Stell dir vor du weißt von einem Graphen nur, dass er aus den Knoten A, B, C und D besteht. Doch woher willst du jetzt wissen, ob du von Knoten A zu Knoten D gehen darfst? Richtig, aus der Adjazenzmatrix. Zum Verständnis: diese Matrix hat denselben Informationsgehalt wie dieser einfache Graph:
Falls dir die Grundlagen der Graphentheorie nicht bekannt sind, solltest du dir zuerst unser Video anschauen, in dem wir dir die Basics erklären!
Eine 1 in einer Zelle bedeutet hier, dass eine Kante zwischen zwei Knoten existiert. Eine 0 bedeutet, dass zwei Knoten nicht miteinander verbunden sind. Die Matrix ist bei einem ungerichteten Graph ober und unterhalb der Diagonale symmetrisch, da beispielsweise die Kante von A nach B auch in die andere Richtung benutzt werden kann.
Da bei der Adjazenzmatrix die Anzahl der Kanten keine Rolle für die Größe der Matrix spielt, eignet sie sich anders als die Inzidenzmatrix für Graphen mit vielen Kanten.
Achtung: Bei einem gewichteten Graphen wird anstatt Einsen das jeweilige Gewicht der Kante in die Matrix geschrieben!
Schauen wir uns das an einem gerichteten Graphen mit Kantengewichten an.
Zuerst erstellen wir uns eine leere Matrix für alle Knoten. Wir sehen, dass kein Knoten eine Kante zu sich selbst hat, also können wir in die jeweiligen Zellen eine 0 eintragen.
Beginnen wir jetzt bei Knoten A. Wir sehen, dass von A zu B eine Kante mit einem Kantengewicht von 25 verläuft. Dieses Kantengewicht tragen wir in die zugehörige Zelle. Anders herum verläuft keine Kante vom Knoten B zu A, also können wir in diese Zelle eine 0 eintragen.
Wiederholen wir das für alle Knoten, erhalten wir dieses Ergebnis:
Zum Schluss schauen wir uns noch kurz Adjazenzlisten an. Hierbei werden einfach für jeden Knoten beim ungerichteten Graphen alle Nachbarn und beim gerichteten Graphen alle Nachfolger in einer Liste gespeichert. Versuchen wir das für einen einfachen Graphen.
Wir schreiben uns für jeden Knoten eine Liste mit seinen Nachbarn. Knoten A ist beispielsweise mit den Knoten B und C verbunden. Das schreiben wir uns auf.
Wiederholen wir das für alle Knoten erhalten wir unsere Liste.
Wie du siehst ist diese Liste auf einen Blick deutlich einfacher zu lesen als die Matrix. Speziell im Bereich der Informatik muss aber beachtet werden, dass sie
Perfekt! Jetzt weißt du, wie du in Zukunft Graphen sinnvoll und einheitlich darstellen kannst.
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.