© Данная статья была опубликована в № 20/2007 журнала "Информатика" издательского дома "Первое сентября". Все права принадлежат автору и издателю и охраняются.      Главная страница "Первого сентября"
     Главная страница журнала "Информатика"
     Содержание № 20/2007
 Математические основы информатики. Лекция 4.


Курсы повышения квалификации

Математические основы информатики

А.Г. Гейн

Учебный план

№_ГАЗЕТЫ

Лекция

17/2007

Лекция 1. Что такое “математические основы информатики”. Почему информатику нередко считают близкой род-
ственницей математики? Верно ли это? Возможна ли информатика без математики? Какая математика нужна для освоения
информатики? Может ли школьная математика дать основу для информатики?

Информация и ее кодирование. Математика кодов. Коды, исправляющие ошибки. Экономное кодирование.

18/2007

Лекция 2. Математические модели формальных исполнителей. Что такое формальная обработка информации? Конеч-
ные автоматы. Что первично: язык или исполнитель? Грамматика языка. Распознаваемые языки. Универсальные исполни-
тели (машина Тьюринга, машина Поста).

19/2007

Лекция 3. Алгоритм и его свойства. Алгоритмическая неразрешимость. Вычислимость. Сложность.
Контрольная работа № 1.

20/2007

Лекция 4. Графы. Графы и орграфы. В каких задачах они возникают? Различные свойства графов (эйлеровость, гамильто-
новость, планарность, двудольность). Сети. Потоки в сетях. Представление графов. Основные алгоритмы на графах.

21/2007

Лекция 5. Логические модели в информатике. Алгебра высказываний. Булевы функции. Нормальные формы. Полные
классы булевых функций. Релейно-контактные схемы. Вентили. Математические модели процессора и памяти компьютера. Предикаты и отношения. Реляционная алгебра. Теоретические основы реляционных СУБД. Языки логического программирования и их математическое основание.
Контрольная работа № 2.

22/2007

Лекция 6. Компьютерная теория чисел и вычислительная геометрия. Зачем нужна теория чисел в компьютерных
науках? Гонка за простыми числами. Как разложить число на множители? Чем отличается теоретическая геометрия от
вычислительной? Почему гладко на бумаге, но коряво на компьютере? Основные правила и алгоритмы вычислительной
геометрии.
23/2007 Лекция 7. Защита информации. Защита символьной информации. Что нужно защищать? Электронная подпись. Системы
верификации. Криптосистемы с открытым ключом. Защита графической информации. Математика электронных водяных знаков.
24/2007 Лекция 8. Основы методики преподавания математических основ информатики.
Итоговая работа

Лекция 4. Графы

Кто может с уверенностью сказать, с чего началась теория чисел? С алгоритма, предложенного Евклидом (IV–III вв. до н.э.), или принадлежащего ему же доказательства теоремы о бесконечности множества простых чисел? Или с работ Диофанта (III в. н.э.) о решении уравнений в целых числах? Или с исследований Пьера Ферма (XVII в. н.э.), в которых изучение свойств целых чисел было основной и, самое важное, осознанной целью?

Кто может с уверенностью сказать, когда возникло понятие функции и кем оно было введено? Тоже никто.

Теория графов — одна из тех немногих математических теорий, для которых точно известен ее создатель, время и место создания: Леонард Эйлер, 1736 г.,
г. Петербург. Именно в этом году Л.Эйлером в “Записках Петербургской академии наук” была опубликована статья, в которой приводилось решение широко теперь известной задачи о Кёнигсбергских мостах. Разумеется, работа Л.Эйлера содержала не только отрицательный ответ на вопрос о возможности обойти все семь мостов г. Кёнигсберга так, чтобы по каждому из них пройти ровно один раз. В ней великий математик сформулировал и обосновал критерий, позволяющий отвечать на данный вопрос для любого графа.

Однако эта статья была единственной в течение почти столетия. Лишь в середине XIX века возродился интерес к теории графов. Исследование электрических сетей, структур молекул и строения кристаллов, применения к решению проблем в биологии и психологии послужили мощным катализатором в становлении данного раздела математики. Графы оказались удобным средством для описания самых разнообразных систем и явились эффективным инструментом структурного анализа. Графы успешно применяются для решения разнообразных задач планирования — выбор оптимального маршрута (транспортная задача), построение сетевого графика, исследование потоков в сетях и т.п. Одной из самых знаменитых задач, которая вызвала фейерверк остроумных работ в области теории графов, была предложенная де Морганом (около 1850 г.) проблема четырех красок: верно ли, что для раскраски любой карты так, чтобы граничащие между собой страны были раскрашены в разные цвета, достаточно четырех красок?

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

