Frank Ehrlich, Ralf Zücker

Wege und Kreise

bla

Was ist ein Weg?

Ein Weg ist ein Graph, der aus aneinander gehängten Kanten besteht. Damit gibt es bei einem Weg zwei ausgezeichnete Knoten.

Definition eines Wegs Für n ≥ 2 nennt man einen Graphen Pn mit der Knotenmenge V (Pn) = {v0,v1,...,vn} und der Kantenmenge E(Pn) = {{v0,v1},{v1,v2},...,{vn−1,vn}} einen Weg (oder Pfad) der Länge n, sofern keine Kante mehrfach durchlaufen wird. Knoten hingegen dürfen bei einem Weg mehrfach vorkommen (d. h. die Knoten vi müssen nicht notwendig paarweise verschieden sein). Lässt man auch mehrfach durchlaufene Kanten zu, so spricht man von einem Kantenzug. Eine häufig genutzte Notation für einen solchen Weg ist die Tupelschreibweise seiner Knoten mithilfe runder Klammern: Pn = (v0,v1,...,vn). Meist fordert man zusätzlich explizit, dass v0 = vn gelten muss, der Weg also offen ist.

Zusammenhängend

Wir nennen einen Graphen G zusammenhängend, falls es zu je zwei verschiedenen Knoten v,w ∈ V (G) einen Weg auf G mit v und w als Endknoten gibt. Ein maximaler zusammen- hängender Teilgraph von G heißt Zusammenhangskomponente von G.

Kreise

Für n ≥ 3 heißt der Graph Cn mit V (Cn) = {v0,v1,...,vn = v0} und E(Cn) = {{v0,v1},{v1,v2},...,{vn−1,v0}} Kreis der Länge n.

Vollständige Graphen

bla

Definition

xxkj

Kantenanzahl

xkdkf

Adjazenz- und Inzidenzmatrix

sffg

Teilgraph