Mathematik Graphentheorie – Grundbegriffe und Wege

Knoten (Ecken) sind die Grundelemente, Kanten verbinden zwei Knoten miteinander und stellen Beziehungen dar.

Der Grad eines Knotens ist die Anzahl der an ihm inzidierenden Kanten; bei gerichteten Graphen unterscheidet man Ein- und Ausgrad.

Bei gerichteten Graphen haben Kanten eine Richtung (Bögen), bei ungerichteten Graphen sind Kanten symmetrische Verbindungen ohne Orientierung.

Ein Weg ist eine abwechselnde Folge von Knoten und Kanten, bei der jede Kante ihre Endknoten verbindet; Knoten dürfen sich wiederholen.

Ein einfacher Weg enthält keine wiederholten Knoten – außer eventuell Start- und Endknoten bei einem Zyklus.

Ein Zyklus ist ein geschlossener einfacher Weg mit mindestens drei Kanten, bei dem Start- und Endknoten identisch sind.

Ein ungerichteter Graph ist zusammenhängend, wenn zwischen je zwei Knoten mindestens ein Weg existiert; bei gerichteten Graphen spricht man von starker Zusammenhang.

Ein Baum ist ein zusammenhängender, kreisfreier Graph; er hat genau n-1 Kanten für n Knoten und genau einen Weg zwischen je zwei Knoten.

Ein vollständiger Graph K_n enthält alle möglichen Kanten zwischen n Knoten – jede Knotenpaar ist direkt verbunden.

Ein bipartiter Graph hat eine Knotenmenge, die in zwei disjunkte Teilmengen zerfällt, wobei Kanten nur zwischen den Teilmengen verlaufen.

Ein Euler-Weg durchläuft jede Kante genau einmal, ein Hamilton-Weg besucht jeden Knoten genau einmal.

Eine Brücke ist eine Kante, deren Entfernung die Anzahl der Zusammenhangskomponenten des Graphen erhöht.

Ein induzierter Teilgraph entsteht durch Auswahl einer Knotenuntermenge und Übernehmen aller Kanten, deren beide Endknoten in der Teilmenge liegen.

Die Summe aller Knotengrade in einem ungerichteten Graphen ist doppelt so groß wie die Anzahl der Kanten – jedes Kantenende wird einmal gezählt.