Маршруты, цепи и циклы
Рассматривая геометрический граф, можно зафиксировать некоторую вершину и, последовательно двигаясь по смежным ребрам к вершинам, прийти в другую вершину или вернуться в исходную. В геометрическом графе это означает, что мы непрерывным образом двигаемся по последовательности простых кривых. Последовательности ребер, по которым можно двигаться непрерывным образом, играют фундаментальную роль в теории графов. В частности, такие структуры, как цепи и циклы, в которых ни одно ребро не встречается дважды и которые мы определим ниже, будут постоянно встречаться во всех последующих главах. Перейдем теперь к формальным определениям.
Конечная последовательность ребер графа e1, e2, …, e n (не обязательно различных) называется маршрутом длины n, если существует последовательность v0, v1, …, v n из n+1 (не обязательно различных) вершин таких, что e i ~ (vi-1 & vi) для i = 1, 2, …, n .
Говорят, что маршрут замкнут, если v0 = v n, и не замкнут, если v0 ¹ v n.В последнем случае также говорят, что маршрут соединяет вершины v0 и v n. Заметим, что одно ребро можно рассматривать как маршрут длины 1.
Обращаясь к рис. 6.6, видим, что последовательность ребер e7, e1, e8, e3, e4, e5 образует незамкнутый маршрут, соединяющий вершины v2 и v4, длины 6. Ему соответствует последовательность вершин v2, v5, v5, v6, v1, v5, v4. Заменяя ребро e5 на e7, получим пример замкнутого маршрута длины 6. Если все ребра, составляющие маршрут различны, то такой маршрут цепью, если она не замкнута, и циклом, если он замкнут. Множество ребер, которое можно упорядочить так, что оно образует цепь, называется неупорядоченной цепью, а множество ребер, образующих после упорядочения цикл, - неупорядоченным циклом. Например, множество ребер e3, e4, e7, e8 на рис. 6.6 образует неупорядоченную цепь, т. к. последовательность e4, e3, e8, e7, полученная упорядочением предыдущей последовательности, является цепью с соответствующей последовательностью вершин v5, v1, v6, v5, v2 . Этой же неупорядоченной цепи можно поставить в соответствие другую цепь e8, e3, e4, e7 с соответствующей последовательностью вершин v5, v6, v1, v5, v2.
Рис.6.6 – Маршруты, цепи, циклы
Иногда важно различать разные способы упорядочения ребер при образовании цепей или циклов, в других случаях упорядочение не существует. Обе ситуации встречаются достаточно часто, поэтому введение различных терминов для упорядоченных и неупорядоченных последовательностей ребер вполне оправданно.
Если все n+1 вершин v0, v1, …, v n различны (очевидно, что в этом случае ребра обязательно различны), то соответствующая цепь называется простой цепью, а соответствующее неупорядоченное множество ребер называется неупорядоченной простой цепью. Если v0 = v n, но все остальные вершины различны, то последовательность ребер называется простым циклом, а соответствующее неупорядоченное множество ребер – неупорядоченным простым циклом. Заметим, что в геометрическом графе простые цепи образуют простые незамкнутые кривые (см. определение выше), а простые циклы – простые замкнутые кривые.