Кенигсбергские мосты. 1. Введение
2. История возникновения теории графов
3. Основные определения теории графов
4. Основные теоремы теории графов
5. Задачи на применение теории графов
Возможно вы искали - Реферат: Теория игр и принятие решений
6. Применение теории графов в школьном курсе математики
7. Приложение теории графов в различных областях науки и техники
8. Последние достижения теории графов
9. Вывод
§1. ИСТОРИЯ ВОЗНИКНОВЕНИЯ ТЕОРИИ ГРАФОВ.
Родоначальником теории графов принято считать математика Леонарда Эйлера (1707-1783). Историю возникновения этой теории можно проследить по переписке великого ученого. Вот перевод латинского текста, который взят из письма Эйлера к итальянскому математику и инженеру Маринони, отправленного из Петербурга 13 марта 1736 года [см. [5]стр. 41-42]:
Похожий материал - Реферат: Теория информации
"Некогда мне была предложена задача об острове, расположенном в городе Кенигсберге и окруженном рекой, через которую перекинуто семь мостов. Спрашивается, может ли кто-нибудь непрерывно обойти их, проходя только однажды через каждый мост. И тут же мне было сообщено, что никто еще до сих пор не мог это проделать, но никто и не доказал, что это невозможно. Вопрос этот, хотя и банальный, показался мне, однако, достойным внимания тем, что для его решения недостаточны ни геометрия, ни алгебра, ни комбинаторное искусство… После долгих размышлений я нашел легкое правило, основанное на вполне убедительном доказательстве, с помощью которого можно во всех задачах такого рода тотчас же определить, может ли быть совершен такой обход через какое угодно число и как угодно расположенных мостов или не может. Кенигсбергские же мосты расположены так, что их можно представить на следующем рисунке [рис.1], на котором A обозначает остров, а B , C иD – части континента, отделенные друг от друга рукавами реки. Семь мостов обозначены буквами a , b , c , d , e , f , g ".
(РИСУНОК 1.1)
По поводу обнаруженного им способа решать задачи подобного рода Эйлер писал [см. [5]стр. 102-104]:
"Это решение по своему характеру, по-видимому, имеет мало отношения к математике, и мне непонятно, почему следует скорее от математика ожидать этого решения, нежели от какого-нибудь другого человека, ибо это решение подкрепляется одним только рассуждением, и нет необходимости привлекать для нахождения этого решения какие-либо законы, свойственные математике. Итак, я не знаю, каким образом получается, что вопросы, имеющие совсем мало отношения к математике, скорее разрешается математиками, чем другими".
Так можно ли обойти Кенигсбергские мосты, проходя только один раз через каждый из этих мостов? Чтобы найти ответ, продолжим письмо Эйлера к Маринони:
Очень интересно - Реферат: Теория случайных функций
"Вопрос состоит в том, чтобы определить, можно ли обойти все эти семь мостов, проходя через каждый только однажды, или нельзя. Мое правило приводит к следующему решению этого вопроса. Прежде всего, нужно смотреть, сколько есть участков, разделенных водой, – таких, у которых нет другого перехода с одного на другой, кроме как через мост. В данном примере таких участков четыре – A , B , C , D . Далее нужно различать, является ли число мостов, ведущих к этим отдельным участкам, четным или нечетным. Так, в нашем случае к участку A ведут пять мостов, а к остальным – по три моста, т. е. Число мостов, ведущих к отдельным участкам, нечетно, а этого одного уже достаточно для решения задачи. Когда это определено, применяем следующее правило: если бы число мостов, ведущих к каждому отдельному участку, было четным, то тогда обход, о котором идет речь, был бы возможен, и в то же время можно было бы начать этот обход с любого участка. Если же из этих чисел два были бы нечетные, ибо только одно быть нечетным не может, то и тогда мог бы совершиться переход, как это предписано, но только начало обхода непременно должно быть взято от одного из тех двух участков, к которым ведет нечетное число мостов. Если бы, наконец, было больше двух участков, к которым ведет нечетное число мостов, то тогда такое движение вообще невозможно… если можно было привести здесь другие, более серьезные задачи, этот метод мог бы принести еще большую пользу и им не следовало бы пренебрегать".
Обоснование вышеприведенного правила можно найти в письме Л. Эйлера к своему другу Элеру от 3 апреля того же года. Мы перескажем ниже отрывок из этого письма.
Математик писал, что переход возможен, если на участке разветвления реки имеется не более двух областей, в которые ведет нечетное число мостов. Для того, чтобы проще представить себе это, будем стирать на рисунке уже пройденные мосты. Легко проверить, что если мы начнем двигаться в соответствии с правилами Эйлера, пересечем один мост и сотрем его, то на рисунке будет изображен участок, где опять имеется не более двух областей, в которые ведет нечетное число мостов, а при наличии областей с нечетным числом мостов мы будем располагаться в одной из них. Продолжая двигаться так далее, пройдем через все мосты по одному разу.
История с мостами города Кенигсберга имеет современное продолжение. Откроем, например, школьный учебник по математике под редакцией Н.Я. Виленкина для шестого класса. В нем на странице 98 в рубрике развития внимательности и сообразительности мы найдем задачу, имеющую непосредственное отношение к той, которую когда-то решал Эйлер.
Задача № 569 . На озере находится семь островов, которые соединены между собой так, как показано на рисунке 1.2. На какой остров должен доставить путешественников катер, чтобы они могли пройти по каждому мосту и только один раз? Почему нельзя доставить путешественников на остров A ?
Вам будет интересно - Курсовая работа: История статистики
(РИСУНОК 1.2)
Решение. Поскольку эта задача подобна задаче о Кенигсбергских мостах, то при ее решении мы также воспользуемся правилом Эйлера. В результате получим следующий ответ: катер должен доставить путешественников на остров E или F , чтобы они смогли пройти по каждому мосту один раз. Из того же правила Эйлера следует невозможность требуемого обхода, если он начнется с острова A .
В заключение отметим, что задача о Кенигсбергских мостах и подобные ей задачи вместе с совокупностью методов их исследования составляют очень важный в практическом отношении раздел математики, называемый теорией графов. Первая работа о графах принадлежала Л. Эйлеру и появилась в 1736 году. В дальнейшем над графами работали Кениг (1774-1833), Гамильтон (1805-1865), из современных математиков – К. Берж, О. Оре, А. Зыков.
§2. ОСНОВНЫЕ ТЕОРЕМЫ ТЕОРИИ ГРАФОВ
Теория графов, как было сказано выше, – дисциплина математическая, созданная усилиями математиков, поэтому ее изложение включает в себя и необходимые строгие определения. Итак, приступим к организованному введению основных понятий этой теории.
Определение 2.01. Графом называется совокупность конечного числа точек, называемых вершинами графа, и попарно соединяющих некоторые из этих вершин линий, называемых ребрами или дугами графа.
Похожий материал - Реферат: Теория управления
Это определение можно сформулировать иначе: графом называется непустое множество точек (вершин ) и отрезков (ребер ), оба конца которых принадлежат заданному множеству точек (см. рис. 2.1).
(РИСУНОК 2.1)
В дальнейшем вершины графа мы будем обозначать латинскими буквами A , B ,C ,D . Иногда граф в целом будем обозначать одной заглавной буквой.
Определение 2.02. Вершины графа, которые не принадлежат ни одному ребру, называются изолированными .
cwetochki.ru
Содержание
Краткий перечень основных понятий теории графов ……………….. 4
Понятия смежности, инцидентности, степени ……………………….. 7
Маршруты и пути ………………………………………………………. 7
Матрицы смежности и инцидентности…..……………………………. 7
Связность. Компоненты связности …………………………………….. 8
Матрицы достижимости и связности ………….………………………. 9
Расстояния в графе …………………………..…………….……………. 9
Образ и прообраз вершины и множества вершин …………..……….. 10
Нагруженные графы ………………..………………………………….. 11
Деревья и циклы …………………………………….………….……… 12
Решение контрольных задач по теме «Теория графов»……………………………………………...…………………... 13
Задание 1. Компоненты сильной связности ориентированного графа.……………………………………………………………………. 13
Задание 2. Расстояния в ориентированном графе..………………...... 16
Задание 3. Минимальный путь в нагруженном ориентированном графе...……...…………………………………………………………... 20
Задание 4. Эйлеровы циклы и цепи ……..………………………….… 23
Задание 5. Минимальное основное дерево...………...…………...…… 25
Задание 6. Задача о коммивояжёре...………...…………...…………… 27
Задания для самостоятельного решения ………….………......……… 34
Список литературы…………………………………………………..…. 37
Краткий перечень основных понятий теории графов.
Теория графов как теоретическая дисциплина может рассматриваться как раздел дискретной математики, исследующий свойства конечных множеств (бесконечные графы не будут вводиться в рассмотрение) с заданными отношениями между их элементами. Как прикладная дисциплина теория графов позволяет описывать и исследовать многие физические, технические, экономические, биологические, социальные и другие системы. Например, графом, изображенным на рис. 1, в котором точки − вершины графа − города, линии, соединяющие вершины − ребра − дороги, соединяющие города, описывается так называемая транспортная задача (задача нахождения кратчайшего пути из одного города - пункта в другой).
Рис. 1.
Формальное определение графа таково. Пусть задано конечное множество V, состоящее из n элементов, называемых вершинами графа, и подмножество X декартова произведения V×V, то есть , называемое множеством дуг, тогда ориентированным графом D называется совокупность (V, X). Неориентированным графом G называется совокупность множества V и множества ребер − неупорядоченных пар элементов, каждый из которых принадлежит множеству V.
Одинаковые пары - параллельные или кратные ребра;
Кратностью ребер называют количество одинаковых пар.
Рис.2.
Например, кратность ребра {v1, v2} в графе, изображенном на рис. 2, равна двум, кратность ребра {v3, v4} − трем.
Псевдограф − граф, в котором есть петли и/или кратные ребра.
Мультиграф − псевдограф без петель.
Граф − мультиграф, в котором ни одна пара не встречается более одного раза.
Граф называется ориентированным, если пары (v, w) являются упорядоченными.
Ребра ориентированного графа называются дугами.
Итак, используемые далее обозначения:
V – множество вершин;
X – множество ребер или дуг;
V (или vi)– вершина или номер вершины;
G, G0 - неориентированный граф;
D, D0 – ориентированный;
{v, w} − ребра неориентированного графа;
{v, v} – обозначение петли;
(v, w) − дуги в ориентированном графе;
V, w - вершины, x, y,z – дуги и ребра;
N(G), n(D) количество вершин графа;
M(G) - количество ребер, m(D) - количество дуг.
Примеры
1) Ориентированный граф D=(V, X), V={v1, v2, v3, v4},
X={x1=(v1,v2), x2=(v1,v2), x3=(v2,v2), x4=(v2,v3)}.
Рис. 3.
2) Неориентированный граф G=(V, X), V={v1, v2, v3, v4, v5},
X={x1={v1,v2}, x2={v2,v3}, x3={v2,v4}, x4={v3,v4}}.
Рис. 4.
Понятия смежности, инцидентности, степени
Если x={v, w} - ребро, то v и w − концы ребра x.
Если x=(v, w) - дуга ориентированного графа, то v − начало, w – конец дуги.
Вершина v и ребро x неориентированного графа (дуга x ориентированного графа) называются инцидентными, если v является концом ребра x (началом или концом дуги x ).
Вершины v, w называются смежными, если {v, w}ÎX.
Степенью вершины v графа G называется число d(v) ребер графа G, инцидентных вершине v.
Вершина графа, имеющая степень 0 называется изолированной, а степень 1 – висячей.
Полустепенью исхода (захода) вершины v ориентированного графа D называется число d+(v) (d-(v)) дуг ориентированного графа D, исходящих из v (заходящих в v).
Следует заметить, что в случае ориентированного псевдографа вклад каждой петли инцидентной вершине v равен 1 как в d+(v), так и в d-(v).
Маршруты и пути
Последовательность v1x1v2x2v3...xkvk+1, (где k³1, viÎV, i=1,...,k+1, xiÎX, j=1,...,k), в которой чередуются вершины и ребра (дуги) и для каждого j=1,...,k ребро (дуга) xj имеет вид {vj, vj+1} (для ориентированного графа (vj, vj+1)), называется маршрутом, соединяющим вершины v1 и vk+1 (путем из v1 в vk+1).
Пример
В графе, изображенном на рис.4, v1x1v2x2v3x4v4x3v2 - маршрут, v2x2v3x4v4 – подмаршрут;
Маршрут можно восстановить и по такой записи x1x2x4x3 ;
Если кратности ребер (дуг) равны 1, можно записать и так v1v2v3v4v2 .
Цепь − незамкнутый маршрут (путь), в котором все ребра (дуги) попарно различны.
Цикл − замкнутая цепь (в неориентированном графе).
referatbox.com
Муниципальное общеобразовательное учреждение «Средняя общеобразовательная школа № 6»
Реферат на тему: «Теория графов»
Подготовила: Майорова Екатерина, 8Г класс Учитель: Малова Татьяна Алексеевна
Содержание:
I. Введение
II. Основная часть. 1.История возникновения теории графов.
2.Некоторые задачи теории графов. 2.1 Логические задачи 2.2 Задачи на связность. 2.3 Задачи по теореме Эйлера о нечетных вершинах
3.Применение теории графов в различных сферах деятельности. 3.1.Графы и информация 3.2.Графы и химия. 3.3.Графы и биология 3.4.Графы и физика
III. Заключение.
IV. Список литературы.
I. Введение.
Я выбрала эту тему, потому что она была и остается актуальной в наше время.
Сейчас почти в любой отрасли науки и техники встречается применение графов. В физике - при построении электрических схем, в химии и биологии - при изучении молекул и их цепочек, в географии – при составлении карт, в истории – при составлении родословной, в геометрии – в чертежах многоугольников, многогранников, пространственных фигур, в экономике – при решении задач о выборе оптимального пути для потоков грузового транспорта (схем авиалиний, метро, железных дорог).
Графами являются блок-схемы программ для ЭВМ, сетевые графики строительства. С помощью графов решается задача о назначении на должности. А именно: если имеется несколько вакантных должностей и группы лиц, желающих их занять, причем каждый из претендентов имеет квалификацию для нескольких должностей, то при каких условиях каждый из претендентов сможет получить работу по одной из своих специальностей? Теория графов в школьной программе не изучается, но широко применяется при решении математических олимпиадных задач.
II. 1. История возникновения теории графов
Изучив информацию Интернет-ресурсов, я для себя открыла следующие интересные факты об истории теории графов. Родоначальником теории графов принято считать математика Леонарда Эйлера. Историю возникновения этой теории можно проследить по переписке великого ученого. В ней он сообщал, что ему была предложена задача о семи мостах Кенигсберга. Спрашивалось, может ли кто-нибудь непрерывно обойти их, проходя только однажды через каждый мост. И ему сразу же было сообщено, что никто еще до сих пор не мог это проделать, но никто и не доказал, что это невозможно. Вопрос этот показался ему достойным внимания тем, что «…Для его решения недостаточны ни геометрия, ни алгебра, ни комбинаторное искусство...». После долгих размышлений он нашел легкое правило, основанное на вполне убедительном доказательстве, с помощью которого можно во всех задачах такого рода определить, может ли быть совершен такой обход через какое угодно число и как угодно расположенных мостов или не может. Кенигсбергские же мосты расположены так, что их можно представить на рисунке, на котором А обозначает остров, а В, С и D - части континента, отделенные друг от друга рукавами реки. Семь мостов обозначены буквами а, b, с, d, е, f, g. Кенигсбергские мосты.
Математик писал, что переход возможен, если на участке разветвления реки имеется не более двух областей, в которые ведет нечетное число мостов.
Для того чтобы проще представить себе это, будем стирать на рисунке уже пройденные мосты. Легко проверить, что если начать двигаться в соответствии с правилами Эйлера, пересечь один мост и стереть его, то на рисунке будет изображен участок, где опять имеется не более двух областей, в которые ведет нечетное число мостов. А при наличии областей с нечетным числом мостов мы будем располагаться в одной из них. Продолжая двигаться так далее, пройдем через все мосты по одному разу. История с мостами города Кенигсберга имеет современное продолжение. В некоторых учебниках математики или в дополнительных материалах (приложениях) учебника можно встретить задачи, чьё решение основано именно на предложенном Эйлером способе. Я поняла, что в ходе рассуждений Эйлер пришёл к следующим выводам:
docus.me
Федеральное агентство по образованию РФ
ГОУ ВПО «УГТУ-УПИ»
Курсовая работа
по теории информационных систем №
(ДИСЦИПЛИНА)
на тему: Теория графов и их применение
Преподаватель Александров О.Е
(ФИО)
Студент гр. № Ит44010ди Риасс А.В.
(ФИО)
номер зачетной книжки 17436537
Екатеринбург
2008
Курсовая работа по _____ теории информационных систем
(ДИСЦИПЛИНА)
№ записи в книге регистрации дата регистрации 200 8 г.
Преподаватель ___Александров О.Е.________________________________
(ФИО)
Студент Риасс А.В. группа № Ит44010ди
(ФИО)
Деканат ФДО
Содержание:
1. История возникновения графов……………………………………………………………3
2. Начальные понятия теории графов………………………………………………………5
3. Определения графа…………………………………………………………………………………5
4. Графы и бинарные отношения……………………………………………………………….7
5. Откуда берутся графы…………………………………………………………………………….7
6. Число графов……………………………………………………………………………………………8
7. Смежность, инцидентность, степени……………………………………………………..8
11. Изоморфизм…………………………………………………………………………………………..11
16. Деревья……………………………………………………………………………………………………15
20. ПРИМЕНЕНИЕ ТЕОРИИ ГРАФОВ В ТЕОРИИ ИНФОРМАЦИИ………………….23
1. ИСТОРИЯ ВОЗНИКНОВЕНИЯ ТЕОРИИ ГРАФОВ.
Родоначальником теории графов принято считать математика Леонарда Эйлера (1707-1783). Историю возникновения этой теории можно проследить по переписке великого ученого. Вот перевод латинского текста, который взят из письма Эйлера к итальянскому математику и инженеру Маринони, отправленного из Петербурга 13 марта 1736 года [см. [5]стр. 41-42]:
"Некогда мне была предложена задача об острове, расположенном в городе Кенигсберге и окруженном рекой, через которую перекинуто семь мостов. Спрашивается, может ли кто-нибудь непрерывно обойти их, проходя только однажды через каждый мост. И тут же мне было сообщено, что никто еще до сих пор не мог это проделать, но никто и не доказал, что это невозможно. Вопрос этот, хотя и банальный, показался мне, однако, достойным внимания тем, что для его решения недостаточны ни геометрия, ни алгебра, ни комбинаторное искусство… После долгих размышлений я нашел легкое правило, основанное на вполне убедительном доказательстве, с помощью которого можно во всех задачах такого рода тотчас же определить, может ли быть совершен такой обход через какое угодно число и как угодно расположенных мостов или не может. Кенигсбергские же мосты расположены так, что их можно представить на следующем рисунке [рис.1], на котором A обозначает остров, а B, C и D – части континента, отделенные друг от друга рукавами реки. Семь мостов обозначены буквами a, b, c, d, e, f, g ".
(РИСУНОК 1.1)
По поводу обнаруженного им способа решать задачи подобного рода Эйлер писал [см. [5]стр. 102-104]:
"Это решение по своему характеру, по-видимому, имеет мало отношения к математике, и мне непонятно, почему следует скорее от математика ожидать этого решения, нежели от какого-нибудь другого человека, ибо это решение подкрепляется одним только рассуждением, и нет необходимости привлекать для нахождения этого решения какие-либо законы, свойственные математике. Итак, я не знаю, каким образом получается, что вопросы, имеющие совсем мало отношения к математике, скорее разрешается математиками, чем другими".
Так можно ли обойти Кенигсбергские мосты, проходя только один раз через каждый из этих мостов? Чтобы найти ответ, продолжим письмо Эйлера к Маринони:
"Вопрос состоит в том, чтобы определить, можно ли обойти все эти семь мостов, проходя через каждый только однажды, или нельзя. Мое правило приводит к следующему решению этого вопроса. Прежде всего, нужно смотреть, сколько есть участков, разделенных водой, – таких, у которых нет другого перехода с одного на другой, кроме как через мост. В данном примере таких участков четыре – A, B, C, D. Далее нужно различать, является ли число мостов, ведущих к этим отдельным участкам, четным или нечетным. Так, в нашем случае к участку A ведут пять мостов, а к остальным – по три моста, т. е. Число мостов, ведущих к отдельным участкам, нечетно, а этого одного уже достаточно для решения задачи. Когда это определено, применяем следующее правило: если бы число мостов, ведущих к каждому отдельному участку, было четным, то тогда обход, о котором идет речь, был бы возможен, и в то же время можно было бы начать этот обход с любого участка. Если же из этих чисел два были бы нечетные, ибо только одно быть нечетным не может, то и тогда мог бы совершиться переход, как это предписано, но только начало обхода непременно должно быть взято от одного из тех двух участков, к которым ведет нечетное число мостов. Если бы, наконец, было больше двух участков, к которым ведет нечетное число мостов, то тогда такое движение вообще невозможно… если можно было привести здесь другие, более серьезные задачи, этот метод мог бы принести еще большую пользу и им не следовало бы пренебрегать".
Обоснование вышеприведенного правила можно найти в письме Л. Эйлера к своему другу Элеру от 3 апреля того же года. Мы перескажем ниже отрывок из этого письма.
Математик писал, что переход возможен, если на участке разветвления реки имеется не более двух областей, в которые ведет нечетное число мостов. Для того, чтобы проще представить себе это, будем стирать на рисунке уже пройденные мосты. Легко проверить, что если мы начнем двигаться в соответствии с правилами Эйлера, пересечем один мост и сотрем его, то на рисунке будет изображен участок, где опять имеется не более двух областей, в которые ведет нечетное число мостов, а при наличии областей с нечетным числом мостов мы будем располагаться в одной из них. Продолжая двигаться так далее, пройдем через все мосты по одному разу.
Графы являются существенным элементом математических моделей в самых разнообразных областях науки и практики. Они помогают наглядно представить взаимоотношения между объектами или событиями в сложных системах. Многие алгоритмические задачи дискретной математики могут быть сформулированы как задачи, так или иначе связанные с графами, например задачи, в которых требуется выяснить какие-либо особенности устройства графа, или найти в графе часть, удовлетворяющую некоторым требованиям, или построить граф с заданными свойствами.
Для описания строения различных систем, состоящих из связанных между собой элементов, часто используют графические схемы, изображая элементы точками (кружками, прямоугольниками и т.д.), а связи между ними - линиями или стрелками, соединяющими элементы. При этом получаются диаграммы вроде тех, что показаны на рис. 1.1.
Рис. 1.1.
На таких диаграммах часто ни способ изображения элементов, ни форма или длина линий не имеют значения - важно лишь, какие именно пары элементов соединены линиями. Если посмотреть внимательно, то можно заметить, что рисунки 1.1а и 1.1 б изображают одну и ту же структуру связей между элементами 
, 
, 
, 
, 
, 
. Эту же структуру можно описать, не прибегая к графическому изображению, а просто перечислив пары связанных между собой элементов: 
, 
, 
, 
, 
, 
, 
. Таким образом, когда мы отвлекаемся от всех несущественных подробностей, у нас остаются два списка: список элементов и список пар элементов. Вместе они составляют то, что математики называют графом. Из этого примера видно, что понятие графа само по себе не связано напрямую с геометрией или графикой. Тем не менее, возможность нарисовать граф - одна из привлекательных черт этого математического объекта.
Термин "граф" неоднозначен, это легко заметить, сравнивая приводимые в разных книгах определения. Однако во всех этих определениях есть кое-что общее. В любом случае граф состоит из двух множеств - множества вершин и множества ребер, причем для каждого ребра указана пара вершин, которые это ребро соединяет. Вершины и ребра называются элементами графа. Здесь будут рассматриваться только конечные графы, то есть такие, у которых оба множества конечны. Чтобы получить законченное определение графа того или иного типа, необходимо уточнить еще три момента.
Ориентированный или неориентированный?
Прежде всего, нужно договориться, считаем ли мы пары 
и 
различными. Если да, то говорят, что рассматриваются упорядоченные пары (порядок элементов в паре важен), если нет - неупорядоченные. Если ребро 
соединяет вершину 
с вершиной 
и пара считается упорядоченной, то это ребро называется ориентированным, вершина - его началом, вершина - концом. Если же эта пара считается неупорядоченной, то ребро называется неориентированным, а обе вершины - его концами. Чаще всего рассматривают графы, в которых все ребра имеют один тип - либо ориентированные, либо неориентированные. Соответственно и весь граф называют ориентированным или неориентированным. На рисунках ориентацию ребра (направление от начала к концу) указывают стрелкой. На рис. 1.1 показаны неориентированные графы, а на рис. 1.2 - ориентированные.
Кратные ребра.
Следующий пункт, требующий уточнения, - могут ли разные ребра иметь одинаковые начала и концы? Если да, то говорят, что в графе допускаются кратные ребра. Граф с кратными ребрами называют также мультиграфом. На рис. 1.2 изображены два графа, левый является ориентированным мультиграфом, а правый - ориентированным графом без кратных ребер.
Петли.
Ребро, которому поставлена в соответствие пара вида 
, то есть ребро, соединяющее вершину с нею же самой, называется петлей. Если такие ребра не допускаются, то говорят, что рассматриваются графы без петель.
Рис. 1.2.
Комбинируя эти три признака, можно получить разные варианты определения понятия графа. Особенно часто встречаются неориентированные графы без петель и кратных ребер. Такие графы называют обыкновенными. Если в графе нет кратных ребер, то можно просто отождествить ребра с соответствующими парами вершин - считать, что ребро это и есть пара вершин. Чтобы исключить петли, достаточно оговорить, что вершины, образующие ребро, должны быть различны. Это приводит к следующему определению обыкновенного графа.
Определение. Обыкновенным графом называется пара 
, где 
- конечное множество, - множество неупорядоченных пар различных элементов из . Элементы множества называются вершинами графа, элементы множества - его ребрами.
Слегка модифицируя это определение, можно получить определения других типов графов без кратных ребер: если заменить слово "неупорядоченных" словом "упорядоченных", получится определение ориентированного графа без петель, если убрать слово "различных", получится определение графа с петлями. Ориентированный граф часто называют орграфом.
В дальнейшем термин "граф" мы будем употреблять в смысле "обыкновенный граф", а рассматривая другие типы графов, будем специально это оговаривать.
Множество вершин графа 
будем обозначать через 
, множество ребер - 
, число вершин - 
, число ребер - 
.
Из определения видно, что для задания обыкновенного графа достаточно перечислить его вершины и ребра, причем каждое ребро должно быть парой вершин. Положим, например, 
, 
. Тем самым задан граф с 
, 
. Если граф не слишком велик, то более наглядно представить его можно с помощью рисунка, на котором вершины изображаются кружками или иными значками, а ребра - линиями, соединяющими вершины. Заданный выше граф показан на рисунке 1.3. Мы будем часто пользоваться именно этим способом представления графа, при этом обозначения вершин иногда будут помещаться внутри кружков, изображающих вершины, иногда рядом с ними, а иногда, когда имена вершин несущественны, и вовсе опускаться.
Рис. 1.3.
Напомним, что бинарным отношением на множестве называется любое подмножество 
множества 
, состоящего из всевозможных упорядоченных пар элементов множества . Каждому такому отношению можно поставить в соответствие граф отношения 
. Сравнивая с тем, что говорилось выше об определениях различных типов графов, видим, что понятие бинарного отношения эквивалентно понятию ориентированного графа с петлями. Другие типы графов без кратных ребер - это частные виды бинарных отношений. Отношение называется рефлексивным, если для любого 
пара 
принадлежит , и антирефлексивным, если ни одна такая пара не принадлежит . Отношение называется симметричным, если из 
следует, что 
. В графе антирефлексивного и симметричного отношения нет петель и для каждой пары вершин либо нет ни одного, либо есть два ребра, соединяющих эти вершины. Если в таком графе каждую пару ориентированных ребер, соединяющих одни и те же две вершины, заменить одним неориентированным ребром, то получится обыкновенный граф.
Легко найти примеры графов в самых разных областях науки и практики. Сеть дорог, трубопроводов, электрическая цепь, структурная формула химического соединения, блок-схема программы - в этих случаях графы возникают естественно и видны "невооруженным глазом". При желании графы можно обнаружить практически где угодно. Это наглядно показано в книге Д.Кнута [D.E.Knuth, "The Stanford GraphBase"] - графы извлекаются из романа "Анна Каренина", из картины Леонардо да Винчи, из материалов Бюро Экономического Анализа США и из других источников.
Немало поводов для появления графов и в самой математике. Наиболее очевидный пример - любой многогранник в трехмерном пространстве. Вершины и ребра многогранника можно рассматривать как вершины и ребра графа. При этом мы отвлекаемся от того, как расположены элементы многогранника в пространстве, оставляя лишь информацию о том, какие вершины соединены ребрами. На рис. 1.4 показаны три способа изобразить один и тот же граф трехмерного куба.
Рис. 1.4.
Еще один способ образования графов из геометрических объектов иллюстрирует рис. 1.5. Слева показаны шесть кругов на плоскости, а справа - граф, в котором каждая вершина соответствует одному из этих кругов и две вершины соединены ребром в том и только том случае, когда соответствующие круги пересекаются. Такие графы называют графами пересечений. Можно построить граф пересечений семейства интервалов на прямой, или дуг окружности, или параллелепипедов. Вообще, для любого семейства множеств 
можно построить граф пересечений с множеством вершин 
, в котором ребро 
имеется тогда и только тогда, когда 
и 
. Известно, что любой граф можно представить как граф пересечений некоторого семейства множеств.
Рис. 1.5.
Возьмем какое-нибудь множество , состоящее из 
элементов, и будем рассматривать всевозможные (обыкновенные!) графы с множеством вершин . Обозначим число таких графов через 
. Эти графы различаются только множествами ребер, а каждое ребро - это неупорядоченная пара различных элементов из . В комбинаторике такие пары называются сочетаниями из по 2, их число равно
Каждая пара может быть включена или не включена в множество ребер графа. Применяя правило произведения, приходим к следующему результату:
Теорема 1. 
.
Если в графе имеется ребро 
, то говорят, что вершины и смежны в этом графе, ребро инцидентно каждой из вершин , , а каждая из них инцидентна этому ребру.
Множество всех вершин графа, смежных с данной вершиной , называется окрестностью этой вершины и обозначается через 
.
На практике удобным и эффективным при решении многих задач способом задания графа являются так называемые списки смежности. Эти списки могут быть реализованы различными способами в виде конкретных структур данных, но в любом случае речь идет о том, что для каждой вершины перечисляются все смежные с ней вершины, т.е. элементы множества . Такой способ задания дает возможность быстрого просмотра окрестности вершины.
Число вершин, смежных с вершиной , называется степенью вершины и обозначается через 
.
Если сложить степени всех вершин некоторого графа, то каждое ребро внесет в эту сумму вклад, равный 2, поэтому справедливо следующее утверждение:
Теорема 2. 
.
Это равенство известно как "лемма о рукопожатиях". Из него следует, что число вершин нечетной степени в любом графе четно.
Вершину степени 
называют изолированной.
Граф называют регулярным степени 
, если степень каждой его вершины равна .
Набор степеней графа - это последовательность степеней его вершин, выписанных в неубывающем порядке.
Рассмотрим некоторые особенно часто встречающиеся графы.
Пустой граф - граф, не содержащий ни одного ребра. Пустой граф с множеством вершин 
обозначается через 
.
Полный граф - граф, в котором каждые две вершины смежны. Полный граф с множеством вершин обозначается через 
.
Граф 
, в частности, имеет одну вершину и ни одного ребра. Очевидно, 
. Будем считать также, что существует граф 
, у которого 
.
Цепь(путь) 
- граф с множеством вершин и множеством ребер 
.
Цикл 
- граф, который получается из графа добавлением ребра 
.
Все эти графы при 
показаны на рис. 1.6
Рис. 1.6.
Пусть - граф с вершинами, причем 
. Построим квадратную матрицу порядка , в которой элемент 
, стоящий на пересечении строки с номером 
и столбца с номером 
, определяется следующим образом:
Она называется матрицей смежности графа. Матрицу смежности можно построить и для ориентированного графа, и для неориентированного, и для графа с петлями. Для обыкновенного графа она обладает двумя особенностями: из-за отсутствия петель на главной диагонали стоят нули, а так как граф неориентированный, то матрица симметрична относительно главной диагонали. Обратно, каждой квадратной матрице порядка , составленной из нулей и единиц и обладающей двумя указанными свойствами, соответствует обыкновенный граф с множеством вершин .
Другая матрица, ассоциированная с графом - это матрица инцидентности. Для ее построения занумеруем вершины графа числами от 1 до , а ребра - числами от 1 до 
. Матрица инцидентности 
имеет строк и столбцов, а ее элемент 
равен 1, если вершина с номером инцидентна ребру с номером , в противном случае он равен нулю. На рис. 1.7 показан граф с занумерованными вершинами и ребрами и его матрицы смежности и инцидентности.
Рис. 1.7.
Для ориентированного графа матрица инцидентности определяется несколько иначе: ее элемент равен 1, если вершина является началом ребра , и равен 
, если она является концом этого ребра, и он равен , если эта вершина и это ребро не инцидентны друг другу.
Часто, особенно когда графы используются для моделирования реальных систем, их вершинам, или ребрам, или и тем, и другим приписываются некоторые числа. Природа этих чисел может быть самая разнообразная. Например, если граф представляет собой модель железнодорожной сети, то число, приписанное ребру, может указывать длину перегона между двумя станциями, или наибольший вес состава, который допустим для этого участка пути, или среднее число поездов, проходящих через этот участок в течение суток и т.п. Что бы ни означали эти числа, сложилась традиция называть их весами, а граф с заданными весами вершин и 
или ребер - взвешенным графом.
На рис. 1.8 изображены два графа с одним и тем же множеством вершин 
. При внимательном рассмотрении можно обнаружить, что это разные графы - в левом имеется ребро 
, в правом же такого нет. В то же время, если не обращать внимания на наименования вершин, то эти графы явно одинаково устроены: каждый из них - цикл из четырех вершин. Во многих случаях при исследовании строения графов имена или номера вершин не играют роли, и такие графы, один из которых получается из другого переименованием вершин, удобнее было бы считать одинаковыми. Для того чтобы это можно было делать "на законном основании", вводится понятие изоморфизма графов.
Рис. 1.8.
Определение. Графы 
и 
называются изоморфными, если существует такая биекция 
множества 
на множество 
, что 
тогда и только тогда, когда 
. Отображение в этом случае называется изоморфизмом графа на граф .
Тот факт, что графы и изоморфны, записывается так: 
.
Для графов, изображенных на рис. 1.8, изоморфизмом является, например, отображение, задаваемое следующей таблицей:
Заметим, что в этом примере есть и другие изоморфизмы первого графа на второй.
Сформулированное определение изоморфизма годится и для ориентированных графов, нужно только обе упоминаемые в нем пары вершин считать упорядоченными.
Изоморфизм - бинарное отношение на множестве графов. Очевидно, что это отношение рефлексивно, симметрично и транзитивно, то есть является отношением эквивалентности. Классы эквивалентности называются абстрактными графами. Когда говорят, что рассматриваются абстрактные графы, это означает, что изоморфные графы считаются одинаковыми. Абстрактный граф можно представлять себе как граф, у которого стерты имена (пометки) вершин, поэтому абстрактные графы иногда называют также непомеченными графами.
Для получения новых графов можно использовать разнообразные операции над графами. Здесь мы рассмотрим два вида операций - локальные, при которых заменяются, удаляются или добавляются отдельные элементы графа, и алгебраические, когда новый граф строится по определенным правилам из нескольких имеющихся.
Простейшая операция - удаление ребра. При удалении ребра сохраняются все вершины графа и все его ребра, кроме удаляемого. Обратная операция - добавление ребра.
При удалении вершины вместе с вершиной удаляются и все инцидентные ей ребра. Граф, получаемый из графа удалением вершины , обозначают 
. При добавлении вершины к графу добавляется новая изолированная вершина. С помощью операций добавления вершин и ребер можно "из ничего", то есть из графа , построить любой граф.
Операция стягивания ребра определяется следующим образом. Вершины и удаляются из графа, к нему добавляется новая вершина 
и она соединяется ребром с каждой вершиной, с которой была смежна хотя бы одна из вершин 
.
Операция подразбиения ребра действует следующим образом. Из графа удаляется это ребро, к нему добавляется новая вершина и два новых ребра и 
. На рис. 1.10 изображены исходный граф , граф 
, полученный из него стягиванием ребра 
и 
, полученный подразбиением того же ребра. В обоих случаях вновь добавленная вершина обозначена цифрой 
.
Рис. 1.10.
Граф называется подграфом графа , если 
, 
. Всякий подграф может быть получен из графа удалением некоторых вершин и ребер. На рис. 1.11 изображены граф и его подграфы , , 
, 
.
Рис. 1.11.
Подграф графа называется остовным, если 
. Остовный подграф может быть получен из графа удалением некоторых ребер, вершины же остаются в неприкосновенности. На рис. 1.11 - остовный подграф графа , а , и не являются остовными подграфами.
Другая важная разновидность подграфов - порожденные подграфы. Пусть задан граф 
и в нем выбрано множество вершин 
. Рассмотрим подграф 
, где 
состоит из всех тех ребер графа , у которых оба конца принадлежат 
. Говорят, что этот подграф порожден множеством вершин . Он обозначается через 
. Порожденный подграф может быть получен из графа удалением "лишних" вершин, т.е. вершин, не принадлежащих .
Можно определить также подграф, порожденный множеством ребер 
. Это подграф 
, где 
состоит из всех вершин, инцидентных ребрам из .
На рис. 1.11 - подграф графа , порожденный множеством вершин 
, т.е. 
, он же порождается множеством ребер 
; подграф не порождается множеством вершин, но порождается множеством ребер 
; подграф не является ни остовным, ни порожденным в каком-либо смысле.
Поскольку граф состоит из двух множеств (вершины и ребра), то различные операции над множествами естественным образом порождают соответствующие операции над графами. Например, объединение двух графов и определяется как граф 
, у которого 
, 
, а пересечение - как граф 
, у которого 
, 
. Обе операции иллюстрирует рис. 1.12.
Рис. 1.12.
Дополнением (дополнительным графом) к графу называется граф 
, у которого множество вершин то же, что у , а множество ребер является дополнением множества до множества всех неупорядоченных пар вершин. Иначе говоря, две различные вершины смежны в графе тогда и только тогда, когда они несмежны в графе . Например, 
. Другой пример показан на рис. 1.13. Очевидно, что всегда 
.
Рис. 1.13.
Под суммой 
двух абстрактных графов понимают объединение графов с непересекающимися множествами вершин. Точнее говоря, имеется в виду следующее. Сначала вершинам графов-слагаемых присваиваются имена (пометки, номера) так, чтобы множества вершин не пересекались, затем полученные графы объединяются. Операция сложения ассоциативна, то есть 
для любых трех графов. Поэтому можно образовывать сумму любого числа графов, не указывая порядка действий с помощью скобок. Если складываются 
экземпляров одного и того же графа , то полученный граф обозначается через 
. Например, 
. На рис. 1.14 изображен граф 
.
Рис. 1.14.
Рис. 1.15.
Соединением двух графов и называется граф, получаемый из их суммы добавлением всех ребер, соединяющих вершины первого слагаемого с вершинами второго. Будем записывать эту операцию как 
. На рис. 1.15 представлен граф 
. Легко видеть, что операции сложения и соединения графов связаны друг с другом следующими простыми соотношениями:
Введем еще два типа специальных графов, которые легко описываются с помощью операции соединения. Первый - полный двудольный граф 
. В этом графе множество вершин разбито на два подмножества (доли), в одном из которых 
вершин, в другом 
, и две вершины в нем смежны тогда и только тогда, если они принадлежат разным подмножествам. Второй - колесо 
. На рис. 1.16 показаны графы 
и 
.
Рис. 1.16.
Произведение 
графов и определяется следующим образом. Множеством вершин графа является декартово произведение множеств и , то есть вершины этого графа - упорядоченные пары 
, где 
- вершина первого сомножителя, 
- вершина второго. Вершины 
и 
в смежны тогда и только тогда, если 
и 
смежна с 
в графе , или 
и 
смежна с 
в графе . С помощью операции произведения можно выразить некоторые важные графы через простейшие. Например, произведение двух цепей дает прямоугольную решетку (см. рис. 1.17). Если один из сомножителей превратить в цикл, добавив одно ребро, то прямоугольная решетка превратится в цилиндрическую, а если и второй сомножитель превратить в цикл, то получится тороидальная решетка.
Рис. 1.17.
Другой пример - - мерный куб 
, определяемый следующим образом. Вершинами его являются всевозможные упорядоченные двоичные наборы длины . Всего, таким образом, в этом графе 
вершин. Вершины 
и 
смежны в нем тогда и только тогда, когда наборы и различаются точно в одной координате. С помощью операции произведения граф можно определить рекурсивно:
На рис. 1.18 показано, как получается 
из 
.
Рис. 1.18.
Деревом называется связный граф, не имеющий циклов. В графе без циклов, таким образом, каждая компонента связности является деревом. Такой граф называют лесом.
Из теоремы 2 предыдущей лекции следует, что во всяком дереве, в котором не меньше двух вершин, имеется вершина степени 1. Такие вершины называют висячими вершинами, или листьями. В действительности легко доказать, что в каждом дереве не меньше двух листьев, а цепь - пример дерева, в котором точно два листа.
В следующих двух теоремах устанавливаются некоторые свойства деревьев.
Теорема 1. Граф с вершинами и ребрами является деревом тогда и только тогда, когда он удовлетворяет любым двум из следующих трех условий:
Доказательство.
Первые два условия вместе составляют определение дерева. Покажем, что выполнение любых двух из условий (1)-(3) влечет за собой выполнение третьего.
(1) и (2) 
(3). Индукция по числу вершин. При 
утверждение очевидно. При 
в дереве имеется хотя бы один лист. Если из дерева удалить лист, то снова получится дерево, так как циклов не появится, а связность, очевидно, сохранится. В этом новом дереве 
вершин и, по предположению индукции, 
ребра. Следовательно, в исходном дереве было ребро.
(2) и (3) (1). Пусть в графе, не имеющем циклов, ребро, а его компонентами связности являются 
, причем 
состоит из 
вершин, 
. Каждая компонента является деревом, поэтому, как доказано выше, число ребер в равно 
, а всего ребер в графе 
. Значит, 
и граф связен.
(1) и (3) (2). Рассмотрим связный граф с ребром. Если бы в нем был цикл, то, удалив любое цикловое ребро, мы получили бы связный граф с меньшим числом ребер. Можно продолжать такое удаление ребер до тех пор, пока не останется связный граф без циклов, то есть дерево. Но ребер в этом дереве было бы меньше, чем , а это противоречит доказанному выше.
Теорема 2. Если - дерево, то
в любая пара вершин соединена единственным путем;
при добавлении к любого нового ребра образуется цикл;
при удалении из любого ребра он превращается в несвязный граф.
Доказательство.
Существование пути между любыми двумя вершинами следует из связности дерева. Допустим, что в некотором дереве существуют два различных пути, соединяющих вершины и . Начальные отрезки этих путей совпадают (оба пути начинаются в одной и той же вершине ). Пусть - последняя вершина этого совпадающего начала, а после в одном пути следует вершина , а в другом - вершина . Рассмотрим ребро 
. Если его удалить из графа, то в оставшемся подграфе вершины и будут соединимыми - соединяющий их маршрут можно построить так: взять отрезок первого пути от до и к нему присоединить отрезок второго от до , взятый в обратном порядке. Но это означает, что ребро не является перешейком. Однако из теоремы 4 предыдущей лекции следует, что в дереве каждое ребро является перешейком. Этим доказано утверждение 1). Утверждения 2) и 3) следуют из 1).
Отметим, что единственный путь, соединяющий две вершины дерева, всегда простой (если путь не является простым, в нем обязательно содержится цикл).
Геометрический граф - это плоская фигура, состоящая из вершин - точек плоскости и ребер - линий, соединяющих некоторые пары вершин. Всякий граф можно многими способами представить геометрическим графом, и мы уже не раз пользовались этой возможностью. На рис. 3.6 показаны два геометрических графа 
и 
, представляющих, как нетрудно проверить, один и тот же обыкновенный граф. Простое устройство этого графа, очевидное на изображении слева, не так легко обнаружить, рассматривая изображение справа. Главная причина этого в том, что в ребра не имеют "лишних" пересечений.
Рис. 3.6.
Геометрический граф, в котором никакие два ребра не имеют общих точек, кроме инцидентной им обоим вершины, называют плоским графом, а по отношению к представляемому им обыкновенному графу - его плоской укладкой. Не каждый граф допускает плоскую укладку. Граф, для которого существует плоская укладка, называется планарным графом. Кроме удобства визуального анализа, есть немало поводов, в том числе и сугубо практических, для интереса к планарным графам и их плоским укладкам.
Если плоскость разрезать по ребрам плоского графа, она распадется на связные части, которые называют гранями. Всегда имеется одна неограниченная внешняя грань, все остальные грани называются внутренними. Если в плоском графе нет циклов, то у него имеется только одна грань. Если же циклы есть, то граница каждой грани содержит цикл, но не обязательно является циклом. На рис. 3.7 показан плоский граф с пятью занумерованными гранями. Граница грани с номером 3 состоит из двух циклов, а граница грани с номером 2 кроме цикла длины 5 включает еще дерево из трех ребер.
Рис. 3.7.
Множества ребер, образующие границы граней, могут быть разными для разных плоских укладок одного и того же графа. На рис. 3.8 показаны две плоские укладки одного графа. В левой укладке есть две грани, границы которых являются простыми циклами длины 5. В правой укладке таких граней нет, но есть грани, ограниченные циклами длины 4 и 6. Однако число граней, как показывает следующая теорема, не зависит от укладки, т.е. является инвариантом планарного графа.
Рис. 3.8.
Теорема 6 (формула Эйлера). Количество граней в любой плоской укладке планарного графа, имеющего вершин, ребер и компонент связности, равно 
.
Доказательство.
Докажем сначала утверждение теоремы при . Рассмотрим связный плоский граф . Если в нем нет циклов, то имеется единственная грань, а 
, и формула верна. Если же есть хотя бы один цикл, то возьмем какое-нибудь ребро , принадлежащее простому циклу . Это ребро принадлежит границе двух граней, одна из которых целиком лежит внутри цикла , другая - снаружи. Если удалить ребро из графа, эти две грани сольются в одну. Граф , полученный из графа удалением ребра , очевидно, будет плоским и связным, в нем на одно ребро и на одну грань меньше, чем в , а число вершин осталось прежним. Если в еще есть циклы, то, удалив еще одно цикловое ребро, получим граф . Будем продолжать удаление цикловых ребер до тех пор, пока не получится связный плоский граф 
без циклов, т.е. дерево. У него ребро и единственная грань. Значит, всего было удалено 
ребер, а так как при удалении каждого ребра число граней уменьшалось на единицу, то в исходном графе было 
грани. Таким образом, формула верна для любого связного плоского графа. Если граф несвязен, то в компоненте связности, имеющей вершин и 
ребер, как доказано выше, будет 
внутренняя грань. Суммируя по всем компонентам и прибавляя 1 для учета внешней грани, убеждаемся в справедливости формулы в общем случае.
Следствие 1. Если в планарном графе вершин, 
, и ребер, то 
.
Доказательство.
Если в графе нет циклов, то 
и неравенство выполняется при . Рассмотрим плоский граф с 
гранями, в котором имеются циклы. Занумеруем грани числами от 
до и обозначим через 
количество ребер, принадлежащих грани с номером . Так как граница каждой грани содержит цикл, то 
для каждого , следовательно, 
. С другой стороны, каждое ребро принадлежит границе не более чем двух граней, поэтому 
. Из этих двух неравенств следует, что 
. Применяя формулу Эйлера, получаем 
.
Следствие 1 дает необходимое условие планарности, которое в некоторых случаях позволяет установить, что граф не является планарным. Рассмотрим, например, полный граф 
. У него 
, 
, и мы видим, что неравенство из следствия 1 не выполняется. Значит, этот граф непланарен. В то же время существуют графы, не являющиеся планарными, для которых неравенство следствия 1 выполняется. Пример - полный двудольный граф 
. У него 6 вершин и 9 ребер. Неравенство выполняется, но мы сейчас установим, что он непланарен. Заметим, что в этом графе нет циклов длины 3 (так как он двудольный, в нем вообще нет циклов нечетной длины). Поэтому граница каждой грани содержит не менее четырех ребер. Повторяя рассуждения из доказательства следствия 1, но используя неравенство 
вместо , получаем следующий результат:
Следствие 2. Если в планарном графе вершин, , ребер и нет циклов длины 
, то 
.
Для графа неравенство следствия 2 не выполняется, и это доказывает, что он непланарен.
Известно несколько критериев планарности, сформулируем без доказательства два из них. Два графа называют гомеоморфными,если из них с помощью подразбиения ребер можно получить изоморфные графы. На рис. 3.9 изображены гомеоморфные графы.
Рис. 3.9.
Сформулируем без доказательства два критерия планарности.
Теорема 7 (критерий Понтрягина-Куратовского). Граф планарен тогда и только тогда, когда у него нет подграфов, гомеоморфных или .
Граф называется стягиваемым к графу 
, если можно получить из последовательностью операций стягивания ребер.
Теорема 8 (критерий Вагнера). Граф планарен тогда и только тогда, когда у него нет подграфов, стягиваемых к или .
Отметим, что, несмотря на внешнее сходство двух теорем, фигурирующие в них понятия гомеоморфизма и стягиваемости существенно различаются. На рис. 3.10 изображен граф, который называют графом Петерсена. В нем нет подграфа, гомеоморфного , так как в графе каждая вершина имеет степень 
, а в графе Петерсена степень каждой вершины равна . При удалении вершин и ребер и подразбиении ребер степени вершин не увеличиваются. В то же время легко видеть, что граф Петерсена можно превратить в стягиванием пяти ребер.
Поиск в глубину - вероятно, наиболее важная ввиду многочисленности приложений стратегия обхода графа. Идея этого метода - идти вперед в неисследованную область, пока это возможно, если же вокруг все исследовано, отступить на шаг назад и искать новые возможности для продвижения вперед. Метод поиска в глубину известен под разными названиями, например, "бэктрекинг", "поиск с возвращением".
Понятия новой, открытой, закрытой и активной вершин для поиска в глубину имеют такой же смысл, как и для поиска в ширину. Отметим, что всегда имеется не более чем одна активная вершина.
Обход начинается с посещения заданной стартовой вершины , которая становится активной и единственной открытой вершиной. Затем выбирается инцидентное вершине ребро 
и посещается вершина . Она становится открытой и активной. Заметим, что при поиске в ширину вершина оставалась активной до тех пор, пока не были исследованы все инцидентные ей ребра. В дальнейшем, как и при поиске в ширину, каждый очередной шаг начинается с выбора активной вершины из множества открытых вершин. Если все ребра, инцидентные активной вершине , уже исследованы, она превращается в закрытую. В противном случае выбирается одно из неисследованных ребер 
, это ребро исследуется. Если вершина новая, то она посещается и превращается в открытую.
Главное отличие от поиска в ширину состоит в том, что при поиске в глубину в качестве активной выбирается та из открытых вершин, которая была посещена последней. Для реализации такого правила выбора наиболее удобной структурой хранения множества открытых вершин является стек: открываемые вершины складываются в стек в том порядке, в каком они открываются, а в качестве активной выбирается последняя вершина. Схематически это показано на рис. 5.1.
Рис. 5.1.
Обозначим стек для открытых вершин через 
, остальные обозначения сохраняют тот же смысл, что и в предыдущем разделе. Через 
обозначается верхний элемент стека (т.е. последний элемент, добавленный к стеку). Тогда процедура обхода одной компоненты связности методом поиска в глубину со стартовой вершиной может быть записана следующим образом (DFS - Depth First Search).
Procedure DFS(a)
посетить вершину
while 
do
if имеется неисследованное ребро
then исследовать ребро
if вершина новая
then посетить вершину
else удалить из
Еще раз обратим внимание на основное отличие этой процедуры от аналогичной процедуры поиска в ширину. При поиске в ширину вершина, став активной, остается ею, пока не будет полностью исследована ее окрестность, после чего она становится закрытой. При поиске в глубину, если в окрестности активной вершины обнаруживается новая вершина , то помещается в стек и при следующем повторении цикла while станет активной. При этом остается в стеке и через какое-то время снова станет активной. Иначе говоря, ребра, инцидентные вершине , будут исследованы не подряд, а с перерывами.
Алгоритм обхода всего графа - тот же, что и в случае поиска в ширину только нужно очередь заменить стеком, а процедуру BFS - процедурой DFS.
Свойства 1 и 2 поиска в ширину, отмеченные в предыдущем разделе, сохраняются и для поиска в глубину. Остается верной и оценка трудоемкости 
, но ее доказательство требует несколько иных рассуждений, так как каждая вершина теперь может становиться активной несколько раз. Однако каждое ребро рассматривается только два раза (один раз для каждой инцидентной ему вершины), поэтому в операторе if в строке 5 ветвь then (строки 6-9) повторяется 
раз. В этом же операторе ветвь else (строка 10) повторяется 
раз, так как каждая вершина может быть удалена из стека только один раз. В целом получается , причем остаются справедливыми сделанные в предыдущей лекции замечания об условиях, при которых имеет место эта оценка.
Работа всякого алгоритма обхода состоит в последовательном посещении вершин и исследовании ребер. Какие именно действия выполняются при посещении вершины и исследовании ребра - зависит от конкретной задачи, для решения которой производится обход. В любом случае, однако, факт посещения вершины запоминается, так что с момента посещения и до конца работы алгоритма она считается посещенной. Вершину, которая еще не посещена, будем называть новой. В результате посещения вершина становится открытой и остается такой, пока не будут исследованы все инцидентные ей ребра. После этого она превращается в закрытую.
Идея поиска в ширину состоит в том, чтобы посещать вершины в порядке их удаленности от некоторой заранее выбранной или указанной стартовой вершины . Иначе говоря, сначала посещается сама вершина , затем все вершины, смежные с , то есть находящиеся от нее на расстоянии , затем вершины, находящиеся от на расстоянии 
, и т.д.
Рассмотрим алгоритм поиска в ширину с заданной стартовой вершиной . Вначале все вершины помечаются как новые. Первой посещается вершина , она становится единственной открытой вершиной. В дальнейшем каждый очередной шаг начинается с выбора некоторой открытой вершины . Эта вершина становится активной. Далее исследуются ребра, инцидентные активной вершине. Если такое ребро соединяет вершину с новой вершиной , то вершина посещается и превращается в открытую. Когда все ребра, инцидентные активной вершине, исследованы, она перестает быть активной и становится закрытой. После этого выбирается новая активная вершина, и описанные действия повторяются. Процесс заканчивается, когда множество открытых вершин становится пустым.
Основная особенность поиска в ширину, отличающая его от других способов обхода графов, состоит в том, что в качестве активной вершины выбирается та из открытых, которая была посещена раньше других. Именно этим обеспечивается главное свойство поиска в ширину: чем ближе вершина к старту, тем раньше она будет посещена. Для реализации такого правила выбора активной вершины удобно использовать для хранения множества открытых вершин очередь - когда новая вершина становится открытой, она добавляется в конец очереди, а активная выбирается в ее начале. Схематически процесс изменения статуса вершин изображен на рис. 4.1. Черным кружком обозначена активная вершина.
Рис. 4.1.
Опишем процедуру поиска в ширину (BFS - от английского названия этого алгоритма - Breadth First Search) из заданной стартовой вершины . В этом описании 
обозначает множество всех вершин, смежных с вершиной , 
- очередь открытых вершин. Предполагается, что при посещении вершины она помечается как посещенная и эта пометка означает, что вершина уже не является новой.
Procedure BFS(a)
посетить вершину
while 
do
for 
do
исследовать ребро
if вершина новая
then посетить вершину
Отметим некоторые свойства процедуры BFS.
Процедура BFS заканчивает работу после конечного числа шагов.
Действительно, при каждом повторении цикла while из очереди удаляется одна вершина. Вершина добавляется к очереди только тогда, когда она посещается. Каждая вершина может быть посещена не более одного раза, так как посещаются только новые вершины, а в результате посещения вершина перестает быть новой. Таким образом, число повторений цикла while не превосходит числа вершин.
В результате выполнения процедуры BFS будут посещены все вершины из компоненты связности, содержащей вершину a, и только они.
Очевидно, что вершина может быть посещена только в том случае, когда существует путь, соединяющий ее с вершиной (так как посещается всегда вершина, смежная с уже посещенной). То, что каждая такая вершина будет посещена, легко доказывается индукцией по расстоянию от данной вершины до вершины .
Время работы процедуры BFS есть , где - число ребер в компоненте связности, содержащей вершину .
Из предыдущих рассуждений видно, что каждая вершина из этой компоненты становится активной точно один раз. Внутренний цикл for для активной вершины выполняется 
раз. Следовательно, общее число повторений внутреннего цикла будет равно 
.
Итак, процедура BFS() производит обход компоненты связности, содержащей вершину . Чтобы перейти к другой компоненте, достаточно выбрать какую-нибудь новую вершину (если такие вершины еще имеются), в качестве стартовой. Пусть - множество вершин графа. Следующий алгоритм осуществляет полный обход графа методом поиска в ширину.
Алгоритм 1. Поиск в ширину.
пометить все вершины как новые
создать пустую очередь
for 
do if новая then BFS()
Учитывая, что цикл for в строке повторяется раз, где - число вершин графа, получаем общую оценку трудоемкости . Необходимо отметить, что эта оценка справедлива в предположении, что время, требуемое для просмотра окрестности вершины, пропорционально степени этой вершины. Это имеет место, например, если граф задан списками смежности. Если же граф задан матрицей смежности, то для просмотра окрестности любой вершины будет затрачиваться время, пропорциональное . В этом случае общее время работы алгоритма будет оцениваться как 
. Наибольшее значение величины при данном равно 
, т.е. имеет порядок 
. Таким образом, трудоемкость алгоритма поиска в ширину при задании графа списками смежности не выше, чем при задании матрицей смежности. В целом же первый способ задания предпочтительнее, так как дает выигрыш для графов с небольшим числом ребер.
В качестве простейшего примера применения поиска в ширину для графа рассмотрим задачу выявления компонент связности. Допустим, мы хотим получить ответ в виде таблицы, в которой для каждой вершины указан номер 
компоненты, которой принадлежит эта вершина. Компоненты будут получать номера в процессе обхода. Для решения этой задачи достаточно ввести переменную со значением, равным текущему номеру компоненты, и каждый раз при посещении новой вершины полагать 
. Значение первоначально устанавливается равным и модифицируется при каждом вызове процедуры BFS.
. ПРИМЕНЕНИЕ ТЕОРИИ ГРАФОВ В ТЕОРИИ ИНФОРМАЦИИ.
Графы и информация
Двоичные деревья играют весьма важную роль в теории информации. Предположим, что определенное число сообщений требуется закодировать в виде конечных последовательностей различной длины, состоящих из нулей и единиц. Если вероятности кодовых слов заданы, то наилучшим считается код, в котором средняя длина слов минимальна по сравнению с прочими распределениями вероятности. Задачу о построении такого оптимального кода позволяет решить алгоритм Хаффмана.
Двоичные кодовые деревья допускают интерпретацию в рамках теории поиска. Каждой вершине при этом сопоставляется вопрос, ответить на который можно либо "да", либо "нет". Утвердительному и отрицательному ответу соответствуют два ребра, выходящие из вершины. "Опрос" завершается, когда удается установить то, что требовалось.
Таким образом, если кому-то понадобится взять интервью у различных людей, и ответ на очередной вопрос будет зависеть от заранее неизвестного ответа на предыдущий вопрос, то план такого интервью можно представить в виде двоичного дерева.
refdb.ru
