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

bla

Kreise

bla

Vollständige Graphen

bla

Definition

xxkj

Kantenanzahl

xkdkf

Adjazenz- und Inzidenzmatrix

sffg

Teilgraph