Graphentheorie

Aus AnthroWiki
Version vom 17. Juli 2019, 09:43 Uhr von imported>Odyssee
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. 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