7. Grundlagen von Graphen¶
Gerichtete und ungerichtete Graphen¶
Wir unterscheiden (hier):
- Gerichtete Graphen
- Ungerichtete Graphen
Ein Kante ist ein (geordnetes) Paar, z.B. $(a, b)$ mit Schwanz (tail) $a$ und Kopf (head) $b$.
$$ V = \{a,b,c,d,e\} $$$$ E = \{(a,b), (b,c), (c,d), (d, a), (a,d), (a,e)\} $$Ein Kante ist ein (ungeordnetes) Paar, z.B. $\{a, b\}$.
$$ V = \{a,b,c,d,e\} $$$$ E = \{ \{a,b\}, \{b,c\}, \{c,d\}, \{d, a\}, \{a,d\}, \{a,e\}\} $$Anwendungen von Graphen (Datenstruktur und Algorithmen)¶
- Straßennetze
- World Wide Web
- Soziale Netzwerke
- Berücksichtigungen von Vorbedingungen
Quiz¶
Betrachten wir einen ungerichteten Graphen ohne parallele Kanten. Außerdem sei der Graph verbunden, d.h. alle Knoten sind über Kanten (direkt oder indirekt) verbunden.
Was ist die minimale und die mögliche maximale Anzahl von Kanten (in Abhängigkeit von $n$)?
Dünnbesetzte vs. dichte Graphen¶
Wir unterscheiden:
- Dünnbesetzte (sparse) Graphen
- Dichte (dense) Graphen
Abhängig davon können verschiedene Algorithmen besser geeignet sein.
Aus dem obigen Quiz:
- Ein verbundener, ungerichteter Graph hat mindestens $m \in \Omega(n)$ Kanten.
- Für einen ungerichteten Graphen ohne parallele Kanten gilt $m \in O(n^2)$.
D.h. ein verbundener, ungerichteten Graph ohne parallele Kanten hat eine Kantenanzahl zwischen linear und quadratisch in Bezug auf die Knotenanzahl.
Unformal gilt:
- Ein Graph mit einer Kantenanzahl linear in Bezug auf die Knotenanzahl ist dünnbesetzt (sparse).
- Ein Graph mit einer Kantenanzahl quadratisch in Bezug auf die Knotenanzahl ist dichtbesetzt (dense).
"Teilweise dichte" Graphen mit z.B. $\approx n^{3/2}$ sind sparse oder dense in Abhängigkeit von der speziellen Anwendung.
Repräsentationsformen¶
Adjazenzlisten (adjacency lists)¶
Ausführlich Adjazenzliste:
- Ein Array für die Knoten des Graphen.
- Ein Array für die Kanten des Graphen.
- Für jede Kante jeweils ein Zeiger (Pointer) zu den zwei Endpunkten.
- Für jeden Knoten ein Zeiger (Pointer) zu jeder Kante, an denen der Knoten beteiligt ist.
Also zwei Arrays (oder verkettete Listen) für die Knoten und Kanten, die sich jeweils (kreuz-)referenzieren.
Im einfachsten Fall wird für jeden Knoten einfach eine Liste der über Kanten verbundenen Nachbarknoten gespeichert:
Beachte: Hier wurde kein explizites Kantenarray angegeben.
Quiz¶
Wieviel Speicherbedarf benötigt die (ausführliche) Adjazenzlisten-Repräsentation:
$\Theta(?)$ das '?' ist eine Funktion von $m$ und $n$.
Adjazenzmatrizen (adjacency matrices)¶
Quadratische $n \times n$-Matrix.
Für ungerichtete Graphen: $$ A_{ij} = \left\{ \begin{array}{ll} 1 & \textrm{falls Kante } \{i,j\} \textrm{ zum Graphen gehört} \\ 0 & \, \textrm{sonst} \\ \end{array} \right. $$
Beispiel:
Kann erweitert werden für
- parallele Kanten: $A_{ij}$ ist die Anzahl der Kanten
- gewichtete Graphen: $A_{ij}$ ist das Gewicht der Kante
- gerichtete Graphen $$ A_{ij} = \left\{ \begin{array}{ll} 1 & \textrm{falls Kante } (i,j) \textrm{ zum Graphen gehört} \\ 0 & \, \textrm{sonst} \\ \end{array} \right. $$
Quiz¶
Wieviel Speicherbedarf benötigt die Adjazenzmatrix-Repräsentation:
$\Theta(?)$ das '?' ist eine Funktion von $m$ und $n$.
Vergleich der beiden Repräsentationen¶
- für (dünnbesetzte) Graphen (bzw. nicht dichtbesetzte) ist die Matrixrepräsentation verschwenderisch im Speicherbedarf.
- abhängig vom Algorithmus bzw. Anwendungsfalls: Adjazenzlisten ideal für Graphenerkundungsalgorithmen (Exploration)
Für viele Anwendungsfälle sind die Graphen dünnbesetzt (Webgraph, soziale Netze, Straßennetz etc.).
Zusammenfassung¶
- Ein Graph besteht aus Knoten und Kanten: $G = (V, E)$
- Ein Graph ist dünnbesetzt (sparse), falls die Anzahl der Kanten $m$ linear zur Knotenzahl $n$ ist.
- Ein Graph ist dicht (dense), falls die Anzahl der Kanten $m$ quadratisch zur Knotenzahl $n$ ist.
- Zwei Repräsentationsformen: Adjazenlisten und Adjazanzmatrizen
- Für dünnbesetzte Graphen sind Adjazenlisten besser geeignet.