Лекции Просолупов

( )

Тогда элемент , , стоящий на пересечении -той строки и -того столбца матрицы ( ) = ( ( )) , равен числу маршрутов из вершины в вершину

длины , = 1, , = 1, . В случае ориентированного графа имеются в виду ориентированные маршруты.

Доказательство. Докажем по индукции. Для степени 1 утверждение верно: элемент матрицы смежности равен числу ребер из в .

Предположим, что формула верна для степени − 1, где > 1. Рассмотрим , -тый элемент ( ) = −1( ) · ( ):

Просуммировав в формуле (*) это произведение по всем возможным промежуточным вершинам , мы получим число всех маршрутов из в длины , что и требовалось

доказать.

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

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

Замечание 76.6 . Можно заметить, что изоморфным графам могут соответствовать разные матрицы смежности. Но это различие не произвольно. Изоморфные графы по сути отличаются порядком нумерации вершин. Этому порядку соответствует порядок нумерации строк и столбцов матрицы смежности. Таким образом, матрицы смежности для изоморфных графов отличаются друг от друга одинаковой перестановкой строк и столбцов.

181

Матрица инцидентности

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

| ( )| × | ( )|, где строки соответствуют вершинам, а столбцы — ребрам графа.

В каждом столбце матрицы инцидентности графа без петель ровно 2 единицы. Сумма по -той строке равна степени вершины .

Сумма всех элементов матрицы инцидентности неориентированного графа без петель равна удвоенному числу его ребер:

∑∑

, ( ) = 2| ( )|.

=1 =1

Пример 76.7 . Для обыкновенного графа на рисунке 45 матрица инцидентности может выглядеть следующим образом

0 1 1 1 0

( ) = 0 0 0 1 1

Для определения матрицы инцидентности ориентированного графа потребуется

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

182

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

Матрицы инцидентности изоморфных графов отличаются друг от друга еще и перестановкой строк.

Списки смежности и список ребер

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

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

Пример 76.10 . Например, для обыкновенного графа на рисунке 36 d) списки смежности будут иметь вид

1: 2, 4, 6 2: 1, 3, 5 3: 2, 4, 6 4: 1, 3, 5 5: 2, 4, 6 6: 1, 3, 5 и список ребер —

(1,2), (1,4), (1,6), (2,3), (2,5), (3,4), (3,6), (4,5), (5,6).

А для ориентированного графа на рисунке 34 b) списки смежности будут иметь вид

a: a, b, d b: c, e c: f, g d: g e: d, e, f f: c, f, g g: d и список ребер —

(a,a), (a,b), (a,d), (b,c), (b,e), (c,f), (c,g), (d,g), (e,d), (e,e), (e,f), (f,c), (f,f), (f,g), (g,d).

183

Лекция 29. Деревья и обходы графа

§77. Деревья

Определение 77.1 . Деревом называется связный граф без циклов.

Граф без циклов называется лесом. Каждая компонента связности леса является деревом.

Теорема 77.2 . Пусть = ( , ), | | = , | | = . Тогда следующие утверждения эквивалентны:

1)— связный граф без циклов (дерево),

2)— граф без циклов и = − 1,

3)— связный граф и = − 1.

Доказательство. 1) 2) Необходимо доказать, что = − 1. Докажем по

индукции. База индукции очевидна: Дерево с 1 вершиной не имеет ребер и соотношение выполняется.

Пусть соотношение выполняется для любого дерева не более чем с −1 вершиной. Рассмотрим дерево с вершинами, > 1.

Выберем произвольное ребро = ( , ) ( ). Рассмотрим граф − . Этот граф не может быть связным. Действительно, если бы граф − был связным, в нем был бы маршрут между вершинами и . Этот маршрут вместе с ребром образовывал бы цикл в графе .

Значит в графе − две компоненты связности 1 и 2. Обе они являются связными графами без циклов и для них выполняется индукционное предположение. Значит 1 = 1 − 1, 2 = 2 − 1 и для исходного графа : = 1 + 2 + 1 =

1 − 1 + 2 − 1 + 1 = − 1.

2) 3) Пусть граф не имеет циклов и число ребер на единицу меньше числа вершин. Докажем, что граф связный.

Пусть граф не связен. Пусть 1, 2, ..., все компоненты связности . Тогда каждый граф связный граф без циклов — дерево.

Мы уже доказали утверждение 1) 2), так что можем этим пользоваться. Следовательно для каждого из графов верно ( ) = ( ) − 1. Таким образом

Но нам известно, что число ребер в графе на единицу меньше числа вершин, то есть= 1. Следовательно в графе может быть только одна компонента связности.

184

3) 1) Пусть граф связный и число ребер на единицу меньше числа вершин. Докажем, что граф не имеет циклов.

Пусть в графе есть циклы. Рассмотрим произвольное ребро 1, которое принадлежит какому-то циклу графа . Граф − 1 связен, поскольку между любыми двумя вершинами в цикле существовало как минимум две цепи.

Можем повторять процесс удаления ребер до тех пор, пока в графе − 1 − 2 −

... − остаются циклы.

Рассмотрим граф = − 1 − 2 − ... − , полученный после размыкания всех циклов графа . Граф связный и в нем нет циклов. Еще раз воспользуемся доказанным переходом 1) 2):

( ) = ( ) − 1 = ( ) − 1 = ( ),

то есть после удаления ребер число ребер в графе не изменилось. Противоречие вызвано предположением, что в графе есть циклы. Следовательно, циклов нет,

что и требовалось доказать.

§78. Эйлеровы и гамильтоновы графы

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

Рисунок 47: Задача о Кенигсбергских мостах

в 1736 году Леонардом Эйлером. Принято считать, что именно с этой задачи начала свое существование теория графов.

185

