Schlagwort-Archive: Kantenfolge

7 Kantenfolge, Kantenzug, Weg

zurück zu Grundbegriffe I

7 Kantenfolge, Kantenzug, Weg

7.1 Kantenfolge

Eine Kantenfolge von x1 nach x2 ist eine endliche Folge von Kanten [x1,x2], [x2,x3], …, [xn-1, xn] so, dass je zwei aufeinanderfolgende Kanten adajazent sind.

[KF(x1,xn] heißt offen, falls x1 ≠ xn und geschlossen, falls x1 = xn.

Kanten dürfen sich wiederholen;

(KF(x1,xn))

7.2 Kantenzug

Ein Kantenzug ist eine KF bei der alle Kanten voneinander verschieden sind.
(KZ(x1,xn))

7.3 Weg

Ein Weg ist eine offene Kantenfolge, in der alle Knoten verschieden sind.

Ein Knoten x wird ebenfalls als Weg (zu sich selbst) aufgefasst.
(W(x1,xn))

Jede Kantenfolge von x1 nach xn enthält einen Weg von x1 nach xn.

[x1,x2],[xi,xj]…[xn-1,xn] xi = xj
x1=xn Knoten = Weg
x1 ist nicht Xn i Vj(i⟨j) u (xi=xj)

i= 1 [x1,xj+1][xj+1.xj+2]…
i ist nicht 1 [x1,…

7.4 Kanntenzüge, Wege, Kreise (dtv)

Kantenzug (offen oder geschlossen) wird def. wie oben Kantenfolge. Tritt keine Kante doppelt auf spricht man von einem einfachen Kantenzug (entspricht Kantenzug s.o.). Bei paarweise verschiedenen Ecken spricht man von einem Weg (wie oben).

Ein Kantenzug in dem jede Kante des Graphen genau einmal auftritt, wird Eulersch’e Linie genannt (im Königsberger Brückenproblem ist eine derartige Linie gesucht).

Enthält ein Kreis bzw. Weg alle Ecken des Graphen, so spricht man von einer geschlossenen bzw. offenen Hamiltonschen Linie.

nach oben

(2865)