§ 10. Понятие графа. Простейшие свойства

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

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

Сформулируем свойство, относящееся к любым графам.

Теорема 1. Сумма степеней всех вершин графа равна удвоенному числу его ребер.

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

Из этого свойства есть следствие, которое принято называть “леммой о рукопожатиях”.

Теорема 2. Количество вершин нечетной степени любого графа всегда четно.

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

А вот еще одно свойство.

Теорема 3. В любом графе есть по крайней мере две вершины, имеющие одинаковую степень.

Доказательство. Пусть в графе n вершин. Ясно, что степень каждой вершины может иметь значение от 0 до n – 1. Если степени всех вершин различны, то каждое из указанных значений должно реализоваться ровно для одной вершины. Рассмотрим вершины степени 0 и степени n – 1. Степень 0 означает, что эта вершина не соединена ни с какой другой; степень
n
– 1 означает, что эта вершина соединена со всеми другими вершинами. Но одновременно так быть не может.

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

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

Рис. 1. Разные изображения одного графа

Маршрутом на графе называется последовательность ребер е1, е2, …, еk, в которой конец одного ребра служит началом следующего. Если при этом конец последнего ребра последовательности совпал с началом первого ребра, то маршрут называется циклическим. Для графа, изображенного на рис. 2, последовательности е1, е2, е4, е5, е2, е3 и е2, е4, е5 являются маршрутами, причем второй из них — циклический. А последовательность е1, е2, е5 маршрутом не является.

Рис. 2

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

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

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

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

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

 

Теорема 4. Если в связном графе удалить ребро, принадлежащее циклу, то граф останется связным.

Ее доказательство мы оставляем читателю в качестве несложного упражнения.

1. Пусть V = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} — множество вершин графа. Для каждого из перечисленных ниже случаев изобразите соответствующий граф:

а) вершины x и y соединены ребром тогда и только тогда, когда |ху| / 3 — целое число;

б) вершины x и y соединены ребром тогда и только тогда, когда х + у = 9;

в) вершины x и y соединены ребром тогда и только тогда, когда х + у содержится в множестве V;

г) вершины x и y соединены ребром тогда и только тогда, когда |ху| < 3;

д) вершины x и y соединены ребром тогда и только тогда, когда x и y не взаимно просты.

2. Составьте список степеней вершин для каждого из графов, построенных вами при выполнении задания 1.

3. Существует ли граф с пятью вершинами и следующим набором степеней вершин а) 0, 1, 2, 3, 4; б) 1, 1, 2, 3, 4; в) 1, 1, 2, 2, 4; г) 1, 1, 2, 3, 3 ? При ответе “Да” надо предъявить соответствующий граф, ответ “Нет” надо обосновать.

4. Какое наибольшее число ребер может содержать граф, имеющий n вершин?

5. Может ли в государстве, в котором из каждого города выходит ровно три дороги, быть ровно сто дорог?

6. — Наша шпионская сеть была хорошо законспирирована, — признался на допросе агент 007. — В ней было 77 агентов, но каждый знал только семерых.

Почему наверняка можно утверждать, что агент лжет?

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

8. Выясните, одинаковы ли графы, изображенные на рис. 3а; на рис. 3б, 3в.

Рис. 3

9. Найдите число простых циклов длины 3, 4, 5 и 6 для графов, изображенных на рис. 4.

Рис. 4

10. На конгрессе собрались ученые, среди которых есть друзья. Оказалось, что никакие двое ученых, имеющих равное число друзей, не имеют общих друзей. Доказать, что найдется ученый, который имеет ровно одного друга.

11. Среди графов, построенных вами при выполнении задания 1, укажите связные. Для несвязных графов найдите число компонент связности.

§ 11. Способы представления графов

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

Напомним, что граф называется нагруженным (взвешенным), если каждому ребру сопоставлено некоторое число (вес ребра). В зависимости от рассматриваемой задачи это число может обозначать расстояние между вершинами или время перехода от одной вершины к другой (если, например, графом изображена какая-либо транспортная схема), или пропускную способность канала, соединяющего две данные вершины (если в виде графа изображена какая-либо коммуникационная сеть), или еще что-либо. Иногда бывает удобно рассматривать ненагруженный граф как нагруженный, у которого каждому ребру поставлено в соответствие число 1. Мы поэтому обсудим способы представления нагруженных графов.

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

