Einleitung
Anschaulich besteht ein Graph aus eine Menge von Punkten, zwischen denen Lininen verlaufen. Die Punkte nennt man Knoten oder Ecken, die Linien nennt man Kanten. Auf die Form der Knoten und Kanten kommt es im allgemeinen dabei nicht an.
In sogenannten 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, schreibt man an Mehrfachkanten auch ihre Vielfachheit ran.
In gerichteten Graphen werden Kanten statt durch Linien durch Pfeile gekennzeichnet, wobei der Pfeil vom ersten zum zweiten Knoten zeigt.
Hypergraphen sind meist nur schwer vor-/darstellbar. In der Regel zeichnet man eine Menge von Punkten, die den Knoten entsprechen, welche durch geschlossene Linien umkreist werden. Die geschlossenen Linien entsprechen dann den Hyperkanten.
Definitionen
Ein Graph G ist in der Graphentheorie ein Tupel (V, E), wobei V eine Menge von Knoten (oft auch Ecken genannt) und E eine (höhere) Menge von Kanten (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 x V,
- ungerichteten Graphen mit Mehrfachkanten eine Multimenge über der Menge aller 2-elementigen Teilmengen von V,
- gerichteten Graphen mit Mehrfachkanten eine Multimenge über dem kartesischen Produkt V x V,
- Hypergraphen eine Teilmenge der Potenzmenge von V.
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.
Um kürzer schreiben zu können, definiert man gewöhnlich zwei Abbildungen V und E, die einem Graphen G=(V,E) seine Knoten- bzw. Kantenmenge zuordnen, d.h. V(G) := V und E(G) := E. Man beachte, dass trotz der selben Symbole (V bzw. E) die Knoten- bzw. Kantenmenge etwas anderes als die gerade definierten Abbildungen darstellen. Wenn es nicht anders gesagt wird, meinen V bzw. E ohne Argument gewöhnlich die Knoten- bzw. Kantenmenge des gerade betrachteten Graphen. V bzw. E mit Argument meinen hingegen immer die gerade definierten Abbildungen, deren Ergebnis dann natürlich wieder eine Knoten- bzw. Kantenmenge ist, und zwar die des als Argument angegebenen Graphen.
Ist G ein Graph, so sagt man allgemein v ist Knoten (bzw. Ecke) von G, wenn v zu V(G) gehört. Ferner sagt man, falls G
- ungerichteter Graph ohne Mehrfachkanten ist und e zu E(G) gehört, e ist eine ungerichtete Kante von G,
- gerichteter Graph ohne Mehrfachkanten ist und e zu E(G) gehört, e ist eine gerichtete Kante von G,
- ungerichteter Graph mit Mehrfachkanten ist und E(G)(e) > 0, e ist eine ungerichtete Kante von G,
- gerichteter Graph mit Mehrfachkanten ist und E(G)(e) > 0, e ist eine gerichtete Kante von G,
- Hypergraph ist und e zu E(G) gehört, e ist eine Hyperkante von G.
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.
Ist in Multigraphen sogar E(G)(e) > 1, so spricht man auch von einer Multi- oder Mehrfachkante. E(G)(e) bezeichnet man auch als die Vielfachheit von e. Hat eine Kante e in gerichteten Graphen die Form (v, v), so spricht man von einer Schleife. Ist e in einem Multigraphen G zusätzlich eine Mehrfachkante, so spricht man von einer Mehrfachschleife. Eine 1- oder 2-elementige Menge von geordneten Paaren mit der Eigenschaft, dass sie neben (v,w) auch (w,v) enthält (im 1-elementigen Fall ist dies natürlich nur bei v=w möglich) nennt man, falls G
- gerichteter Graph ohne Mehrfachkanten ist und sowohl (v,w) als auch (w,v) Kante von G sind, ungerichtete Kante von G,
- gerichteter Graph mit Mehrfachkanten ist und E(G)((v,w)) = E(G)((w,v)), ungerichtete Kante von G.
1-elementige ungerichtete Kanten in gerichteten Graphen sind offensichtlich also immer Schleifen. Umgekehrt lässt sich zu jeder Schleife e leicht eine ungerichtete Kante konstruieren (nämlich {e}). Schleifen sind in diesem Sinne also immer ungerichtet, weshalb man gewöhnlich das Attribut "gerichtet" weg lässt. Ist jede Kante eines gerichteten Graphen G Element einer ungerichteten Kante von G, so nennt man G auch symmetrisch.
Man lässt gewöhnlich in ungerichteten Graphen das Attribut "ungerichtet" für Kanten weg. In gerichteten Graphen lässt man das Attribut "gerichtet" für Kanten gewöhnlich nur dann weg, falls man keine ungerichteten Kanten betrachtet. In Hypergraphen sagt man statt Hyperkante auch oft einfach nur Kante.
Gerichtete Graphen ohne Schleifen nennt man schleifenlos oder schleifenfrei.
Als Knotenzahl n(G)=|V(G)| eines Graphen G bezeichnet man die Anzahl seiner Knoten, als Kantenzahl m(G)=|E(G)| bezeichnet man die Anzahl seiner Kanten (in Multigraphen summiert man über die Vielfachheit der Kanten).
Einen Graph, dessen Knotenmenge endlich ist, nennt man endlicher Graph. Zwangsläufig ist in diesen auch die Kantenmenge endlich. Im Gegensatz dazu nennt man einen Graph, dessen Knotenmenge unendlich ist, unendlicher Graph. Meist betrachtet man nur endliche Graphen und lässt daher das Attribut "endlich" weg, während man "unendliche Graphen" explizit kennzeichnet.
Bemerkungen
Ungerichtete Graphen ohne Mehrfachkanten sind offensichtlich 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 offensichtlich eine einfache eineindeutige 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 offensichtlich 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.
Erweiterungen
Oft erweitert man Graphen G=(V,E) zu knotengefärbten Graphen, indem man das Tupel (V,E) zu einem Tripel (V,E,f) ergänzt, wobei f eine Abbildung von V in die Menge der natürlichen Zahlen ist. 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 Graph. 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.
Man kann auch gleichzeitig oder mehrfach Knoten und Kanten färben bzw. wichten. 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.
Beispiele
Beispiele für Klassen einfacher Graphen sind
- Ein Wald ist ein Graph ohne Kreis
- Ein Baum ist ein zusammenhängender Graph ohne Kreis
- Ein vollständiger Graph ist ein Graph bei dem zwischen allen Knotenpaaren jeweils eine Kante existiert
Siehe auch: Zyklisch (Graphentheorie)