Graph (Graphentheorie)

Grundidee und formale Beschreibung

Ein Graph ist in der Graphentheorie eine abstrakte Struktur zur Darstellung von Objekten und ihrer Verbindungen. Die Objekte heißen Knoten oder Ecken, die Verbindungen Kanten, manchmal Bögen. Anschaulich zeichnet man Knoten als Punkte und Kanten als Linien oder, bei Richtung, als Pfeile. So kann ein U-Bahn-Netz modelliert werden: Stationen sind Knoten, direkte Zugverbindungen Kanten. Weitere genannte Anwendungen sind Moleküle mit Atomen und Molekularverbindungen, Polyeder im Schlegeldiagramm sowie das Internet aus Computern und Datenverbindungen.

Formal ist ein Graph G ein geordnetes Paar (V,E). V ist die Knotenmenge, E die Kantenmenge. Bei einem ungerichteten Graphen ohne Mehrfachkanten ist E eine Teilmenge aller 2-elementigen Teilmengen von V: Eine Kante {v,w} verbindet also v und w ohne Reihenfolge. Bei einem gerichteten Graphen ohne Mehrfachkanten ist E eine Teilmenge von V×V; eine Kante (v,w) führt vom Startknoten v zum Endknoten w.

Für Multigraphen können Kanten als Multimenge beschrieben werden. Bei ungerichteten Graphen ist E dann eine Funktion von der Menge W aller 2-elementigen Teilmengen von V nach ℕ₀, bei gerichteten Graphen eine Funktion E: V×V → ℕ₀. Ihr Wert gibt an, wie oft eine Kante vorkommt. Für Hypergraphen ist E eine Teilmenge der Potenzmenge von V.

Üblich ist V(G) für die Knotenmenge und E(G) für die Kantenmenge eines Graphen G. Die Knotenzahl lautet n(G)=|V(G)|, die Kantenzahl m(G)=|E(G)|; bei Multigraphen werden Kanten nach ihrer Vielfachheit gezählt. Zwei Knoten sind benachbart, wenn eine Kante sie verbindet.

Wichtige Graphtypen

Ein ungerichteter Graph besitzt Kanten ohne Richtung. Jede Verbindung kann in beide Richtungen durchlaufen werden. Ungerichtete Graphen ohne Mehrfachkanten heißen auch einfache oder schlichte Graphen.

Ein gerichteter Graph oder Digraph verwendet Pfeile vom Anfangs- zum Endknoten. Eine Kante kann nur in ihrer Pfeilrichtung durchlaufen werden. Orientierte Graphen sind ein Spezialfall: Gibt es eine Kante von A nach B, gibt es nie zugleich die umgekehrte Kante von B nach A.

Ein Baum ist ein zusammenhängender Graph ohne geschlossene Pfade, also ohne Zyklen der Länge größer oder gleich 3. Bei jedem Baum ist die Anzahl der Knoten um 1 größer als die Anzahl der Kanten. Bäume werden besonders in der Informatik verwendet, etwa für Breitensuche und Tiefensuche in Netzwerken, Verkehrs- oder Versorgungsnetzen. Die Alpha-Beta-Suche in künstlicher Intelligenz und Strategiespielen basiert auf Suchbäumen.

In einem Multigraphen dürfen mehrere Kanten dieselben zwei Knoten verbinden. Außerdem kann er Schleifen enthalten, also Kanten, die zum selben Knoten führen, von dem sie ausgehen. Bei einer zusammengefassten Darstellung kann eine gewichtete Kante die Zahl der Mehrfachkanten angeben.

Ein planarer Graph lässt sich in einer Ebene so zeichnen, dass sich Kanten nicht schneiden. Zu jeder Fläche gehört im dualen Graphen ein Knoten innerhalb dieser Fläche; die Dualität ist gegenseitig, denn der duale Graph des dualen Graphen ist wieder der ursprüngliche Graph. Für planare Graphen gilt der Eulersche Polyedersatz E-K+F=2.

In einem Hypergraphen verbindet eine Hyperkante mehr als zwei Knoten zugleich. Bei wenigen Kanten kann man die zu einer Hyperkante gehörenden Punkte mit einer geschlossenen Linie umkreisen. Bei vielen Kanten ist die Darstellung als bipartiter Meta-Graph übersichtlicher: Eine Bipartitionsmenge steht für die Knoten, die andere für die Hyperkanten; Kanten zwischen beiden zeigen die Zugehörigkeit an.

Teilgraphen, Wege und Sonderfälle

Ein Teilgraph G′ von G enthält nur Knoten und Kanten, die bereits in G vorkommen. Ein durch eine Knotenmenge U induzierter Teilgraph enthält alle Knoten aus U sowie alle Kanten aus G zwischen diesen Knoten.

Ein Weg oder Pfad ist eine Folge paarweise verschiedener Knoten v₁,…,vₙ, bei der aufeinander folgende Knoten durch Kanten verbunden sind. Gilt v₁=vₙ und ist dies der einzige doppelte Knoten, heißt die Folge Zyklus oder Kreis. Eine Kantenfolge ist dagegen eine Folge benachbarter Knoten, in der Wiederholungen erlaubt sind. Die Begriffe Weg, Pfad, Kantenfolge, Kreis und Zyklus werden in der Literatur teilweise unterschiedlich definiert.

