Graph (Graphentheorie)

Ein Graph ist in der Graphentheorie eine abstrakte Struktur, die eine Menge von Objekten zusammen mit den zwischen diesen Objekten bestehenden Verbindungen repräsentiert. Die mathematischen Abstraktionen der Objekte werden dabei Knoten (auch Ecken) des Graphen genannt. Die paarweisen Verbindungen zwischen Knoten heißen Kanten (manchmal auch Bögen). Die Kanten können gerichtet oder ungerichtet sein. Häufig werden Graphen anschaulich gezeichnet, indem die Knoten durch Punkte und die Kanten durch Linien dargestellt werden.

Schematischer Aufbau eines Stammbaumes

Netzplan der Wiener U-Bahn

Anschauliche Beispiele für Graphen sind ein Stammbaum oder das U-Bahn-Netz einer Stadt. Bei einem Stammbaum stellt jeder Knoten ein Familienmitglied dar und jede Kante ist eine Verbindung zwischen einem Elternteil und einem Kind. In einem U-Bahn-Netz stellt jeder Knoten eine U-Bahn-Station dar und jede Kante eine direkte Zugverbindung zwischen zwei Stationen.

Anschauung für spezielle Graphen

Multigraph

In so genannten Multigraphen können zwei Knoten auch durch mehrere Kanten verbunden sein, was in einfachen Graphen nicht erlaubt ist. Statt mehrere Linien zwischen zwei Punkten zu zeichnen, kennzeichnet man Mehrfachkanten auch häufig durch ihre Vielfachheit.

Gerichteter Graph

In gerichteten oder auch orientierten Graphen werden Kanten statt durch Linien durch Pfeile gekennzeichnet, wobei der Pfeil vom ersten zum zweiten Knoten zeigt. Dies verdeutlicht, dass jede Kante des Graphen nur in eine Richtung durchlaufen werden kann. Eine typische Anwendung ist der Netzplan mit einer temporalen Kette.

Hypergraph

Bei Hypergraphen verbindet eine Kante (auch Hyperkante genannt) nicht nur zwei, sondern mehrere Knoten gleichzeitig. Hypergraphen können beispielsweise durch mehrere planare Graphen mit Indizierung der Kanten dargestellt werden. Hypergraphen mit wenigen Kanten (so genannte dünne Graphen) zeichnet man so, dass man eine Menge von Punkten zeichnet, die den Knoten entsprechen, und die zu einer Hyperkante gehörigen Punkte werden dann durch eine geschlossene Linie umkreist, die somit die Teilmenge der zu ihr gehörenden Knoten innerhalb aller Knoten angibt. Bei Hypergraphen mit vielen Kanten wird diese Darstellung aber schnell unübersichtlich. Weniger intuitiv, aber übersichtlicher ist es dann, einen Hypergraphen als bipartiten Meta-Graphen darzustellen, wobei die eine der beiden Bipartitionsmengen den Knoten des Hypergraphen, die andere Bipartitionsmenge den Hyperkanten des Hypergraphen entspricht. Die Kanten zwischen diesen beiden Bipartitionsmengen symbolisieren dann die Zugehörigkeit der Knoten zu den Hyperkanten.

Definitionen

Ein Graph G ist ein Tupel (V,E), wobei V eine Menge von Knoten (englisch vertex/vertices, oft auch Ecken genannt) und E eine Menge von Kanten (engl. edge/edges, manchmal auch Bögen genannt) bezeichnet. Dabei ist E in

• ungerichteten Graphen ohne Mehrfachkanten eine Teilmenge aller 2-elementigen Teilmengen von V,
• gerichteten Graphen ohne Mehrfachkanten eine Teilmenge des kartesischen Produktes $V \times V$,
• ungerichteten Graphen mit Mehrfachkanten eine Multimenge über der Menge W aller 2-elementigen Teilmengen von V, also eine Funktion $E\colon W \to \N_0$,
• gerichteten Graphen mit Mehrfachkanten eine Multimenge über dem kartesischen Produkt $V \times V$, also eine Funktion $E\colon V \times V \to \N_0$,
• Hypergraphen eine Teilmenge der Potenzmenge von V.

1. ungerichteter Graph ohne Mehrfachkanten

2. gerichteter Graph ohne Mehrfachkanten

3. ungerichteter Graph mit Mehrfachkanten

4. gerichteter Graph mit Mehrfachkanten

