§ 2. Маршруты, циклы и связанность.

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

О п р е д е л е н и е.

1. Пусть – граф. Маршрутом длины в графе из в называется последовательность вершин (необязательно различных) таких, что , , а для всех Маршрут называется замкнутым, если . Маршрут называется цепью, если все его вершины различны. Замкнутая цепь называется циклом. Цикл называется простым циклом, если только , а остальные различны.

2. Если существует маршрут из в , , , то говорят, что w достижима из v.

3. Граф без циклов называется ациклическим. Циклы и длины циклов были определены для случая подстановок в § 4 гл. 3. Заметим, что понятие замкнутости, в сущности, соответствует своему названию.

О п р е д е л е н и е.

1. Граф называется связным, если каждая пара различных вершин может быть соединена маршрутом.

2. Деревом называется связный ациклический граф.

3. Корневым деревом называется дерево с выделенной вершиной, называемой корнем.

4. Остовным деревом для называется остовный подграф, являющийся древом.

В § 1 мы отметили, что вычисления с матрицей смежности обнаруживают важную информацию о природе графа. Следующие результаты являются примерами внутренних связей между алгеброй и топологией в теории графов.

В приведённой ниже теореме и ее следствиях степени вычисляются в M(n, Z), а не в M(n, B). Следовательно, в могут возникать числа больше, чем 1.

Теорема. Пусть A – матрица смежности графа и . Тогда есть число маршрутов длины k от до .

Доказательство. Будем использовать инструкцию по k. Для k=1 маршрут длины 1 как раз является ребром G. Следовательно, результат теоремы при k=1 вытекает из определения A. Пусть

, ,

Тогда

.

Пусть результат имеет место для k-1. Тогда, если - элементы матрицы , то – число маршрутов длины k-1 от до ; по определению - число маршрутов длины 1 от до . Следовательно, – число маршрутов длины k из к , где есть предпоследняя вершина маршрута.

От сюда следует, что

есть число маршрутов длины k от до . Это завершает доказательство. //

Следствие.

1. Маршрут от до в существует тогда и только тогда, когда -й элемент матрицы порядка :

не равен нулю.

2. Если не использовать условие , то требуемая матрица имеет вид

.

Доказательство.

а) Пусть – маршрут из в в G. Если не существует повторяющихся вершин, то (так как ) маршрут содержит не более n-1 ребер, и необходимое утверждение следует из теоремы.

Пусть существует повторяющаяся вершина. Тогда маршрут имеет вид

Замкнутый маршрут

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

б) Если разрешается , то существование маршрута из в влечет то, что существует последовательность . Если не существует повторяющихся вершин (за исключением, возможно, случая ). Тогда маршруты состоят из более чем n+1 вершин (не более n ребер). Следовательно, (i, j)-й элемент матрицы не равен нулю. Тогда при отсюда следует

//

Напомним, что для произвольного бинарного отношения R величина определялась как

,

и если при , то отсюда следует (с учетом § 1 гл. 6), что

.

Аналогично

.

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

Матрицу называют матрицей связи, связности или достижимости графа . Маршрут из к существует в G тогда и только тогда, когда (i, j)-й элемент из C равен 1. Граф G является связным тогда и только тогда, когда для всех .

Важные свойства отношения могут быть сформулированы следующим образом.

Предложение. - Отношение эквивалентности на V.

Доказательство. Так как по определению является рефлексивным замыканием R, то необходимо только проверить симметричность . Выполнение влечет существование маршрута от v к w в G, т.е.

Следовательно,

Таким образом,

есть маршрут из w в v в G, откуда . //

Отношение определяет важный класс подграфов, который сейчас будет определен. Будут также даны некоторые сопутствующие понятия; они будут важны в дальнейшем, когда будут обсуждаться «пересечения» графа.

Определение. Пусть – разбиение графа, определяемое отношением . Тогда говорят, что p – число связанности G. Подграфы , порожденные классами эквивалентности, называют компонентами связности графа G.

Лесом называется граф, в котором каждая связная компонента является деревом. Остовный лес для графа – это совокупность вершин разъединенных деревьев таких, что и для всех i. (Разъединенность вершин означает, что при .)

Рисунок 7.6. иллюстрирует вышеупомянутые понятия для графа при p=2.

Упражнение 7.2.

1. Пусть , где

Используя матрицу смежности G, определить:

1. число маршрутов длины 2 из в ;

2. число маршрутов длины 3 из в ;

3. является ли G связным.

2. Изобразить остовные деревья для графов из упражнения 7.1. 3

3. Дать матричную характеристику ацикличности в графе.

Р ис. 7.6