Маршруты, цепи и циклы

Рассматривая геометрический граф, можно зафиксировать некоторую вершину и, последовательно двигаясь по смежным ребрам к вершинам, прийти в другую вершину или вернуться в исходную. В геометрическом графе это означает, что мы непрерывным образом двигаемся по последовательности простых кривых. Последовательности ребер, по которым можно двигаться непрерывным образом, играют фундаментальную роль в теории графов. В частности, такие структуры, как цепи и циклы, в которых ни одно ребро не встречается дважды и которые мы определим ниже, будут постоянно встречаться во всех последующих главах. Перейдем теперь к формальным определениям.

Конечная последовательность ребер графа e ₁, e ₂, …, e _n (не обязательно различных) называется маршрутом длины n, если существует последовательность v ₀, v ₁, …, v _n из n +1 (не обязательно различных) вершин таких, что e _i ~ (v_{i- 1} & v_i) для i = 1, 2, …, n.

Говорят, что маршрут замкнут, если v ₀ = v _n, и не замкнут, если v ₀ ¹ v _n. В последнем случае также говорят, что маршрут соединяет вершины v ₀ и v _n. Заметим, что одно ребро можно рассматривать как маршрут длины 1.

Обращаясь к рис. 6.6, видим, что последовательность ребер e ₇, e ₁, e ₈, e ₃, e ₄, e ₅ образует незамкнутый маршрут, соединяющий вершины v ₂ и v ₄, длины 6. Ему соответствует последовательность вершин v ₂, v ₅, v ₅, v ₆, v ₁, v ₅, v ₄. Заменяя ребро e ₅ на e ₇, получим пример замкнутого маршрута длины 6. Если все ребра, составляющие маршрут различны, то такой маршрут цепью, если она не замкнута, и циклом, если он замкнут. Множество ребер, которое можно упорядочить так, что оно образует цепь, называется неупорядоченной цепью, а множество ребер, образующих после упорядочения цикл, - неупорядоченным циклом. Например, множество ребер e ₃, e ₄, e ₇, e ₈ на рис. 6.6 образует неупорядоченную цепь, т. к. последовательность e ₄, e ₃, e ₈, e ₇, полученная упорядочением предыдущей последовательности, является цепью с соответствующей последовательностью вершин v ₅, v ₁, v ₆, v ₅, v ₂. Этой же неупорядоченной цепи можно поставить в соответствие другую цепь e ₈, e ₃, e ₄, e ₇ с соответствующей последовательностью вершин v ₅, v ₆, v ₁, v ₅, v ₂.

Рис.6.6 – Маршруты, цепи, циклы

Иногда важно различать разные способы упорядочения ребер при образовании цепей или циклов, в других случаях упорядочение не существует. Обе ситуации встречаются достаточно часто, поэтому введение различных терминов для упорядоченных и неупорядоченных последовательностей ребер вполне оправданно.

Если все n +1 вершин v ₀, v ₁, …, v _n различны (очевидно, что в этом случае ребра обязательно различны), то соответствующая цепь называется простой цепью, а соответствующее неупорядоченное множество ребер называется неупорядоченной простой цепью. Если v ₀ = v _n, но все остальные вершины различны, то последовательность ребер называется простым циклом, а соответствующее неупорядоченное множество ребер – неупорядоченным простым циклом. Заметим, что в геометрическом графе простые цепи образуют простые незамкнутые кривые (см. определение выше), а простые циклы – простые замкнутые кривые.