Zurückblättern Weiterblättern Übergeordnetes Thema Sachgebiet Hauptinhaltsverzeichnis Stichwortverzeichnis Hilfeseiten        


Ungerichtete und gerichtete Graphen

Ein Graph ist ein geordnetes Paar aus einer Menge von Knoten und einer Menge von Kanten . Auf ist eine Abbildung ( Inzidenzfunktion ) erklärt, die jedem Element von eindeutig ein geordnetes oder ungeordnetes Paar (nicht notwendig verschiedener) Elemente von zuordnet. Ist jedem Element von ein ungeordnetes Paar zugeordnet, dann wird ein ungerichteter Graph genannt (linke Abbildung).



Ist dagegen jedem Element von ein geordnetes Paar zugeordnet, dann spricht man von einem gerichteten Graphen (rechte Abbildung). Die Elemente von heißen dann auch Bögen oder gerichtete Kanten . Alle anderen Graphen werden gemischte Graphen genannt.
In der graphischen Darstellung erscheinen die Knoten der Graphen als Punkte, die gerichteten Kanten als Pfeile und die ungerichteten Kanten als ungerichtete Linien.

Beispiel A

Für den Graphen in der Abbildung



gilt:

Beispiel B

Für den Graphen in der Abbildung



gilt:


Beispiel C

Für den Graphen in der Abbildung



gilt: