Zusammenhang & Kreisfreiheit

Allgemeine Graphen können viele Eigenschaften haben, die je nach Anwendungsfall wichtig werden können. Im Folgenden sollen zwei solche Eigenschaften betrachtet werden.

Ein ungerichteter Graph kann zusammenhängend sein. Das bedeutet, dass von jedem beliebigen Knoten aus, über eine Folge von Kanten, zu jedem anderen Knoten gelaufen werden kann. Ein ungerichteter Graph kann zykelfrei (oder auch kreisfrei) sein. Dabei ist ein Zyklus eine Folge von Kanten, die einen Knoten mit sich selbst verbindet, sodass keine anderen Knoten mehrfach besucht werden.

Der nachfolgende Graph ist zusammenhängend, aber nicht kreisfrei, da die drei blau markierten Knoten einen Zyklus bilden.

Der nachfolgende Graph ist kreisfrei, aber nicht zusammenhängend, da es keinen Weg zwischen den blau markierten Knoten gibt.

Weiterführende Informationen zur Einführung von Graphen finden Sie in (Aigner, 2015).