Пути в графах

Чередующаяся последовательность

(2.1)

вершин и ребер графа, такая что (i = 1, 2, …, l), называется путем, соединяющим вершины и (или (, )-путем).

его вершин, а также последовательностью его ребер

.

Граф называется связным, если любые две несовпадающие вершины в нем соединены маршрутом.

Путь называется простым, если все его вершины, кроме, может быть, крайних, различны. Путь называется цепью, если все его ребра различны, и простой цепью, если все его вершины различны. Путь (2.1) называется циклическим, если . Циклическая цепь называется циклом, а циклическая простой путь – простым циклом. Простую цепь, имеющую п вершин, будем обозначать Cn, простой цикл – Zn ( рис.2.14).

Число l ребер в пути (2.1) называется его длиной.

Пример 3. В графе G на рис 2.11 (1, 4, 5, 2, 4) – цепь; (1, 4, 5, 2, 3) – простая цепь; (1, 4, 5, 2, 4, 1) – циклический путь, не являющийся циклом; (4, 3, 2, 4) – цикл.