Repräsentation von Graphen im Computer
| Table of contents |
|
2 Adjazenzmatrix 3 Adjazenzliste 4 Beispiele 5 vergleichende Betrachtungen |
Für die Repräsentation von Graphen im Computer gibt es im Wesentlichen zwei gebräuchliche Formen, die Adjazenzmatrix und die Adjazenzliste. Alternative Bezeichnungen sind Nachbarschaftsmatrix und Nachbarschaftsliste. Die Bedeutung der beiden Begriffe liegt darin, dass praktisch jede algorithmische Lösung graphentheoretischer Probleme auf wenigstens eine der beiden Repräsentationen zurückgreift.
Ein Graph mit n Knoten kann durch eine n×n-Matrix repräsentiert werden. Dazu nummeriert man die Knoten von 1 bis n durch und trägt in die Matrix die Beziehungen der Knoten zueinander ein.
In ungerichteten Graphen ohne Mehrfachkanten wird in die i-te Zeile und j-te Spalte eine 1 eingetragen, wenn der i-te und j-te Knoten benachbart, d.h. durch eine Kante verbunden sind. Andernfalls wird eine 0 eingetragen. Da die Relation "benachbart" symmetrisch ist (wenn Knoten i mit Knoten j benachbart ist, dann ist auch Knoten j mit Knoten i benachbart), ist auch die Adjazenzmatrix symmetrisch. Da ungerichtete Graphen keine Schleifen besitzen steht in der Hauptdiagonalen der Matrix überall die 0.
In gerichteten Graphen ohne Mehrfachkanten wird in die i-te Zeile und j-te Spalte eine 1 eingetragen, wenn der i-te Knoten Vorgänger des j-ten Knoten ist. Andernfalls wird eine 0 eingetragen. Die Matrix ist genau dann symmetrisch, wenn es der Graph ist und ihre Hauptdiagonale enthält nur Nullen, wenn der Graph schleifenfrei ist. Dies ist genau der Grund, warum man gerichtete Graphen die symmetrisch und schleifenfrei sind auch ungerichtet nennt. Ihre Adjazenzmatrix ist dann nämlich äquivalent zu der eines ungerichteten Graphen und diese sind ein Spezialfall der gerichteten Graphen.
In Graphen mit Mehrfachkanten trägt man in die (i)-te Zeile und j-te Spalte die Vielfachheit von {i,j} in ungerichteten Graphen bzw. (i,j) in gerichteten Graphen ein. Auch an dieser Stelle sieht man leicht, warum Graphen ohne Mehrfachkanten als Spezialfälle von Graphen mit Mehrfachkanten betrachtet werden können.
In kantengewichteten Graphen trägt man häufig auch das Kantengewicht der jeweiligen Kante ein, wobei in Abhängigkeit des betrachteten Problems Knoten die nicht durch eine Kante verbunden sind mit 0 oder ∞ markiert werden.
Hypergraphen lassen sich nicht durch eine Adjazenzmatrix darstellen.
Die Adjazenzliste wird in ihrer einfachsten Form durch eine einfach verkettete Liste aller Knoten des Graphen dargestellt, wobei jeder Knoten eine Liste aller seiner Nachbarn (in ungerichteten Graphen) bzw. Nachfolger in gerichteten Graphen besitzt. Vielfachheiten der Kanten Knotengewichte, und Kantengewichte werden meist in Attributen der einzelnen Elemente gespeichert. Je nach Problemstellung kann es notwendig sein, statt einer einfach verketteten Liste eine doppelt verkettete Liste zu verwenden und in gerichteten Graphen zusätzlich zur Liste der Nachfolger eine Liste der Vorgänger zu verwalten.Einleitung
Adjazenzmatrix
Adjazenzliste