Определение 78.1 . Эйлеровым циклом в графе называется цикл, который проходит через все ребра графа ровно по одному разу.

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

Для проверки графа на эйлеровость есть удобный критерий.

Лемма 78.3 . Пусть граф является эйлеровым графом. Тогда степени всех вершин графа четны.

графа причем каждое ровно один раз.

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

графа равна удвоенному числу проходов цикла через вершину . Следовательно степень четна.

Теорема 78.4 . Пусть — связный граф. Тогда в графе существует эйлеров цикл тогда и только тогда, когда степени всех вершин графа четны.

Доказательство. Необходимость следует из леммы 78.3.

Достаточность. Пусть ( ): deg — четна. С помощью двухшагового процесса разобьем все ребра графа на циклы.

1) Начнем с произвольной вершины ( ) строить цепь переходя по любым

ребрам от вершины к вершине. Поскольку степени вершин четны, войдя в некоторую вершину по одному ребру мы обязательно можем из нее выйти по второму. Таким образом, мы точно можем обходить вершины, пока не вернемся в исходную вершину. Так мы построили некоторый цикл 1 = 1( ). По лемме 78.3, степени всех

вершин в 1( ) четны.

2) Удалим из все ребра, входящие в цикл 1( ). Поскольку степени всех вершин

ви 1( ) четны, то и в графе − ( 1( )) степень каждой вершины четна. Дальше мы можем перейти к пункту 1) и искать цикл 2 в графе − ( 1( )).

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

= ( , ( , 2 ), 2 , ( 2 , 3 ), ..., , ( , ), ),

186

= ( , ( , 2 ), 2 , ( 2 , 3 ), ..., , ( , ), ).

Объединим эти циклы в точке и получим новый цикл

, = ( , ( , 2 ), 2 , ( 2 , 3 ), ..., , ( , ), , ( , 2 ), 2 , ( 2 , 3 ), ..., , ( , ), ).

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

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

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

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

187

Лекция 30. Минимальное остовное дерево и деревья поиска

§79. Остов минимального веса

Задача 79.1 . Пусть имеется населенных пунктов и между некоторыми

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

Сформулируем задачу на языке графов.

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

: → R+.

Будем считать весом любого подграфа графа суммарный вес его ребер:

∑

( ) = ( ).

( )

Требуется найти такой связный остовной подграф 1 = ( , 1), чтобы его вес( 1) был минимальным из весов всех связных остовных подграфов.

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

Пример минимального остовного дерева для взвешенного графа приведен на рисунке 48.

Приведем алгоритм решения этой задачи.

Алгоритм 79.3 (Алгоритм Краскала).

Пусть = ( , ), | | = , : → R+.

1)1 = arg min ( ).

2)= 1; = ( , ) = + 1.

3)( < − 1){

+1 = + +1;

= + 1;

}

188

8

8

Рисунок 48: Остов минимального веса

На каждом шаге этого алгоритма мы выбираем самое "легкое" ребро графа, при добавлении которого у нас не образуется циклов вместе с уже выбранными ранее ребрами. Процесс завершается, когда мы выберем − 1 ребро. Чтобы убедиться,

что этот алгоритм решает задачу об остове минимального веса, нужно показать, что 1) мы действительно можем довести процесс до конца (всегда найдется такое − 1

ребро); 2) построенный граф будет деревом; 3) это дерево будет минимальным по весу из всех остовных деревьев .

Пусть граф — связный граф и : → R+ — весовая функция. Тогда алгоритм Краскала строит минимальное остовное дерево.

Доказательство. 1) Во-первых, покажем, что алгоритм всегда позволяет построить граф −1.

Пусть на некотором шаге ( < − 1) мы не смогли выбрать следующее ребро+1. Значит не существует ни одного такого ребра , что в + нет циклов.

Граф не имеет циклов по построению. Если бы граф был связен, то по теореме 77.2 в нем было бы − 1 ребро. Так как < − 1, граф не является связным.

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

По нашему предположению, + будет иметь цикл. Этот цикл должен проходить по ребру (иначе цикл был бы и в графе ). Но тогда этот цикл состоит из маршрута между вершинами и и ребра ( , ). То есть в графе должен

189

быть маршрут между вершинами и и они обе принадлежать одной компоненте связности ?!

2) Покажем, что построенный в алгоритме граф −1 есть дерево. Действительно, выбирая каждое ребро мы проверяем, что у нас не должно

появляться циклов. Когда мы выберем − 1 ребро, по теореме 77.2 они образуют связный граф без циклов — остовное дерево графа .

3) Наконец докажем, что построено дерево минимального веса.

Пусть min( ) — вес минимального остовного дерева графа . Пусть

= { | = ( , ( )) — остовное дерево графа , ( ) = min( )}.

Пусть * остовное дерево минимального веса, которое имеет наибольшее число общих ребер с графом −1:

* = arg max | ( −1) ∩ ( )|.

Будем доказывать от противного. Пусть −1 не является минимальным остовным деревом. Тогда * не совпадает с −1.

Пусть — первое ребро в −1, которого нет в *:

= ( , ) ( −1) : / ( *), и < ( *).

Рассмотрим граф * + . В нем обязательно есть цикл , так как * уже был связным графом — имел маршрут между вершинами и . Так как в графе −1

Посмотрим с другой стороны. На -том шаге алгоритма мы выбирали ребро

как ребро минимального веса из всех невыбранных ребер, не образующих циклов с ребрами , < . Все ребра , < входят и в дерево *, а значит и ребро ′

не образует с ними цикла. Таким образом, на -том шаге алгоритма ребро ′ было кандидатом на выбор и было бы выбрано, если бы ( ′) < ( ). Следовательно

( * + − ′) = ( *) + ( ) − ( ′) = ( *) = min( ).

190