Алгоритмические задачи на графах

• Название: Алгоритмические задачи на графах
• Дата: 29.09.2021
• Размер: 1.07 Mb.
• Имя файла: Alg-graphs-full (1).pdf
• Тип: Учебное пособие; #238917
• страница: 1 из 12

Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования
Тверской государственный университет
Кафедра информатики
М.И. Дехтярь
АЛГОРИТМИЧЕСКИЕ
ЗАДАЧИ
НА ГРАФАХ
Учебное пособие
Тверь  2012

Содержание Основные понятия 2 Представления графов 2.1 Матрица (таблица) смежности . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7 2.2 Матрица (таблица) инцидентности . . . . . . . . . . . . . . . . . . . . . . . . . . .
7 2.3 Списки смежности . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8 2.3.1 Графы с ограниченной полустепенью исхода . . . . . . . . . . . . . . . . .
8 2.3.2 Произвольные графы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8 2.4 Задачи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
10 3 Неориентированные и ориентированные деревья 3.1 Основные определения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
12 3.2 Представления деревьев . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
15 3.2.1 Сылка на вершину-отца . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
15 3.2.2 Скобочное представление . . . . . . . . . . . . . . . . . . . . . . . . . . . .
15 3.2.3 Представление множеством путей . . . . . . . . . . . . . . . . . . . . . . .
16 3.2.4 Стандартное представление бинарного дерева . . . . . . . . . . . . . . . .
16 3.2.5 Представление бинарного дерева с помощью массива . . . . . . . . . . . .
16 3.2.6 Представление произвольного дерева с помощью бинарного . . . . . . . .
17 3.3 Деревья и формулы (выражения) . . . . . . . . . . . . . . . . . . . . . . . . . . . .
17 3.4 Обходы деревьев . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
19 3.5 Задачи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
22 Минимальное остовное дерево Алгоритм Крускала . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
23 4.2 Задачи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
26 Алгоритмы обхода графов Поиск в глубину на неориентированном графе и задача о лабиринте . . . . . . .
27 Поиск в ширину на неориентированном графе . . . . . . . . . . . . . . . . . . . .
31 Двусвязные компоненты неориентированных графов . . . . . . . . . . . . . . . .
32 5.4 Компоненты сильной связности и базы ориентированного графа . . . . . . . . .
36 Задачи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
40 6 Задачи о путях на графе 6.1 Достижимость и транзитивное замыкание графа . . . . . . . . . . . . . . . . . . .
41 6.1.1 Кратчайшие пути между всеми парами вершин . . . . . . . . . . . . . . .
44 6.2 Задача о кратчайших путях из одного источника . . . . . . . . . . . . . . . . . .
44 6.2.1 Алгоритм Дейкстры . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
45 6.2.2 О реализации алгоритма Дейкстры . . . . . . . . . . . . . . . . . . . . . .
47 6.2.3 Алгоритм Беллмана-Форда . . . . . . . . . . . . . . . . . . . . . . . . . . .
50 6.2.4 Кратчайшие пути в ациклических графах . . . . . . . . . . . . . . . . . . .
52 6.3 Задачи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
54 2