Den Zusatz „ohne Mehrfachkanten“ lässt man gewöhnlich weg und nennt Graphen mit Mehrfachkanten Multigraphen. Ferner verzichtet man meist auf das Attribut „ungerichtet“ und kennzeichnet nur gerichtete Graphen explizit. Ungerichtete Graphen ohne Mehrfachkanten nennt man auch häufig schlicht oder einfach. Eine andere Bezeichnung für gerichtete Graphen ist Digraph (Directed Graph).

Abgeleitete Bezeichnungen

Statt die Knoten- und Kantenmenge eines Graphen G mit den Symbolen V und E zu identifizieren, kann man auch allgemeiner Abbildungen V und E definieren, die einen Graphen auf dessen Knotenmenge oder Kantenmenge abbilden. Für zwei Graphen G₁ = (V₁,E₁) und G₂ = (V₂,E₂) bezeichnen also V(G₁): = V₁ und E(G₁): = E₁ sowie V(G₂) = V₂ und E(G₂) = E₂.

Die Mehrdeutigkeit V(G) = V und E(G) = E wird bei dieser Notation in Kauf genommen, obwohl die Abbildungen etwas anderes darstellen als die mit ihr verbundene Knoten- und Kantenmenge. Als Konvention bietet sich an, mit V bzw. E ohne Argument Knoten- bzw. Kantenmenge zu bezeichnen, V bzw. E mit Argument bezeichnen dagegen die definierten Abbildungen.

Ist G ein Graph, so sagt man allgemein v ist Knoten bzw. Ecke von G, wenn v zu V(G) gehört. Außerdem bezeichnet man Kanten $e \in E(G)$ als

• ungerichtete Kante von G, falls G ein ungerichteter Graph ist.
• gerichtete Kante von G, falls G ein gerichteter Graph ist.
• Hyperkante von G, falls G ein Hypergraph ist.

In einer ungerichteten Kante e = {v,w} bezeichnet man v und w als Endknoten von e. In einer gerichteten Kante e = (v,w) bezeichnet man v als Startknoten und w als Endknoten von e.

Bei Multigraphen bezeichnet E(G)(e) die Vielfachheit von e. Wenn E(G)(e) > 1 gilt, so spricht man von einer Multi- oder Mehrfachkante.

Hat eine Kante e in gerichteten Graphen die Form (v,v), so spricht man von einer Schleife. Ist die Schleife e in einem Multigraphen G zugleich eine Mehrfachkante, so spricht man von einer Mehrfachschleife. Gerichtete Graphen ohne Schleifen nennt man schleifenlos oder schleifenfrei.

Als Knotenzahl $n(G) = \vert V(G) \vert$ eines Graphen G bezeichnet man die Anzahl seiner Knoten, als Kantenzahl $m(G) = \vert E(G) \vert$ bezeichnet man die Anzahl seiner Kanten (in Multigraphen summiert man über die Vielfachheit der Kanten).

Spezialfälle

Zwei verschiedene Kanten e₁ und e₂ eines gerichteten Graphen, die dieselben Knoten verbinden, kann man auch als eine ungerichtete Kante innerhalb des gerichteten Graphen betrachten. Im Falle von Mehrfachkanten müssen die Vielfachheiten beider Kanten übereinstimmen.

Gibt es zu jeder Kante eines gerichteten Graphen eine solche entgegengesetzte Kante im Graphen, so ist dies ein Symmetrischer Graph.

Einen Graphen, dessen Knotenmenge endlich ist, nennt man einen endlichen Graphen. Zwangsläufig ist in diesen auch die Kantenmenge endlich. Im Gegensatz dazu nennt man einen Graphen, dessen Knotenmenge unendlich ist, unendlichen Graphen. Meist betrachtet man nur endliche Graphen und lässt daher das Attribut „endlich“ weg, während man unendliche Graphen explizit kennzeichnet.

Teilgraphen, Pfade und Zyklen

Ein gerichteter Graph mit Zyklus

Ein gerichteter Graph ohne Zyklus

Ein Teilgraph G' eines Graphen G enthält nur Knoten und Kanten, die auch in G enthalten sind. Eine Knotenmenge induziert einen eindeutigen Teilgraphen von G.

Eine Folge von Knoten $v_1,\ldots,v_n$, in der aufeinander folgende Knoten v_i und v_{i + 1} im Graphen durch eine Kante verbunden sind, bezeichnet man als Weg. Statt als Knotenfolge können Wege auch als Kantenzug definiert werden. Unterscheiden sich alle Knoten des Weges voneinander, bezeichnet man den Weg als Pfad, andernfalls als Zyklus. Gilt v₁ = v_n, spricht man von einem Kreis, ein spezieller Zyklus.