Ein gerichteter Graph ohne Zyklus heißt azyklisch oder zyklenfrei, auf Englisch DAG (directed acyclic graph). Ergänzt man in ihm Kanten zwischen gleichen Ausgangs- und Endknoten wie vorhandene Wege, werden Umwege abgekürzt; dies heißt Bildung der transitiven Hülle und erweitert den Graphen zu einer endlichen und diskreten Halbordnung. Ein Hasse-Diagramm ist ein gerichteter azyklischer Graph, bei dem die durch das Transitivitätsgesetz implizierten Kanten weggelassen sind; dies ist die transitive Reduktion.

Ein gerichteter Graph ist symmetrisch, wenn zu jeder Kante auch die entgegengesetzt gerichtete Kante vorhanden ist. Bei Mehrfachkanten müssen die Vielfachheiten übereinstimmen. Symmetrische schleifenlose gerichtete Graphen lassen sich eindeutig ungerichteten Graphen zuordnen. Graphen mit endlicher Knotenmenge heißen endlich, mit unendlicher Knotenmenge unendlich.

Operationen und zusätzliche Informationen

Für Graphen desselben Typs G₁=(V₁,E₁) und G₂=(V₂,E₂) bedeutet G₁+G₂ die Vereinigung ihrer Knoten- und Kantenmengen. G₁−E₂ entfernt die Kanten aus E₂ aus G₁. G₁−V₂ entfernt die Knoten aus V₂ und zugleich alle Kanten, die einen dieser Knoten enthalten. Häufige Abkürzungen sind G₁+v für das Hinzufügen eines einzelnen Knotens und G₁−v für dessen Entfernen. Weitere Basisoperationen sind Kantenkontraktion und die Bildung des Komplementgraphen.

Graphen können Informationen tragen. Ein knotengefärbter Graph ist (V,E,f), wobei f: V → ℕ jedem Knoten eine Farbe zuordnet. Bei einem kantengefärbten Graphen ohne Mehrfachkanten oder einem Hypergraphen gilt entsprechend f: E → ℕ. In der Graphentheorie kann „Färbung“ außerdem speziell eine gültige Färbung meinen. Benannte Graphen (V,E,f,g) ordnen Knoten und/oder Kanten Namen zu.

Bei gewichteten Graphen bildet f nicht in die natürlichen, sondern in die reellen Zahlen ab. f(v) oder f(e) heißt dann Knoten- beziehungsweise Kantengewicht. In einem als Graph aufgefassten Straßennetz können Orte Knoten, Straßen Kanten und Kantengewichte Distanzen sein. Die Kantengewichte können in einer quadratischen Gewichtsmatrix, der Adjazenzmatrix, gesammelt werden.

Ein Homomorphismus p: V₁ → V₂ zwischen Graphen desselben Typs erhält ihre Struktur: Eine Kante in G₁ wird auf eine entsprechende Kante in G₂ abgebildet. Bei Multigraphen darf die Vielfachheit zwischen Bildknoten nicht kleiner sein, also etwa E₁({v,w})≤E₂({p(v),p(w)}). Bei Hypergraphen wird jede Hyperkante {v₁,…,vₖ} auf {p(v₁),…,p(vₖ)} abgebildet. Das Bild p(G₁) ist ein Teilgraph von G₂. Ist p umkehrbar und auch seine Umkehrfunktion ein Homomorphismus, heißt p Isomorphismus.

Anzahlen und Computerdarstellung

Die Zahl einfacher ungerichteter Graphen mit n nummerierten Knoten beträgt 2^(n·(n−1)/2). Der Exponent n·(n−1)/2 ist die Zahl der Kanten des vollständigen Graphen Kₙ. Ohne nummerierte Knoten, also wenn isomorphe Graphen nicht mehrfach gezählt werden, ist die Anzahl ungefähr proportional zu (1/n!)·2^(n·(n−1)/2). Für n=1 bis 8 nennt der Artikel folgende Zahlen mit beziehungsweise ohne nummerierte Knoten: 1: 1 und 1; 2: 2 und 2; 3: 8 und 4; 4: 64 und 11; 5: 1.024 und 34; 6: 32.768 und 156; 7: 2.097.152 und 1.044; 8: 268.435.456 und 12.346.

Im Computer werden Graphen vor allem als Adjazenzmatrix oder Adjazenzliste dargestellt; die Adjazenzmatrix heißt auch Nachbarschaftsmatrix, die Adjazenzliste Nachbarschaftsliste. Eine weitere, seltener verwendete Form ist die Inzidenzmatrix oder Knoten-Kanten-Matrix. Diese benötigt bei fester Kantenzahl linear viel Speicherplatz bezüglich der Knotenzahl und ist daher für dünne Graphen mit wenigen Kanten vorteilhaft. Eine Adjazenzmatrix hat quadratischen Platzbedarf bezüglich der Knotenzahl, kann aber bei dichten Graphen kompakter sein. Viele Probleme lassen sich nur mit Adjazenzlisten in linearer Zeit lösen, weshalb diese in der Praxis meist verwendet werden.

Das C++-Beispiel implementiert einen gerichteten Graphen mit Adjazenzlisten. Knoten speichern Index, Wert und einen Zeiger auf den nächsten Nachbarn; Kanten speichern Start- und Endindex. Beim Erzeugen des Graphen wird für jede Kante der Endknoten in die Nachbarschaftsliste des Startknotens eingefügt. Anschließend gibt das Programm für jeden Knoten seine benachbarten Knoten aus.