Список ребер: (AA; 2), (AB; 3), (AC; 6), (BC; 2), (AD; 4), (BD; 3), (CD; 5).

Таблица 3.1

В таблице смежности ненагруженного графа везде вместо чисел, указывающих нагрузку (т.е. отличных от 0), стояло бы число 1. А в списке ребер ненагруженного графа просто не нужна числовая характеристика.

Рис. 5

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

В дальнейшем в заданиях на составление алгоритма, тем или иным образом обрабатывающего граф, мы для простоты будем считать вершины графа перенумерованными натуральными числами от 1 до n (без пропусков и повторений). Список ребер для нагруженного графа будем задавать как двумерный массив A[1 : n, 1 : 3], где в первой строке соответствующей этому массиву таблице указывается один конец ребра, во второй — другой его конец, а в третьей — величина нагрузки (здесь n — число ребер в графе). Для ненагруженного графа соответствующий массив содержит только первые две строки. Если граф задается таблицей смежности, то договоримся считать значение первого индекса номером первой вершины, а второго индекса — номером второй вершины; сами номера вершин в массиве не присутствуют. В частности, для графа на рис. 5 при естественной нумерации вершин A — 1, B — 2, C — 3 и D — 4 список ребер в силу нашей договоренности задается массивом, который можно изобразить табл. 3.2, а таблица смежности выглядит так, как показано в табл. 3.3.

1. Для каждого из графов, изображенных на рис. 6, запишите его представление списком ребер и таблицей смежности.

Вопросы и задания

Рис. 6

3. Изобразите графы, заданные следующими таблицами смежности.

4. а) Граф, имеющий n вершин, задан списком ребер. Составьте алгоритм, создающий по этому списку таблицу смежности.

б) Граф, имеющий n вершин, задан таблицей смежности. Составьте алгоритм, создающий по этой таблице список ребер.

§ 12. Алгоритмы обхода связного графа

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

Один из них называется поиском в глубину. Идея алгоритма такова. Пусть зафиксирована начальная вершина v0. Выберем смежную с ней вершину v1. Затем для v1 поступаем так же: выбираем смежную с ней вершину из числа еще невыбранных вершин. И так далее: если мы уже выбрали вершины v0, v1, …, vk, то следующая вершина выбирается смежной с vk из числа невыбранных. Если для вершины vk такой вершины не нашлось, то возвращаемся к вершине vk – 1 и для нее ищем смежную среди невыбранных. При необходимости возвращаемся еще на шаг назад и т.д. Ясно, что так будут перебраны все вершины графа, и поиск закончится. На рис. 7 показаны две реализации поиска в глубину для одного и того же графа (при одинаковом выборе начальной вершины): около каждой вершины написан присвоенный ей порядковый номер при исполнении поиска в глубину. Свое название этот метод получил за то, что при его реализации мы стремимся как можно дальше уйти от исходной вершины, а когда идти уже некуда, возвращаемся в ту вершину, откуда идет хотя бы одно ребро в непройденные еще вершины.

Рис. 7. Два варианта применения поиска в глубину

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

Будем считать, что граф задан таблицей смежности. Кроме того, организуем одномерный массив В, число элементов в котором совпадает с числом вершин в графе. На k-м месте этого массива будем писать номер вершины, в которую мы попали на k-м шаге. С третьим вопросом поступим так: из всех смежных непройденных вершин будем выбирать вершину с наименьшим номером. Чтобы хранить список вершин, откуда еще есть куда отправиться, организуем еще один одномерный массив St[1:n].

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

алг Поиск в глубину (арг цел m, n,

цел таб G[1:n; 1:n],

рез цел таб B[1:n])

нач цел t, u, St[1:n];

ввод n |запрашивается количество вершин

|в графе

ввод G[1:n: 1:n] |реально это действие —

|ввод таблицы смежности G —

|оформляется двойным циклом

ввод m |запрашивается номер вершины,

с которой начинается обход графа

нц для t от 1 до n

B(t) := 0

St(t) := 0

кц

B(m) := 1 |помечается пройденная вершина

St(1) := m

u := 1 | количество элементов в массиве St

нц пока (u > 0)

t := 1

