Repräsentation von Graphen im Computer

Inhaltsverzeichnis

1 Einleitung 2 Adjazenzmatrix 3 Inzidenzmatrix 4 Adjazenzliste 5 vergleichende Betrachtungen

Einleitung

Für die Repräsentation von Graphen im Computer gibt es im Wesentlichen zwei gebräuchliche die Adjazenzmatrix und die Adjazenzliste . Alternative Bezeichnungen sind Nachbarschaftsmatrix und Nachbarschaftsliste . Die Bedeutung der beiden Begriffe liegt dass praktisch jede algorithmische Lösung graphentheoretischer Probleme wenigstens eine der beiden Repräsentationen zurückgreift. Eine aber seltener genutzte Möglichkeit zur Darstellung von im Computer ist die Inzidenzmatrix die man auch als Knoten-Kanten-Matrix bezeichnet.

Adjazenzmatrix

Ein Graph mit n Knoten kann durch eine n × n - Matrix repräsentiert werden. Dazu nummeriert man die von 1 bis n durch und trägt in die Matrix 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 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. 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 Die Matrix ist genau dann symmetrisch wenn der Graph ist und ihre Hauptdiagonale enthält Nullen wenn der Graph schleifenfrei ist. Dies ist genau der Grund man gerichtete Graphen die symmetrisch und schleifenfrei auch ungerichtet nennt. Ihre Adjazenzmatrix ist dann nämlich zu der eines ungerichteten Graphen und diese ein Spezialfall der gerichteten Graphen.

In Graphen mit Mehrfachkanten trägt man in die (i)-te Zeile j -te Spalte die Vielfachheit von { i j } in ungerichteten Graphen bzw. ( i j ) in gerichteten Graphen ein. Auch an Stelle sieht man leicht warum Graphen ohne als Spezialfälle von Graphen mit Mehrfachkanten betrachtet können.

In kantengewichteten Graphen trägt man häufig auch das Kantengewicht jeweiligen Kante ein wobei in Abhängigkeit des Problems Knoten die nicht durch eine Kante sind mit 0 oder ∞ markiert werden.

Hypergraphen lassen sich nicht durch eine Adjazenzmatrix

Inzidenzmatrix

Ein Graph mit n Knoten und m Kanten kann auch durch eine n × m - Matrix repräsentiert werden. Dazu nummeriert man die von 1 bis n und die Kanten von 1 bis m durch und trägt in die Matrix Beziehungen der Knoten zu den Kanten ein.

Adjazenzliste

Die Adjazenzliste wird in ihrer einfachsten durch eine einfach verkettete Liste aller Knoten des Graphen dargestellt wobei Knoten eine Liste aller seiner Nachbarn (in ungerichteten Graphen) bzw. Nachfolger in gerichteten Graphen besitzt. Vielfachheiten der Knotengewichte und Kantengewichte werden meist in Attributen der einzelnen gespeichert. Je nach Problemstellung kann es notwendig statt einer einfach verketteten Liste eine doppelt verkettete Liste zu verwenden und in gerichteten Graphen zur Liste der Nachfolger eine Liste der zu verwalten.

vergleichende Betrachtungen

Adjazenzlisten sind zwar aufwändiger zu implementieren zu verwalten bieten aber eine Reihe von gegenüber Adjazenzmatritzen. Zum einen verbrauchen sie stets linear viel Speicherplatz was insbesondere bei dünnen (also Graphen mit wenig Kanten) von Vorteil während die Adjazenzmatrix quadratischen Platzbedarf bezüglich der Knoten besitzt (dafür aber kompakter bei dichten also Graphen mit vielen Kanten ist). Zum lassen sich viele graphentheoretische Probleme nur mit in linearer Zeit lösen. In der Praxis man daher meist diese Form der Repräsentation.

Bücher zum Thema Repräsentation von Graphen im Computer

Dieser Artikel von Wikipedia unterliegt der GNU FDL.