Потоки в сетях 7.1 Потоки и разрезы. Алгоритм Форда-Фалкерсона . . . . . . . . . . . . . . . . . . .
56 7.2 Алгоритм построения максимального потока за кубическое время . . . . . . . . .
61 Сети с единичными пропускными способностями . . . . . . . . . . . . . . . . . .
65 Максимальные паросочетания в двудольных графах . . . . . . . . . . . . . . . .
66 7.4.1
Паросочетания в общих графах . . . . . . . . . . . . . . . . . . . . . . . .
69 Задачи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
69 полные задачи для графов 8.1 Полиномиальная сводимость и полные задачи . . . . . . . . . . . . . . . . . .
72 8.2 Полиномиальная разрешимость выполнимости 2-КНФ . . . . . . . . . . . . . . .
73 8.3 Клика, независимое множество, вершинное покрытие . . . . . . . . . . . . . . . .
75 8.4 Гамильтонов цикл . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
78 Задача коммивояжера . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
81 8.6 Раскраска вершин графа . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
83 8.7 Задачи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
87 9 Что делать с полными проблемами Аппроксимация для задачи ВЕРШИННОЕ ПОКРЫТИЕ . . . . . . . . . . . . .
89 Аппроксимации для задачи коммивояжера . . . . . . . . . . . . . . . . . . . . . .
91 Метод ветвей и границ для задачи коммивояжера . . . . . . . . . . . . . . . .
94 9.4 Задачи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
97 10 Применение графов в анализе социальных сетй
99 10.1 Социальные сети . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
99 10.2 Параметры центральности акторов . . . . . . . . . . . . . . . . . . . . . . . . . . 100 10.2.1 Близкая центральность (closeness centrality (Sabidussi, 1966)) . . . . . . . 100 10.2.2 Срединная центральность (Betweenness Centrality) . . . . . . . . . . . . . . 101 10.2.3 Алгоритмы вычисления центральности . . . . . . . . . . . . . . . . . . . . 101 10.3 Престижность . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104 10.3.1 Средняя престижность (Proximity Prestige) . . . . . . . . . . . . . . . . . . 104 10.3.2 Ранжированный престиж (Rank Prestige) . . . . . . . . . . . . . . . . . . . 105 10.4 Ранжирование интернет-страниц. Алгоритм PageRank . . . . . . . . . . . . . . . 105 10.5 Обнаружение сообществ (Community Discovery) . . . . . . . . . . . . . . . . . . . 108 10.6 Двудольное ядро сообществ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109 10.6.1 Выявление двудольных ядер . . . . . . . . . . . . . . . . . . . . . . . . . . 109 10.6.2 Сообщества максимального потока . . . . . . . . . . . . . . . . . . . . . . . 110 10.7 Задачи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Список литературы
115
Предметный указатель 3