s := 1

нц пока ((t <= n) и

(G(St(u), t) = 0 или B(t) = 1))

t := t + 1

кц |поиск новой смежной вершины

если (t < n + 1)

то u := u + 1

B(t) := 1

St(u) := t

вывод t

иначе St(u) := 0

u := u – 1

все

кц

кон

Как обрабатывается в этом алгоритме массив St? По мере продвижения в глубину в него заносятся номера пройденных вершин. Как только вершина оказывается тупиковой, т.е. из нее уже нельзя продвинуться дальше к новой вершине, эта вершина стирается из массива St (в ячейку заносится 0), и алгоритм начинает работать с предыдущей вершиной. Если и она оказывается тупиковой, то она тоже стирается, и обрабатывается предыдущая вершина и т.д. Количество ненулевых элементов в St, т.е. номеров вершин, то увеличивается, то уменьшается в зависимости от удаленности от исходной вершины. Все это происходит до тех пор, пока все элементы в St не станут нулевыми (и счетчик u не станет нулевым). Заметим, что ненулевой элемент, который появляется в St последним, первым из него удаляется. Это напоминает движение патронов в магазине автомата: последний патрон, которым снаряжен магазин, будет первым подан на выстрел. Поэтому такой способ организации данных — последним пришел, первым обработан — называют магазинным, а саму такую структуру данных магазином или, по-другому, стеком.

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

Другой алгоритм называется поиском в ширину. Суть этого подхода состоит в том, чтобы рассматривать все вершины, смежные с уже рассмотренными. На рис. 8 показаны две реализации поиска в ширину для одного и того же графа (при одинаковом выборе начальной вершины).

Рис. 8. Два варианта применения поиска в ширину

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

А сейчас рассмотрим одну из часто встречающихся задач: найти длину кратчайшей цепи от заданной вершины до любой другой. Длиной цепи при этом называют количество содержащихся в ней ребер.

Идея решения этой задачи состоит в следующем. Исходной вершине припишем число 0. Каждой смежной с ней вершине припишем число 1. Каждой вершине, смежной с той, которая уже помечена числом 1 и не была помечена раньше, приписываем число 2. Каждой вершине, смежной с той, которая уже помечена числом 2 и не была помечена раньше, приписываем число 3. И так далее, до тех пор, пока такое действие можно будет производить. Конечно, при этом могут оказаться вершины, добраться до которых так и не удастся. На рис. 9 приведен результат обработки указанным образом конкретного графа. Действие этого алгоритма напоминает распространение волны, и потому он получил название “волнового алгоритма”.

 

Рис. 9. Результат обработки графа волновым алгоритмом

Легко понять, что число, написанное около вершины, показывает длину кратчайшей цепи, ведущей к ней от заданной вершины. Запишем волновой алгоритм, считая, что граф задан таблицей смежности. Предположим для простоты, что в этом графе n вершин, а таблица смежности представлена целочисленным массивом G[1 : n; 1 : n]. Результатом является одномерный целочисленный массив Р[1 : n], для которого в ячейке Р[k] хранится длина пути от заданной вершины до вершины с номером k; если вершина с номером k не достижима, то договоримся в ячейку Р[k] записывать –1.

алг Кратчайший_путь (арг цел m, n,

цел таб G[1:n: 1:n],

рез цел таб Р[1:n])

нач цел m, n, I, J, K, G[1: n; 1: n], Р[1: n];

ввод n |запрашивается количество вершин в графе

ввод G[1:n: 1:n] |реально это действие —

|ввод таблицы смежности G — оформляется двойным циклом

ввод m |запрашивается номер начальной

|вершины

нц для I от 1 до n

P(I) := –1;

кц |сначала массив результатов заполним –1

Р(m) := 0 |до исходной вершины

|добираемся за 0 шагов

нц для K от 0 до n – 1 |K — расстояние

от исходной вершины

нц для I от 1 до n

если P(I) = K

|ищем вершину с заданным расстоянием K

|до исходной вершины

то нц для J от 1 до n

если (P(J) = –1 и G(I, J) = 1)

то P(J) := K + 1

все

кц

|перечисляем вершины с расстоянием K + 1

|до исходной вершины, смежные с I-й

|вершиной

все

кц

кц

нц для I от 1 до n

если P(I) = – 1

то вывод "Вершина", I;

вывод "недостижима из вершины", m;

иначе вывод "Кратчайший путь до

