Graphentheorie

Verschiedene typische Formen von Graphen

Die Graphentheorie ist jenes Teilgebiet der Mathematik, das sich mit den Eigenschaften von Graphen beschäftigt.

Ein Graph wird mathematisch als eine abstrakte Struktur definiert, die aus Knoten und Kanten besteht. Ein Knoten ist ein einzelnes Element des Graphen und die Verbindung zweier Knoten eine Kante. Knoten können dabei auch durch Mehrfachkanten, d.h. durch mehrere Kanten verbunden sein. Die Anzahl der Kanten eines Knotens bestimmt dessen Knotengrad (kurz auch Grad oder Valenz). Wird der Kante zusätzlich auch eine Richtung zugewiesen, spricht man von einer gerichteten Kante, andernfalls von einer ungerichteten Kante. Sind zwei Knoten durch eine gerichtete Kante verbunden, so bilden sie ein geordnetes Paar. Einem Knoten oder einer Kante kann auch ein reelle Zahl als Gewicht, d.h. als Knotengewicht oder Kantengewicht zugewiesen werden. Ein Beispiel dafür ist etwa ein Straßennetz, bei dem die Kanten mit den Fahrzeiten oder Entfernungen gewichtet sind und so die schnellsten bzw. kürzesten Wege ermittelt werden können.

Ein Spezialfall einer Kante ist die Schleife oder Schlinge, die einen Knoten mit sich selbst verbindet. Sie erhöht daher den Knotengrad um 2. Ein geschlossener Zug von Knoten und Kanten wird als Masche bezeichnet. Wenn die Mehrzahl der Knoten eines Graphen zu einer oder mehreren Maschen gehört, spricht man von einem Netzwerk.

Siehe auch

• Graphentheorie - Artikel in der deutschen Wikipedia
• Graph (Graphentheorie) - Artikel in der deutschen Wikipedia