Graphentheorie

Teilgebiet der Kombinatorik, das sich mit der Charakterisierung von Graphen und der Untersuchung ihrer Eigenschaften und Anwendungsmöglichkeiten beschäftigt. Ein Graph besteht aus einer Menge von Punkten, die Knoten oder Ecken genannt werden, und einer Menge von Kanten, die je zwei Knoten miteinander verbinden. Verbindet eine Kante einen Knoten mit sich selbst, heißt sie Schlinge. Graphen werden zur Veranschaulichung von Relationen genutzt: Ist auf einer endlichen Menge M eine Relation definiert, ist jedes Element von M ein Knoten des Graphen; zwei Knoten sind genau dann durch eine Kante verbunden, wenn zwischen den entsprechenden Elementen von M eine Relation besteht. Ein Graph, der nur endlich viele Knoten enthält, heißt endlicher Graph; haben die Kanten einen Richtungssinn, spricht man von einem gerichteten Graph; sind je zwei Knoten durch genau eine Kante verbunden, nennt man den Graph vollständig oder einen Simplex. Ein Weg von einem Knoten zu einem anderen ist eine Folge von Kanten, die die beiden Knoten miteinander verbindet. Gibt es in einem Graphen zwischen zwei beliebigen Ecken immer einen Weg, der sie verbindet, so wird er auch als Netz bezeichnet. In vielen Anwendungsbeispielen stellt die Graphentheorie ein Modell dar, mit dem sich die jeweils betrachteten Probleme abstrakt formalisieren lassen, so werden Methoden der Graphentheorie u. a. bei der Planung von Verkehrsnetzen, in der Netzplantechnik oder auch zur Darstellung und Analyse chemischer Strukturformeln genutzt.