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

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

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

Конечная последовательность ребер графа (не обязательно различных) называется маршрутом длины если существует последовательность из (не обязательно различных) вершин таких, что

Говорят, что маршрут замкнут, если и не замкнут, если В последнем случае также говорят, что маршрут соединяет вершины Заметим, что одно ребро можно рассматривать как маршрут длины Обращаясь к рис. 1.6, видим, что последовательность ребер образует незамкнутый маршрут, соединяющий вершины длины .

Рис. 1.6.

Ему соответствует последовательность вершин Заменяя ребро на получим пример замкнутого маршрута длины 6. Если все ребра, составляющие маршрут различны, то такой маршрут называется цепыо, если она не замкнута, и циклом, если он замкнут. Множество ребер, которое можно упорядочить так, что оно образует цепь, называется неупорядоченной цепью, а множество ребер, образующих после упорядочения цикл, — неупорядоченным циклом. Например множество

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

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

Если все вершин различны (очевидно, что в этом случае ребра обязательно различны), то соответствующая цепь называется простой цепью, а соответствующее неупорядоченное множество ребер называется неупорядоченной простой цепью. Если но все остальные вершины различны, то последовательность ребер называется простым циклом, а соответствующее неупорядоченное множество ребер — неупорядоченным простым циклом. Заметим, что в геометрическом графе простые цепи образуют простые незамкнутые кривые (см. определение выше), а простые циклы — простые замкнутые кривые.

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

Опишите процесс информационного взаимодействия в такой организации, пользуясь введенными выше понятиями.

Упражнения

(см. скан)

(см. скан)