Wenn ein gerichteter Graph Zyklen enthält, nennt man ihn zyklisch. Enthält ein gerichteter Graph keinen Zyklus, nennt man ihn azyklisch. Dann repräsentiert er eine Halbordnung. In der objektorientierten Programmierung entspricht eine Polyhierarchie einem gerichteten azyklischen Graphen.

Gewichteter Graph

Ein Graph ist gewichtet oder auch bewertet, wenn die Kantenmenge E mit Werten versehen ist – vgl. Erweiterungen. Die Bewertung eines Graphen kann durch eine quadratische Bewertungsmatrix

$B \in \mathbb{R}^{m \times m}$ mit m = | V |

beschrieben werden.

Bemerkungen

Ungerichtete Graphen ohne Mehrfachkanten sind Spezialfälle von Hypergraphen. Multigraphen, in denen keine Mehrfachkanten vorkommen, sind zwar nicht formal, aber anschaulich äquivalent zu Graphen ohne Mehrfachkanten, weshalb man auch diese als Graphen ohne Mehrfachkanten bezeichnet. Es gibt eine bijektive Zuordnung zwischen den beiden Varianten. In diesem Sinne sind Graphen ohne Mehrfachkanten also Spezialfälle von Graphen mit Mehrfachkanten. Ähnlich verhält es sich mit ungerichteten Graphen, die in gewissem Sinn Spezialfälle von gerichteten Graphen sind. Ist ein gerichteter Graph symmetrisch und schleifenlos, so bezeichnet man diesen auch als ungerichtet, da es auch hier eine einfache eineindeutige Zuordnung zwischen beiden Varianten gibt (siehe auch Repräsentation von Graphen im Computer).

Es lassen sich natürlich auch ungerichtete Graphen mit Schleifen definieren, wobei man diese wohl am einfachsten wie eben als (formale) Spezialfälle von gerichteten Graphen definiert und die Bedingung der Schleifenlosigkeit weg lässt. Solche Graphen sind aber nur selten Gegenstand der Betrachtungen in der Graphentheorie.

Der wohl allgemeinste Typ von Graphen sind gerichtete Hypergraphen mit Mehrfachkanten. Jeder oben definierte Graphentyp kann dann als Spezialfall von diesem betrachtet werden. Solche Graphen sind aber so gut wie gar nicht Gegenstand der Betrachtungen in der Graphentheorie, weshalb sie hier auch nicht näher erläutert werden.

Sollen Graphen als Darstellung eines Sachverhaltes herhalten, werden Algorithmen benötigt, die für das Graphzeichnen benötigt werden. Diese Disziplin der Informatik hat sich in den letzten Jahren stets fortentwickelt und liefert Lösungen für unterschiedliche Visualisierungen, die auf Graphen beruhen.

Erweiterungen

Graphen können mit weiteren Eigenschaften bzw. Informationen ergänzt werden.

Eine Erweiterung von Graphen G = (V,E) zu knotengefärbten Graphen erhält man, indem das Tupel (V,E) zu einem Tripel (V,E,f) ergänzt wird. f ist eine Abbildung von V in die Menge der natürlichen Zahlen. Anschaulich gibt man jedem Knoten damit eine Farbe.

Statt der Knoten kann man in Graphen ohne Mehrfachkanten und in Hypergraphen auch die Kanten färben und spricht dann von einem kantengefärbten Graphen. Dazu erweitert man ebenfalls das Tupel (V,E) zu einem Tripel (V,E,f), wobei f aber eine Abbildung von E (statt von V) in die Menge der natürlichen Zahlen ist. Anschaulich gibt man jeder Kante damit eine Farbe. In Graphen mit Mehrfachkanten ist dies zwar prinzipiell auch möglich, aber schwieriger zu definieren, insbesondere, wenn Mehrfachkanten entsprechend ihrer Vielfachheit mehrere verschiedene Farben zugeordnet werden sollen.

Statt von knoten- bzw. kantengefärbten Graphen spricht man von knoten- bzw. kantengewichteten Graphen, falls f statt in die natürlichen Zahlen in die reellen Zahlen abbildet. Knoten- bzw. kantengefärbte Graphen sind also Spezialfälle von knoten- bzw. kantengewichteten Graphen.