вершины", I;

вывод "от вершины", m;

вывод "равен", P(I);

все

кц

кон

Вопросы и задания

1. Исполните алгоритм “Поиск в глубину” для графов, заданных табл. 3.4–3.6.

2. а) Объясните, почему приведенный алгоритм “Поиск в глубину” не может применяться к несвязным графам. Какое из свойств алгоритмов будет нарушаться при таком применении?

б) Модифицируйте алгоритм “Поиск в глубину” так, чтобы он стал применимым и к несвязному графу.

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

4. Выполните поиск в ширину для графов, заданных табл. 3.4–3.6.

5. Исполните волновой алгоритм для графов, заданных табл. 3.4–3.6.

6. Граф, изображенный на рис. 9, имеет 21 вершину. Из представленного на рис. 9б) результата работы алгоритма, приведенного в объяснительном тексте, видно, что при значениях счетчика K, больших, чем 6 (а таких значений 15), цикл будет работать “вхолостую” — ведь новых чисел при вершинах появиться не может. Модифицируйте алгоритм так, чтобы цикл по K не исполнялся сверх нужного числа раз.

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

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

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

§ 13. Мосты и точки сочленения

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

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

Ребро связного графа называется мостом, если после его удаления граф перестает быть связным.

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

Вопросы и задания

1. Что такое точка сочленения?

2. Какое ребро связного графа называют мостом?

3. Какой граф называют двусвязным?

4. Укажите мосты и точки сочленения для графов, представленных на рис. 10.

Рис. 10

5. а) Дан связный граф, содержащий не менее трех вершин. Известно, что в нем имеется мост. Можно ли утверждать, что этот граф содержит точку сочленения?

б) Дан связный граф, содержащий не менее трех вершин. Известно, что в нем имеется точка сочленения. Можно ли утверждать, что этот граф содержит мост?

6. Составьте алгоритм, с помощью которого можно найти все точки сочленения заданного графа. Рассмотрите два варианта задания графа — списком ребер и таблицей смежности.

7. Составьте алгоритм, с помощью которого можно найти все мосты заданного графа. Рассмотрите два варианта задания графа — списком ребер и таблицей смежности.

8. а) Докажите, что вершина v является точкой сочленения в связном графе тогда и только тогда, когда найдутся такие две вершины a и b, для которых любая цепь, соединяющая эти вершины, проходит через вершину v.

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

§ 14. Деревья

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

Деревья — это те графы, с которыми в курсе информатики, да и других предметах чаще всего приходится иметь дело. Дерево каталогов и генеалогическое дерево, да и вообще любая иерархическая система с точки зрения своей структуры представляет именно дерево. Применяя алгоритмы поиска в глубину или в ширину, вы из исходного графа извлекаете дерево — вершинами в нем являются вершины исходного графа, и эти вершины соединяются ребром, если при исполнении алгоритма переход от одной вершины к следующей осуществлялся по этому ребру. На рис. 11а представлено дерево, полученное применением поиска в глубину в соответствии с рис. 7а; на рис. 11б представлено дерево, полученное применением поиска в ширину в соответствии с рис. 8а. Дерево, ребра которого являются ребрами некоторого заданного графа G, содержащее все вершины этого графа, называется каркасом графа G. Так что можно сказать, что на рис. 11 представлены два каркаса одного и того же графа. По-другому каркас называют остовом, или стягивающим деревом.

Рис. 11. Деревья, получаемые при обходе графа

Дерево, как правило, изображают некоторым стандартным образом. Для этого фиксируют одну из вершин, ее называют корнем. Корень изображают внизу, а все остальные вершины распределяют по уровням. На первом уровне размещаются вершины, смежные с корнем, на втором — смежные с вершинами первого уровня, отличные от корня, на третьем — смежные с вершинами второго уровня, отличные от вершин первого уровня, и т.д. На рис. 12 приведены два изображения одного и того же дерева, взятого с рис. 11б, при разном выборе корневой вершины: в одном случае корнем служит вершина, обозначенная числом 0, в другом — числом 6. Впрочем, нередко бывает удобнее рисовать дерево сверху вниз или слева направо.

Рис. 12. Одно и то же дерево при разном выборе корня

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

