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

Ein Graph, bei dem je zwei Knoten benachbart sind, heißt vollständig. Für n ≥ 2 bezeichnen wir den vollständigen Graphen auf n Knoten mit Kn .

Kantenanzahl

xkdkf

Adjazenz

Bei einem Graph mit der Knotenmenge V = {v1,...,vn} und der Kantenmenge E = {e1,...,em} verstehen wir unter der Adjazenzmatrix von G die (n × n)-Matrix A(G), deren Eintrag an der Stelle (i, j) gleich der Anzahl der Kanten zwischen den Knoten vi und vj ist.

Inzidenzmatrix

Bei einem Graph mit der Knotenmenge V = {v1,...,vn} und der Kantenmenge E = {e1,...,em} verstehen wir unter der Inzidenzmatrix von G die (n × m)-Matrix I(G), deren Eintrag an der Stelle (i, j) gleich 1 ist, wenn der Knoten vi zur Kante ej gehört, und andern- falls gleich 0.

Teilgraph

Es sei G = (VG ,EG ) ein Graph. Ein Teilgraph von G ist ein Graph H = (VH ,EH ), dessen Kno- tenmenge VH eine Teilmenge von VG und dessen Kantenmenge EH eine Teilmenge von EG ist. Wir nennen einen Teilgraphen H ⊆ G darüber hinaus induziert, falls mit jedem Knoten v von H auch sämtliche mit v inzidenten Kanten zu H gehören.