Введение
Мы часто сталкиваемся с задачами, в условиях которых заданы некоторые объекты и между некоторыми их парами имеются определенные связи. Если объекты изобразить точками
(вершинами), а связи  линиями (ребрами, соединяющими соответствующие пары точек, то получится рисунок, называемый графом. Историю теории графов принято исчислять с 1736 г.,
когда Эйлер исследовал задачу о кенигсберских мостах построить в графе циклический путь,
проходящий по одному разу через каждое ребро. В середине го века Гамильтон заинтересовался задачей построения циклического пути, проходящего по одному разу через каждую вершину графа. К тому же времени относится использование графов для анализа электрических цепей (Кирхгоф) и химических молекул (Кэли). Начало развития современной теории графов относится км годам го столетия. Графы нашли многочисленные применения в электротехнике, электронике, биологии, экономике, программировании ив других областях.
Настоящее пособие написано по материалам курсов Проектирование эффективных алгоритмов и Алгоритмы на графах, которые автор неоднократно в 1990-2012гг. читал в Тверском государственном университете. Основное внимание уделено рассмотрению широко используемых в различных приложениях типовых алгоритмических задач, таких, как представления графов, отношение достижимости и транзитивное замыкание графа, компоненты сильной связности ориентированного графа и его базы, деревья и их обходы, минимальные остовные деревья,
поиск в глубину, поиск кратчайших путей и потоки в транспортных сетях. Рассмотрены также многие сложные (полные) задачи на графах и возможные подходы к их решению. В последней главе продемонстрировано применение теории графов к анализу социальных сетей. Каждая глава завершается разделом с задачами, которые могут служить материалом для проведения практических занятий и домашних заданий. Ряд задач содержат дополнительный материал, по тем или иным причинам не вошедший в основной текст. Список литературы заведомо неполон,
он включает лишь учебники, монографии и статьи, непосредственно использованные при написании этого пособия. В них можно найти дальнейшие ссылки на многочисленные источники,
посвященные алгоритмам на графах Основные понятия
Приведем основные определения теории графов.
Определение 1. Ориентированный граф  это пара (V, E), где V  конечное множество вершин (узлов, точек) графа, а E  некоторое множество пар вершин, те. подмножество множества V Чили бинарное отношение на V . Элементы E называют ребрами (дугами,
стрелками, связями. Для ребра e = (u, v) ? E вершина u называется началом e, а вершина v
 концом e, говорят, что ребро e ведет изв Неориентированный граф G = (V, E)  это ориентированный графу которого для каждого ребра (u, v) ? E имеется противоположное ребро (v, u) ? E, те. отношение E симметрично. Такая пара (u, v), (v, u) называется неориентированным ребром. Для его задания можно использовать обозначение для множества концов {u, v}, но чаще используется указание одной из пар в круглых скобках. Если e = (u, v) ? E, то вершины u и v называются смежными в G, а ребро e и эти вершины называются инцидентными. Степенью вершины в неориентированном графе называется число смежных с ней вершин. Вершина степени называется изолированной.
В ориентированном графе полустепень исхода вершины  это число исходящих из нее ребер,
а полустепень захода  это число входящих в данную вершину ребер.
1
Интересно, что несмотря на внешнюю похожесть задача Эйлера имеет простое эффективное решение (см.
задачу 2.13), а задача Гамильтона в общем случае эффективно не решается (см. раздел 8.4)
4

Заметим, что в ориентированном графе может быть ребро вида (u, u), называемое петлей,
а в неориентированном петель не бывает.
Пример 1. На рис. 1 приведены примеры ориентированного графа G
1
= (V
1
, и неориентированного графа G
2
= (V
2
, E
2
)
. Здесь V
1
= {a, b, c, d}, E
1
= {(a, b), (a, c), (b, b), (b, d), (d, a)}
,
V
2
= {a, b, c, d}, E
2
= {(a, b), (a, c), (a, d), (b, d)}
. В графе ребро (b, b) является петлей, полу- степень исхода вершины a равна 2, а полустепень захода для нее равна 1. В графе степень вершины a равна 3, вершин b и d  2, вершины c  1, а вершины e  0, те. вершина e является изолированной b
c d
P
i
-
?
?
@
@
@
@
@
I
G
2
:










a b
c Рис. 1: Ориентированный граф и неориентированный граф Части графов называются подграфами.
Определение 2. Граф G
1
= (V
1
, называется подграфом графа G = (V, E), если V
1
? и E
1
? Во многих приложениях с вершинами и ребрами графов связывается некоторая дополнительная информация. Обычно она представляется с помощью функций разметки вершин и ребер.
Определение 3. Размеченный граф  это ориентированный или неориентированный граф = (V, E)
, снабженный одной или двумя функциями разметки вида l : V ? M и c : E ? где M и L  множества меток вершин и ребер, соответственно.
Упорядоченный граф  это размеченный граф G = (V, E), в котором ребра, выходящие из каждой вершины v ? V , упорядочены, те. помечены номерами 1, . . . , k v
, где k v

полустепень исхода v, те. k v
= |{w | (v, w) ? В качестве множества меток ребер L часто выступают числа, задающие веса, длины,
стоимости ребер. Графы с такой разметкой часто называют взвешенными.
Во многих задачах, использующих графы с разметкой ребер, удобно допускать несколько ребер между одной парой вершин.
Определение 4. Ориентированный мультиграф  это пара (V, E), где V  конечное множество вершин (узлов, точек) графа, а множество ребер (дуг) E  это некоторое мультимножество пар вершин, те. множество, в которое каждый элемент (ребро) может входить несколько раз.
Обычно "параллельные"ребра в размеченных мультиграфах различаются своими метками.
Неориентированный граф G = (V, E) называется полным, если E = V Ч V \ {(v, v) | v ? V те. любые две его вершины соединены ребром. Полный вершинный граф часто обозначается как K
n
. Наследующем рисунке показаны первые пять полных графов

K
1
:
t
K
2
:
t t
K
3
:
t t
t
@
@
K
4
: t t
@
@
@
@
t t
K
5
:
t t
t t
t
Q
Q
Q
Q
Q
Q






A
A
A
A
A
A
A
A
















a a
a a
a a
a a
a Рис. 2: Полные графы K
1
? Во многих случаях естественно не различать графы, отличающиеся лишь именами (порядком) вершин.
Определение 5. Изоморфизм графов. Два графа G
1
= (V
1
, и G
2
= (V
2
, называются изоморфными, если между их вершинами существует взаимно однозначное соответствие такое, что для любой пары вершин u, v из ребро (u, v) ? ребро, ?(v)) ? Для изоморфизма размеченных графов требуется также совпадение меток соответствующих вершин : l
1
(v) = l
2
(?(v))
и/или ребер c
1
((u, v)) = c
2
((?(u), Многие приложения графов связаны с изучением путей между их вершинами.
Определение 6. Путь в ориентированном или неориентированном графе  это последовательность ребер вида (v
1
, v
2
), (v
2
, v
3
), . . . , (v n?1
, v n
)
. Этот путь ведет изначальной вершины в конечную вершину v и имеет длину n ? 1. В этом случае будем говорить, что v достижима из v
1
. Будем считать, что каждая вершина достижима сама из себя путем длины. Путь можно также определять как соответствующую последовательность вершин, v
2
, v
3
, . . . , v n?1
, v где (v i
, v i+1
) ? при i = 1, 2, . . . , n ? Путь назывется простым, если все ребра и все вершины на нем, кроме, быть может,
первой и последней, различны.
Циклом в ориентированном графе называется путь, в котором начальная вершина совпадает с конечной и который содержит хотя бы одно ребро. Цикл (v
1
, v
2
, . . . , v n?1
, v n
= называется простым, если в нем нет одинаковых вершин, кроме первой и последней, т.е.
если все вершины v
2
, . . . , v n?1
различны.
В неориентированном графе путь (v
1
, v
2
, . . . , v n?1
, v n
= называется циклом, если n и все ребра (v i
, v i+1
)
различны.
Из последнего определения следует, что длина цикла в неориентированном графе не меньше Если в графе нет циклов, то он называется ациклическим.
Неориентированный граф называется связным, если любая пара вершин в нем соединена путем. При выполнении такого же условия ориентированный граф называется сильно связным или двусвязным
Максимальный связный подграф неориентированного графа называется его связной компонентой. Максимальный сильно связный подграф ориентированного графа называется его сильно связной компонентой.
Следующее утверждение непосредственно следует из определений.
Лемма 1.1. Если в графе G (ориентированном или неориентированном) имеется путь из вершины u в вершину v, тов нем имеется и простой путь изв Представления графов
Из определения графа следует, что каждый граф G = (V, E) можно задать, непосредственно перечислив его множество вершин V и множество ребер E. Однако такое представление неудобно для решения многих задач о графах. Например, чтобы проверить наличие ребра между двумя вершинами, придется, вообще говоря, просмотреть все множество E. Хорошее представление, по крайней мере, должно позволить легко переходить от вершины к ее соседу и перечислять всех ее соседей.
В этом параграфе мы рассмотрим три разных способа представления графов, которые более эффективны при решении типичных для теории графов задач Матрица (таблица) смежности
Определение 7. Матрицей смежности ориентированного (или неориентированного) графа = (V, с n вершинами V = {v
1
, . . . , v называется булева матрица размера n Ч n с элементами если (v i
, v j
) ? в противном случае
Это представление позволяет легко проверять наличие ребер между заданными парами вершин. Для поиска всех соседей, в которые ведут ребра из вершины v i
, необходимо просмотреть соответствующую ей ю строку матрицы A
G
, а чтобы найти вершины, из которых ребра идут в v i
, необходимо просмотреть ее i-ый столбец. Требуемая для память  по порядку битов не может быть уменьшена для графов, у которых много ребер. Но для разреженных графов с числом ребер существенно меньшим по порядку в матрице смежности много ненужных
нулей. Для таких графов более эффективными могут оказаться другие представления Матрица (таблица) инцидентности
Определение 8. Матрицей инцидентности ориентированного (или неориентированного)
графа G = (V, E) с n вершинами V = {v
1
, . . . , v и m ребрами E = {e
1
, . . . , e называется матрица размера n Ч m с элементами если для некоторого k ребро e j
= (v i
, v если для некоторого k ребро e j
= (v k
, v если ребро e j
= (v i
, v в остальных случаях.
Таким образом, в матрице инцидентности любому ребру e j
= (v i
, v соответствует j- ый столбец, в котором вой строке стоит 1, а вой. Ребра-петли выделяются числом. Для проверки наличия ребра между двумя вершинами v и v требуется просмотреть ю и k-ую строки B
G
, поиск всех соседей вершины требует просмотра соответствующей строки.
Если m >> n, то это требует существенно больше времени, чем при использовании матрицы смежности. Поэтому при практическом решении задач на графах матрица инцидентности почти не используется

2.3 Списки смежности
Определение 9. Пусть G = (V, E)  ориентированный граф, v  вершина из V . Список смежности L
v для вершины v включает все смежные с ней вершины, те w
1
, . . . , w k
, где {w
1
, . . . , w k
} = {w | (v, w) ? Представление графа G = (V, E) c n вершинами V = {v
1
, . . . , v с помощью списков смежности состоит из списков смежности всех вершин L
v
1
, L
v
2
, . . . , L
v Размер этого представления сравним с суммой числа вершин и ребер графа. Оно позволяет легко переходить по ребрам от вершины к ее соседям. В программах списки смежности представляются массивами или списковыми структурами, которые легко реализуются во всех языках программирования.
Рассмотрим некоторые представления списков смежности для графов с ограниченной по- лустепенью исхода и для произвольных графов Графы с ограниченной полустепенью исхода
Пусть G = (V, E)  граф c n вершинами V = {v
1
, . . . , v n
}
, в котором полустепень исхода у каждой вершины ограничена числом t, те. для каждой вершины v ее список смежности i
= v j
1
, . . . , v имеет длину k(i) ? Такой граф G можно представить с помощью t одномерных целочисленных массивов
СОСЕД1, СОСЕД, . . . , СОСЕД t длины n каждый, таких что СОСЕД = j для всех ? i ? n и 1 ? r ? k(i). При r > k(i) можно положить СОСЕД = 0. Для некоторых задач также полезно хранить для каждой вершины информацию о числе соседей, например, в массиве СОСЕДИ размера n: СОСЕДИ = k(i). Это представление достаточно компактно и эффективно, если степени исхода большинства вершин равны t или близки к этому числу ив процессе работы с графом он не изменяется, в частности, не меняется множество его вершин,
т.е. не требуется динамически перестраивать массивы) Если же при работе с графом он может сильно изменяться, то более эффективным является представление с помощью списочной структуры, элементы которой являются записями типа ВЕРШИНА = (Номер, ЧислоСоседей, Сосед, . . . , Сосед, где для элемента, представляющего вершину v поле Номер равно i, поле ЧислоСоседей содержит k(i), и каждое поле Сосед ? r ? содержит ссылку на элемент, представляющий вершину v j
r
. Такое представление позволяет производить локальные изменения графа (удаление и вставку вершины) за время Произвольные графы
Пусть G = (V, E)  граф c n вершинами V = {v
1
, . . . , v и полустепени исхода у вершин достаточно различны, например имеется несколько вершин с большим числом соседей, ау остальных их немного. В таком случае граф можно представить с помощью списковой структуры следующего вида:
все вершины графа связаны в линейный список с элементами-записями типа ВЕРШИНА Номер, Соседи, Следующая. Здесь поле Следующая содержит ссылку наследующую вершину, а поле Соседи содержит ссылку на начало списка соседей данной вершины. Список соседей состоит из элементов-записей типа СОСЕД = ( Сосед, Следующий_Сосед), в которых Сосед это ссылка на элемент в списке вершин, являющийся соседом данной вершины, а Следующий Сосед указывает наследующий элемент в списке соседей.
Пример 2. Рассмотрим следующий граф G = (V, E):
V = {v
1
, v
2
, v
3
, v
4
, v
5
, v
6
}
,
8

E = {e
1
= (v
1
, v
3
), e
2
= (v
3
, v
2
), e
3
= (v
4
, v
1
), e
4
= (v
4
, v
5
), e
5
= (v
5
, v
3
), e
6
= (v
5
, v
6
), e
7
=
(v
6
, v
6
), e
8
= (v
2
, v
1
)}
. Он показан на рис t
t t
t t
1 2
3 4
5 Рис. 3: Граф Построим для него определенные выше представления) Матрица смежности 0
1 0
0 0
1 0
0 0
0 0
0 1
0 0
0 0
1 0
0 0
1 0
0 0
1 0
0 1
0 0
0 0
0 1
?
?
?
?
?
?
?
?
2) Матрица инцидентности.
B
G
=
?
?
?
?
?
?
?
?
1 0
?1 0
0 0
0
?1 0
?1 0
0 0
0 0
1
?1 1
0 0
?1 0
0 0
0 0
1 1
0 0
0 0
0 0
0
?1 1
1 0
0 0
0 0
0 0
?1 2
0
?
?
?
?
?
?
?
?
3) Списки смежности v
3
;
L
v
4
: v
1
, v
5
;
L
v
2
: v
1
;
L
v
5
: v
3
, v
6
;
L
v
3
: v
2
;
L
v
6
: v
6 4) Реализация списков смежности с помощью массивов.
Заметим, что полустепень исхода у вершин графа G не превосходит 2. Поэтому он может быть представлен с помощью двух массивов СОСЕДИ и СОСЕДИ как это показано в следующей таблице.
Вершины:
1 2 3
4 5 СОСЕДИ 3 1 2 1 3 СОСЕДИ 0 0 0 5 6 Таблица 1: Представление графа G с помощью массивов) Реализация списков смежности с помощью списков при фиксированном числе соседей показана на рис. 4.
6) При сильно различающихся степенях вершин граф представляется с помощью списков двух типов ВЕРШИНА и СОСЕД. Это представление G показано на рис. 5.
9

1 3
2 4
5 6
Ч
Ч
Ч
Ч
?
?
?
?
6
?
6 Рис. 4: Представление графа G с помощью списков (полустепень исхода t ? 2 )
-
-
-
-
-
-
-
?
?
?
?
?
?
1 2
3 4
5 6
Ч
Ч
Ч
Ч
Ч
Ч
Ч
Ч
6
?
?
6
?
?
?
6
ВЕРШИНЫ:
СОСЕДИ:
Рис. 5: Общее представление графа G с помощью списков типа ВЕРШИНА и СОСЕД Задачи
Задача 2.1. Докажите, что во всяком ациклическом ориентированном графе имеется хотя бы одна вершина, из которой не выходят ребра, тес полустепенью исхода 0, и хотя бы одна вершина, в которую не входят ребра, тес полустепенью захода Задача 2.2. Докажите, что, если полустепени захода у всех вершин ориентированного графа больше 0, тов этом графе имеется цикл.
Задача 2.3. Докажите, что сумма степеней всех вершин произвольного неориентированного графа четна.
У этой задачи имеется популярная интерпретация доказать, что общее число рукопожатий, которыми обменялись люди, пришедшие на вечеринку, всегда четно.
Задача 2.4. Докажите, что в неориентированном графе число вершин нечетной степени всегда четно.
Задача 2.5. Перечислите все неизоморфные неориентированные графы, у которых не более четырех вершин.
Задача 2.6. Докажите, что в любой группе из 6 человек есть трое попарно знакомых или трое попарно незнакомых.
Задача 2.7. Докажите, что неориентированный связный граф остается связным после удаления некоторого ребра ? это ребро принадлежит некоторому циклу.
Задача 2.8. Докажите, что неориентированный связный граф с n вершинами а) содержит не менее n ? 1 ребер,
б) если содержит больше n ? 1 ребер, то имеет по крайней мере хоть один цикл.
Задача 2.9. Докажите, что, если в неориентированном графе (без петель) имеется ровно две вершины нечетной степени, то они связаны путем.
Задача 2.10. Докажите, что неориентированный граф G = (V, E) связен ? для каждого разбиения V = V
1
? с непустыми и существует ребро, соединяющее с Задача 2.11. Докажите, что в связном неориентированном графе любые два простых пути максимальной длины имеют общую вершину

Задача 2.12. Предложите алгоритмы для следующих преобразований представлений графа = (V, с n вершинами и m ребрами и оцените их сложность) Преобразовать матрицу смежности в списки смежности) Преобразовать списки смежности в матрицу смежности) Преобразовать списки смежности в матрицу инцидентности.
4) Преобразовать матрицу инцидентности в списки смежности.
Задача 2.13. Цикл в связном неориентированном графе называется Эйлеровым, если он проходит по одному разу через каждое ребро графа. Докажите, что в таком графе имеется
Эйлеров цикл тогда и только тогда, когда степени всех его вершин четны (такие графы называются четными).
Указание. Достаточность можно установить, доказав правильность следующей процедуры построения Эйлерова цикла) Выбрать произвольную вершину a и построить цикл, начинающийся и закачивающийся в a, следуя правилу (*): прийдя в некоторую вершину, выйти из нее по произвольному ребру,
еще не включенному в цикл) Если построенный цикл содержит не все ребра, то выбрать среди вершин, через которые он проходит, произвольную вершину b, инцидентную еще не пройденному ребру (почему такая вершина найдется, и построить, начиная с нее, цикл, следуя тому же правилу (Объединить этот цикл с построенным ранее) Повторять пункт (2) до тех пор, пока построенный цикл не станет Эйлеровым.
Задача 2.14. Докажите, что для любого связного неориентированного графа G = (V, описанный в предыдущей задаче алгоритм построения Эйлерова цикла можно реализовать за время Задача 2.15. Используя алгоритм из задачи 2.13, определить по неориентированному графу = (V, четный ли он. Если он не является четным, то удалить из него минимальное число ребер, чтобы он стал четным. Построить в исходном или в получившемся после удаления ребер четном графе Эйлеров цикл = {a, b, c, e, f, g, h, k, m, n}
, E = {(a, c), (a, h), (a, m), (a, k), (b, c), (b, k), (b, f), (b, m), (c, k), (c, m),
(e, f ), (e, g), (f, k), (f, n), (g, m), (g, h), (h, k), (h, m), (k, Задача 2.16. Неориентированный граф G = (V, E) называется двудольным, если его вершины можно разбить на две непересекающихся части X и Y (V = X ? Y, X ? Y = ?) так,
что каждое ребро из e ? E соединяет вершину из X с вершиной из Y . Такой граф также называется бихроматическим, так как его вершины можно раскрасить в два цвета так, что соседние вершины будут окрашены в разные цвета.
Докажите, что граф является двудольным тогда и только тогда, когда в нем нет циклов нечетной длины (теорема Кјнига).
Указание. Достаточность можно установить, доказав правильность следующей процедуры разбиения V на X и Y ,
1) Выбрать произвольную вершину v ? V, поместить ее в X и отметить знаком +.
2) WHILE имеются неотмеченные вершины с отмеченными соседями) DO { Поместить все неотмеченные вершины с соседями изв и отметить их знаком - Поместить все неотмеченные вершины с соседями изв и отметить их знаком +
}
;
3) IF после завершения цикла 2 в V остались неотмеченные вершины поместить произвольную такую вершину v в X, отметить ее знаком +
11

и снова повторить цикл 2
ELSE выдать в качестве результата полученные множества X  вершины, отмеченные, и Y  вершины, отмеченные -Для доказательства корректности этой процедуры установите, что в процессе разметки ни одна вершина не получит соседа стой же меткой.
Задача 2.17. Используя результаты предыдущей задачи, определить является ли заданный ниже неориентированный граф G = (V, E) двудольным. Если он не двудольный, то каково минимальное число ребер, которые нужно из него удалить, чтобы он стал двудольным?
Приведите обоснование ответа = {a, b, c, e, f, g, h, k, m, n}
, E = {(a, h), (a, n), (a, k), (b, k), (b, f), (b, m), (c, k), (c, h), (e, f), (e, g),
(f, a), (f, m), (g, m), (m, Задача 2.18. Пусть имеется группа студентов, каждый из которых должен сдать два экзамена по предметам из множества {p
1
, . . . , p n
}
. Экзамены должны пройти в два дня:
вторник и четверг. Задень студент может сдать только один экзамен.
Определите, какие экзамены нужно назначить на вторники на четверг, чтобы каждый студент смог сдать оба свои экзамена. Можно ли составить такое расписание, чтобы каждый экзамен принимался только в один из дней Предложите эффективный алгоритм для составления такого расписания (если оно существует).
Задача 2.19. Предложите алгоритм сложности O(|V |+|E|), который в неориентированном графе G = (V, E) удаляет каждую вершину v степени 2, заменяя инцидентные ей ребра, и (v, w) на ребро (u, w). Подчеркнем, что в результирующем графе не должно остаться вершин степени 2, те. каждая линейная цепь заменится на одно ребро Неориентированные и ориентированные деревья Основные определения
Деревья являются одним из интереснейших классов графов, используемых для представления различного рода иерахических структур.
Определение 10. Неориентированный граф называется деревом, если он связный ив нем нет циклов.
Определение 11. Ориентированный граф G = (V, E) называется (ориентированным) деревом, если) в нем есть одна вершина r ? E, в которую не входят ребра она называется корнем дерева) в каждую из остальных вершин входит ровно по одному ребру) все вершины достижимы из корня.
На рисунке 6 показаны примеры неориентированного дерева и ориентированного дерева. Обратите внимание на то, что дерево получено из с помощью выбора вершины c в качестве корня и ориентации всех ребер в направлении от корня".
Это неслучайно. Докажите самостоятельно следующее утверждение о связи между неориентированными и ориентированными деревьями.
Лемма 3.1. Если в любом неориентированном дереве G = (V, E) выбрать произвольную вершину в качестве корня и сориентировать все ребра в направлении от корня, те

@
@
@
,
,
,







?
H
H
H
j




?
H
H
H
H
j
?
?
u u
u u
u u
u u
u m
m m
m m
m m
m m
a b
c d
e f
g h
k h
k d
g e
f c
b Неориентированное дерево Ориентированное дерево Рис. 6: Неориентированное и ориентированное деревья сделать v началом всех инцидентных ей ребер, вершины, смежные с v  началами всех инцидентных им еще не сориентированных ребер и т.д., то полученый в результате ориентированный граф будет ориентированным деревом.
Неориентированные и ориентированные деревья имеют много эквивалентных характери- стик.
Теорема 3.1. Пусть G = (V, E)  неориентированный граф. Тогда следующие условия эквивалентны является деревом) Для любых двух вершин в G имеется единственный соединяющий их путь) G связен, но при удалении из E любого ребра перестает быть связным) G связен и |E| = |V | ? 1.
(5) G ациклический и |E| = |V | ? 1.
(6) G ациклический, но добавление любого ребра к E порождает цикл.
Доказательство. (1) ? (2): Если бы в G некоторые две вершины соединялись двумя путями, то, очевидно, в G имеелся бы цикл. Но это противоречит определению дерева в (1).
(2) ? (3)
: Если G связен, но при удалении некоторого ребра (u, v) ? E не теряет связности,
то между u и v имеется путь, не содержащий это ребро. Но тогда в G имеется не менее двух путей, соединяющих u и v, что противоречит условию (2).
(3) ? (4)
: Предоставляется читателю (см. задачу 2.8).
(4) ? (5)
: Если G содержит цикли является связным, то при удалении любого ребра из цикла связность не должна нарушиться, но ребер останется |E| = |V ?2|, а по задаче а) в связном графе должно быть не менее |V ? 1| ребер. Полученное противоречие показывает, что циклов в G нет и выполнено условие (5).
(5) ? (6)
: Предположим, что добавление ребра (u, v) к E не привело к появлению цикла. Тогда в G вершины u и v находятся в разных компонентах связности. Так как |E| = |V ?1|, тов одной из этих компонент, пусть это (V
1
, E
1
)
, число ребер и число вершин совпадают |E
1
| = |V
1
|
. Но тогда в ней имеется цикл (см. задачу 2.8 (б) ), что противоречит ацикличности G.
(6) ? (1)
: Если бы G не был связным, то нашлись бы две вершины u и v из разных компонент связности. Тогда добавление ребра (u, v) к E не привелобы к появлению цикла, что противоречит. Следовательно, G связен и является деревом

Для ориентированных деревьев часто удобно использовать следующее индуктивное опре- деление.
Определение 12. Определим по индукции класс ориентированных графов D, называемых деревьями. Одновременно для каждого из них определим выделенную вершину  корень) Граф T
0
= (V, E)
, с единственной вершиной V = {v} и пустым множеством ребер E = является деревом (входит в D). Вершина v называется корнем этого дерева) Пусть графы T
1
= (V
1
, E
1
), . . . , T
k
= (V
k
, с корнями r
1
? V
1
, . . . , r k
? V
k принадлежат, а r
0
 новая вершина, те. r
0
/
?
S
k i=1
V
i
. Тогда классу D принадлежит также следующий граф T = (V, E), где V = {r
0
} ?
S
k i=1
V
i
, E = {(r
0
, r i