Вершины степени 1, отличные от корня, называются листьями. Легко видеть, что, удаляя лист вместе с ведущим в него ребром, мы одновременно уменьшаем на 1 количество вершин и количество листьев. Проделав это столько раз, сколько ребер в дереве, мы останемся один на один с корнем. Следовательно, в любом дереве вершин всегда на 1 больше, чем ребер. На самом деле справедливо и обратное утверждение: если в связном графе количество вершин на 1 больше числа ребер, то это дерево. Мы предлагаем вам доказать это утверждение самостоятельно (см. задание 6).

Вопросы и задания

1. Как связаны количества ребер и вершин в дереве?

2. Для дерева, изображенного на рис. 11а, нарисуйте дерево, взяв в качестве корня вершину, обозначенную а) числом 5; б) числом 10.

3. Изобразите все деревья с четырьмя и пятью вершинами.

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

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

5. Докажите, что связный граф является деревом тогда и только тогда, когда любое его ребро является мостом. (Совет: воспользуйтесь утверждением, сформулированным в задании 8б к § 13.)

6. Докажите, что связный граф, в котором количество ребер на 1 меньше числа вершин, является деревом. (Совет: воспользуйтесь теоремой 4, сформулированной в § 10.)

7. Составьте алгоритм, позволяющий построить каркас с использованием поиска в глубину. Рассмотрите два варианта задания графа — списком ребер и таблицей смежности.

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

§ 15. Каркасы минимального веса

Представьте себе, что надо соединить несколько пунктов линиями связи. Известна стоимость возможного строительства линии между парами таких пунктов. Какие именно пункты надо соединить, чтобы получившаяся сеть обслуживала все пункты и при этом имела минимальную стоимость?

Переводя эту задачу на язык графов, можно сказать так.

Имеется нагруженный связный граф. Требуется найти каркас с минимальным суммарным весом его ребер.

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

Рис. 13. Два каркаса для одного графа

Опишем метод построения хотя бы одного каркаса минимального веса, известный как алгоритм Краскала. Будем считать, что исходный связный граф G задан списком ребер. И получающийся каркас тоже будет задан списком ребер. Идея алгоритма состоит в построении двух последовательностей множеств ребер исходного графа: Т1, Т2, Т3, … и Е1, Е2, Е3, …

На первом шаге выбираем произвольное ребро е1 наименьшего веса (если таких ребер несколько, то берем любое из них) и полагаем Т1 = {e1}. В качестве Е1 строится множество ребер, каждое из которых не содержится в Т1 и при добавлении к Т1 не образует цикл.

Пусть уже построены множества Т1, Т2, …, Тk и Е1, Е2, …, Еk. Если Еk не содержит ребер, то в качестве искомого каркаса берем Тk. Если же множество Еk не пусто, то строим Тk+1 и Еk+1 по следующему правилу: в Еk выбираем ребро наименьшего веса (если таких ребер несколько, то снова берем любое из них) и добавляем его в множество Тk, это и будет множество Тk+1; множество Еk+1 состоит из ребер исходного графа, каждое из которых еще не попало в Тk+1 и при добавлении его к Тk+1 не образуется цикл. Такое построение последовательности множеств Тk и Еk повторяется, пока какое-нибудь из множеств Еk не станет пустым.

Алгоритм, реализующий эту идею, вы составите самостоятельно, выполнив задание 5. Но каждый, кто хорошо разобрался в материале лекции 2, не может не задаться следующими вопросами:

1) Почему соответствующий алгоритм конечен?

2) Почему соответствующий алгоритм результативен?

3) Почему результатом является требуемый каркас?

Конечность алгоритма обеспечивается тем, что количество ребер, остающихся вне множества Тk на каждом шаге, уменьшается на 1. Следовательно, и в Еk в конце концов нельзя будет “рекрутировать” ни одного ребра.

Предложенный алгоритм не является детерминированным, поэтому надо убедиться, что после его завершения образуется каркас исходного графа. Пусть исполнение алгоритма завершилось построением графа Тk, т.е. Еk не содержит ребер. По построению в Тk нет циклов. Если Тk не содержит хотя бы одну вершину исходного графа G, то ребро е, выходящее из этой вершины, не принадлежит Тk, а при включении его в Тk не может образоваться цикл. Но тогда это ребро обязано было попасть в Еk в противоречии с тем, что Еk пусто. Значит, содержит все вершины графа G. Осталось показать, что Тk связен. Допустим снова, что это не так. Тогда Тk содержит по крайней мере две компоненты связности, скажем, А и В. Поскольку исходный граф G связен, существуют смежные вершины а из А и b из В. Пусть е — соединяющее их ребро. Тогда е не принадлежит Тk. Более того, по определению е является мостом исходного графа G. Значит, в графе, полученном из Тk добавлением этого ребра, не может образоваться цикл, ибо иначе цикл, содержащий ребро е, был бы и в самом графе G. Снова получаем, что ребро е должно было бы попасть в Еk, что противоречит отсутствию в Еk элементов. Это противоречие показывает, что на самом деле граф Тk связен и, следовательно, Тk — дерево, содержащее все вершины графа G, т.е. Тk — каркас графа G.

