R1 Grundlagen der Graphentheorie
Repräsentation von Graphen
Abstraktion
Grafische Darstellung und Unterschied zu Bild oder Zeichnung
Von der namensgebenden und sehr anschaulichen Möglichkeit einen Graphen grafisch darzustellen wurde in den vorhergehenden Abschnitten schon Gebrauch gemacht. Viele Algorithmen lassen sich anhand der grafischen Darstellung erklären und zumindest bei einer Handrechnung kann auch die Lösung im Graphen erfolgen.
Wichtig ist die Feststellung, dass die Abbildung eines realen Systems in einem Graphen eine Abstraktion ist. Insbesondere ist es in der grafischen Darstellung eines Graphens nicht mehr möglich Entfernungen zu messen oder trigonometrische Berechnungen anzustellen. Das unterscheidet einen Graphen von einer Landkarte oder einer maßstäblichen Zeichnung.
Es gibt aber noch andere Möglichkeiten Graphen zu repräsentieren, die kompakter und besser der automatisierten Datenverarbeitung zugänglich sind.
Betrachten wir folgende beide Graphen:
Auflistung
a.)
Eine Variante einer Auflistung ist die schon am Anfang des Kapitels eingeführte Schreibung als Menge, im Folgenden dargestellt für den ungerichteten Graphen aus Abb. 1-5a.
V={A; B; C; D; E} E={(A;C);(A;D);(A;E);(B;E);(B;D);(C;D);(C;E)}
Vorteil dieser Schreibweise ist, dass viel in eine Zeile passt, was in geschriebenen Texten natürlich vorteilhaft ist.
b.)
Die Informationen lassen sich auch in Tabellenform organisieren:
Knotenliste
| A |
| B |
| C |
| D |
| E |
Kantenliste
| A | C |
| A | D |
| A | E |
| B | E |
| B | D |
| C | D |
| C | E |
Im Falle eines zusammenhängenden Graphen reicht es aus, die Kanten aufzulisten. Schließlich ergeben sich die Knoten aus den Kanten. Anders sieht es aus, wenn es in einem Graphen isolierte Knoten gibt. Isolierte Knoten sind Konten mit denen keine Kante inzidiert. In diesem Fall besteht die Gefahr, dass Knoten „verloren gehen“ wenn nur die Kanten aufgelistet werden. Die Form der Speicherung der Knoten als Liste ist eine sehr kompakte Form und ermöglicht die automatisierte Datenverarbeitung.
Neben dieser sehr nah an der Definition des Graphen orientierten Speicherung gibt es viele weitere Möglichkeiten, die Liste zur organisieren oder mit zusätzlichen Informationen anzureichern. Ob das sinnvoll ist, hängt immer davon ab, wofür die Liste benutzt werden soll.
Beispiel
In dem gerichteten Graphen aus Abb. 1-5b soll schnell herausgefunden werden, welche Kanten an einem bestimmten Knoten enden.
In der Kantenliste könnten die Zeilen durchnummeriert werden und am Ende eine Spalte einfügt werden, die angibt, in welcher Zeile der Endknoten ebenfalls als Endknoten auftritt, man spricht auch von einem Zeiger auf die Folgeadresse. Da weiterhin Suchen notwendig wäre, um den Anfang der Verweiskette zu finden, ist es sinnvoll in der Knotenliste anzugeben, in welcher Zeile der Knoten erstmalig als Endknoten auftritt, man spricht von einer Ankeradresse.
Knotenliste mit Ankeradresse
| Knoten | Zeile |
|---|---|
| A | 7 |
| B | 6 |
| C | 1 |
| D | 2 |
| E | 3 |
Kantenliste mit Folgeadressen
| Zeilennr. | Nächste Zeile | ||
|---|---|---|---|
| 1 | A | C | - |
| 2 | A | D | 4 |
| 3 | B | E | 5 |
| 4 | C | D | - |
| 5 | C | E | - |
| 6 | D | B | 8 |
| 7 | E | A | - |
| 8 | E | B | - |
Matrixschreibweise
Es gibt aber noch eine weitere Repräsentationsform, die den Vorteil hat, dass sie die Strukturen von Graphen mathematische Operationen zugänglich macht und somit die Verbindung zu anderen Optimierungsmethoden herstellt, die Darstellung als Matrix. Für die Darstellung als Matrix wiederum gibt es zwei verbreitete Ansätze.
Inzidenzmatrix
In einer Inzidenzmatrix steht jede Zeile für einen Knoten und jede Spalte für eine Kante. Inzidiert in einem ungerichteten Graphen eine Kante mit den Knoten i und j, das heißt existiert eine Kante zwischen den Knoten i und j, wird in der Spalte die die Kante repräsentiert jeweils in Zeilen i und j eine Eins getragen.
Beispiel: Der Graph aus Abb. 1-5a
Feststellung: In jeder Spalte sind genau zwei Einsen, die restlichen Elemente sind Null. Bei gerichteten Grafen wird „1“ für den Anfangsknoten eingetragen, für den Endknoten „-1“:
Beispiel: Der Graph aus Abb. 1-5b
Feststellung: In jeder Spalte befinden sich genau eine „-1“ und eine „1“. Mittels Inzidenzmatrix können nur schlichte Graphen gespeichert werden, es gibt keine Möglichkeit Mehrfachkanten oder Schlingen abzubilden.
Die Darstellung als Inzidenzmatrix wird in den folgenden Kapiteln häufig verwendet, auf sie trifft das eingangs Gesagte, dass Matrizen die Brücke zu anderen Optimierungsmethoden schlagen, in starkem Maße zu.
Nachteil ist, dass besonders bei Graphen mit sehr vielen Knoten sehr viele Nullen gespeichert werden müssen.
Adjazenzmatrix
In einer Adjazenzmatrix repräsentieren sowohl die Zeilen als auch die Spalten die Knoten. Sind die Knoten i und j eines ungerichteten Graphen durch eine Kante verbunden, wird für das Element ij eine 1 eingetragen und ebenfalls für das Element ji. Bei ungerichteten Graphen ist die Matrix immer symmetrisch. Die übrigen Elemente sind gleich Null.
In gerichteten Graphen wird wenn von einem Knoten i zu einem Knoten j ein Pfeil existiert das Element ij auf 1 gesetzt, die übrigen Elemente sind gleich Null.
Die sich ergebende Matrix ist im Allgemeinen nicht symmetrisch.