Man bezeichnet f(v) bzw. f(e) auch als Gewicht des Knotens v bzw. der Kante e. Zur Unterscheidung spricht man auch von Knotengewicht bzw. Kantengewicht. Eine solche Gewichtung wird erforderlich, wenn die Information über Knotenbeziehungen nicht ausreicht. Fasst man beispielsweise das Straßennetz (vereinfacht) als Graph auf (Orte sind Knoten, die Orte verbindende Straßen sind Kanten), so könnte eine Gewichtung der Kanten Aufschluss über die Distanz zwischen zwei Orten geben.

Analog gibt es auch benannte Graphen (V,E,f,g), bei denen Knoten und/oder Kanten einen Namen tragen, und die Abbildungen f bzw. g den Knoten bzw. Kanten einen Namen zuordnen. Die zuvor abgebildeten Beispiele sind benannte Graphen, bei denen die Knoten mit Buchstaben benannt wurden. Dies wird oft bei Visualisierungen gemacht, so dass man besser über den Graphen diskutieren kann.

Außerdem kann man gleichzeitig oder mehrfach Knoten und Kanten färben, gewichten oder benennen. Die genaue Definition wird dann normalerweise beim speziellen Anwendungsfall erläutert.

Man beachte, dass die Begriffe „Färbung“ und „färben“ in der Graphentheorie auch eine speziellere Bedeutung besitzen. Exakt spricht man dann zwar von gültiger Färbung, lässt das Attribut „gültig“ aber meist weg.

Schließlich lassen sich auch Abbildungen zwischen Graphen definieren. Interessant sind insbesondere solche, die mit der Struktur der beiden verträglich sind, so genannte „Homomorphismen“.

Seien dazu $G_1=\left(V_1,E_1\right)$ und $G_2=\left(V_2,E_2\right)$ Graphen desselben Typs. Eine Abbildung $p\colon V_1\to V_2$ heißt Homomorphismus zwischen G₁ und G₂, falls gilt:

• In ungerichteten Graphen ohne Mehrfachkanten:
  Ist {v,w} eine Kante von G₁, so ist {p(v),p(w)} eine Kante von G₂.
• In gerichteten Graphen ohne Mehrfachkanten:
  Ist (v,w) Kante von G₁, dann ist (p(v),p(w)) Kante von G₂.
• In ungerichteten Graphen mit Mehrfachkanten:
  E₁({v,w}) ≤ E₂({p(v),p(w)}), d. h. je zwei Ecken sind mit höchstens so vielen Kanten verbunden wie ihre Bildecken.
• In gerichteten Graphen mit Mehrfachkanten:
  E₁((v,w)) ≤ E₂((p(v),p(w))).
• In Hypergraphen:
  Ist {v₁,...,v_k} Kante von G₁, so ist {p(v₁),...,p(v_k)} Kante von G₂.

Das Bild p(G₁) ist dann ein Teilgraph von G₂. Ist p umkehrbar und die Umkehrfunktion ebenfalls ein Homomorphismus, so ist p ein Isomorphismus von Graphen.

Zu beachten ist, dass die Knoten vor den Kanten einen Vorrang haben, indem p als Funktion nur auf den Knoten spezifiziert ist, die auf den Kanten lediglich eine induzierte Wirkung entfaltet.

Literatur

• Reinhard Diestel: Graphentheorie. 4. Auflage. Springer, Berlin u. a. 2010 (Erstausgabe 1996), ISBN 978-3-642-14911-5 (online: 4th Electronic Edition 2010, Free preview version (englisch)).
• Jürgen Ebert: Effiziente Graphenalgorithmen. In: Studien-Texte – Informatik. Akademische Verlags-Gesellschaft, Wiesbaden 1981, ISBN 3-400-00424-3 (Zugleich Habilitationsschrift an der Universität Osnabrück 1982).
• Dieter Jungnickel: Graphen, Netzwerke und Algorithmen. 3. vollständig überarbeitete und erweiterte Auflage Auflage. BI-Wissenschafts-Verlag, Mannheim u. a. 1994, ISBN 3-411-14263-4 (Inhaltsverzeichnis, PDF, 1,14 MB).
• Manfred Nitzsche: Graphen für Einsteiger. Rund um das Haus vom Nikolaus. In: Studium. 3., überarbeitete und erweiterte Auflage. Vieweg+Teubner, Wiesbaden 2009, ISBN 978-3-8348-0813-4.

Siehe auch

• Baum (Graphentheorie)
• Graphenspiele
• Small-world-Netzwerk
• Skalenfreies Netz
• Zufallsgraph