Осталось ответить на третий вопрос: почему вес у построенного каркаса минимален?

Допустим, что это не так. Выберем каркас Т, имеющий наименьший суммарный вес. Как мы уже говорили, таких каркасов с наименьшим весом может оказаться несколько. Выберем среди них такой, у которого наибольшее количество общих с каркасом Тk ребер. Будем по-прежнему обозначать этот минимальный каркас буквой Т.

Можно считать, что в каркасе Тk все ребра перенумерованы в порядке поступления их в Тk. Ясно, что Тk не может целиком содержаться в Т, ибо иначе эти два каркаса просто бы совпали — ведь у них одно и то же множество вершин. Пусть em — ребро с наименьшим номером, которое содержится в Тk, но не содержится в Т '. Добавим это ребро к графу Т. В получившемся связном графе F, очевидно, образовался некоторый цикл С. В этом цикле есть ребро е, не принадлежащее каркасу Тk, ибо в Тk вообще нет циклов. Рассмотрим граф Т ', полученный из графа Т изъятием ребра е и добавлением ребра em. Граф Т' связен, поскольку получен из связного графа F удалением ребра, принадлежащего циклу (теорема 4 из § 10). Граф Т ' является деревом, поскольку в нем столько же ребер и вершин, сколько в дереве Т, т.е. вершин на 1 больше, чем ребер (см. задание 6 к § 14). Наконец, все вершины графа G принадлежат графу Т ', поскольку у Т и Т ' одно и то же множество вершин. Тем самым, Т' — тоже каркас графа G.

Сравним вес ребер е и em. Поскольку ребра е1, е2, …, em-1 принадлежат Т, добавление ребра е к множеству Тm-1 не создает цикла в получающемся графе (ибо
Т
— дерево). Правило выбора em показывает, что вес е не меньше веса em (иначе в Тm было бы включено другое ребро, нежели em). Данное сравнение весов показывает, что вес графа Т' не больше веса графа Т. Но каркас Т имеет наименьший вес среди всех каркасов графа G. Значит, вес каркаса Т ' совпадает с весом каркаса Т, т.е. тоже является наименьшим. Однако у каркаса Т ' количество общих ребер с каркасом Тk на единицу больше, чем у каркаса Т, что противоречит выбору Т. Полученное противоречие показывает, что каркас Тk сам является каркасом минимального веса.

Вот теперь все. Можно приступать к выполнению заданий.

Вопросы и задания

1. Какая функция выступает лимитирующей в алгоритме Краскала?

2. Найдите каркас минимального веса, используя метод Краскала для графов, представленных на рис. 14.

3. Алгоритм Краскала, как отмечалось в объяснительном тексте, не является однозначным. Рассмотрим множество всех каркасов минимального веса, которые могут получиться в результате применения этого алгоритма к заданному графу G. Верно ли, что это множество содержит все каркасы минимального веса, имеющиеся в графе G?

4. Как нужно изменить алгоритм Краскала, чтобы его можно было использовать для построения каркаса максимального суммарного веса?

5. Запишите алгоритм, реализующий метод Краскала. Для этого определите, как именно будет выбираться очередное ребро для построения множества Тm из множества Тm – 1.

6. Составьте алгоритм, реализующий метод Краскала, если граф задан таблицей смежности.

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

8. Попытайтесь обосновать, что метод Прима, описанный в задании 7, всегда дает каркас минимального веса.

9. Составьте алгоритм, реализующий метод Прима. Рассмотрите два варианта задания исходного графа — списком ребер и таблицей смежности.

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

1. Новиков Н.Ф. Дискретная математика для программистов. СПб.: Питер, 2006, 364 с.

2. Окулов С.М. Программирование в алгоритмах. М.: Бином, 2006, 383 с.

3. http://algolist.manual.ru/maths/graphs/.