Typen von Graphen in der Graphentheorie

Dies ist eine alte Version dieser Seite, zuletzt bearbeitet am 22. November 2002 um 07:57 Uhr durch Koethnig (Diskussion | Beiträge). Sie kann sich erheblich von der aktuellen Version unterscheiden.
(Unterschied) ← Nächstältere Version | Aktuelle Version (Unterschied) | Nächstjüngere Version → (Unterschied)

Definition

Ein Graph G ist ein Tupel (V, E), wobei V eine Menge von Knoten (oft auch Ecken genannt) und E eine Menge von Kanten bezeichnet. Dabei ist E eine Teilmenge aller 2-elementigen Teilmengen von V.


Einordnung

So definierte Graphen nennt man auch oft schlicht oder einfach, da sie die simpelste Art von Graphen darstellen. Zur Unterscheidung von gerichteten Graphen verwendet man auch oft die Bezeichnung ungerichteter Graph.

Weitere generalisierte Formen von Graphen sind Multigraphen und Hypergraphen.

In der Regel betrachtet man nur endliche Graphen, bei denen die Menge der Knoten endlich ist. Zwangsläufig ist dann auch die Menge der Kanten endlich. Graphen mit unendlich vielen Knoten bezeichnet man als unendliche Graphen. Normalerweise läßt man das Attribut "endlich" weg und kennzeichnet nur unendliche Graphen explizit.


Anschauung

Anschaulich ist ein Graph eine Menge von Punkten, die den Knoten entsprechen, welche durch Linien miteinander verbunden sind, die den Kanten entsprechen. Dabei können im Unterschied zu Multigraphen zwei Punkte nur durch maximal eine Linie verbunden sein.


Beispiel

Folgendes Bild zeigt einen Graphen.

http://schlichter_graph.jpg

Formal schreibt sich dieser wie folgt:

G = ({1,2,3,4,5,6,...???},{???})