- •Раздел III. Теория грАфов
- •Тема 1. Вводные понятия
- •1.1. Основные понятия теории графов
- •1.2. Машинное представление графа
- •Тема 2. Степени, маршруты, связность
- •2.1. Степени вершин графов
- •2.2. Маршруты и цепи
- •2.3. Связность
- •Тема 3. Алгоритмы обхода вершин в графах общего вида
- •3.1. Вычислительная сложность алгоритма
- •3.2. Алгоритм поиска в глубину
- •If nowy[u] then depth_r(u) ;
- •Var nowy : array [1..N] of boolean;
- •If nowy[V] then depth_r(V)
- •3.3. Алгоритм поиска в ширину(очередь – queue)
- •If nowy[u] then
- •3.4. Модификации алгоритмов
- •3.5. Путь минимального веса в графе. Алгоритм Флойда
- •Тема 4. Деревья
- •4.1. Эквивалентные определения дерева
- •4.2. Остов
- •Тема 5.Специальные вершинные подмножества графа
- •5.1. Определения вершинных подмножеств
- •5.2. Теоремы о вершинных подмножествах
Раздел III. Теория грАфов
Литература
1. Новиков, Ф. А. Дискретная математика для программистов. – Санкт-Петербург: Питер, 2004. – 304 с.
2. Липский, В. Комбинаторика для программистов. М.: Мир, 1988,- 213 с.
3. Кристофидес, Р. Теория графов. Алгоритмический подход [Текст] / Р. Кристофидес / Пер. с англ. М.: Мир, 1978. 432 с.
4. Алгоритмы поиска в глубину и ширину на графах: Методические указания к практическим занятиям по курсу "Дискретная математика" /Воронеж. гос. технол. акад. : Сост. Ю. В. Бугаев, И. Ю. Шурупова, О. Ю. Никифорова. Воронеж, 2001. 23 с.
Тема 1. Вводные понятия
Как и большинство разделов дискретной математики, теория графов возникла при решении различных головоломок. Известна точная дата ее появления – 1736 г. Это год, в котором великий математик Леонард Эйлер опубликовал статью с решением задачи о Кенигсбергских мостах. В 18 в. Кенигсберг был расположен на обоих берегах и двух островах реки Пречель. Острова были связаны между собой и с берегами семью мостами:
Правый берег
Течение реки
М 3
М 2
М 1
М 4
М 7
М 6
М 5
Левый берег
Существовала популярная задача: можно ли, выйдя из дома, вернуться обратно, пройдя по каждому мосту ровно один раз?
Размышляя над этой задачей, Эйлер для удобства рассуждений изобразил ее в виде простой геометрической фигуры – из точек, соединенных линиями. Каждый берег и остров он изобразил точками, а мосты – линиями, их соединяющими. Получилась фигура, которая сейчас называется графом:
V1 –
прав. берег
V3
–
остров 1
V4
– остров
2
V2 –
лев. берег
Задачу о мостах Эйлер сформулировал так: можно ли, начав движение из любой вершины, и двигаясь вдоль линий, пройти по каждой линии точно по одному разу и вернуться в исходную вершину?
В современной постановке задача звучит так: существует ли в данном мультиграфе простой цикл, содержащий все ребра?
В своей работе Эйлер
1) доказал, что эта задача не имеет решения;
2) сформулировал и доказал необходимое и достаточное условие существования в произвольном графе такого (Эйлерова) цикла.
Потом о теории графов забыли, чтобы вспомнить в 19 веке, когда возникли задачи исследования электрических цепей, моделей кристаллов и структур молекул. Новый всплеск интереса к теории графов приходится на средину 20 века. Выяснилось, что к задачам о графах сводится множество производственных и научных задач – прокладка трасс, проектирование систем управления и интегральных схем, построение логических схем в экономике, химии, биологии. В терминах теории графов формулируются основные алгоритмы, связанные с перебором вариантов. Без преувеличения можно сказать, что теория графов – язык дискретной математики.
1.1. Основные понятия теории графов
Изображение графа в виде точек и линий – это лишь наиболее наглядный способ их представления. Формально граф определяется так: граф – это пара объектов G = (V, E), где V – некоторое конечное множество, Е – отношение на V: E VV. V – множество вершин, E – множество ребер.
Ребро принято обозначать либо как элемент Е: e1, …, em, ej E, либо указанием его начальной и конечной вершины (vi, vj). Второе обозначение не всегда однозначно, например, в задаче о мостах обозначению (v1, v3) соответствуют два различных ребра.
Def. Графом без кратных ребер называется граф, в котором для любых i, j существует единственное ребро ek = (vi, vj). Граф с кратными ребрами называется еще мультиграфом.
Def. Пусть u, v – вершины, е = (u, v) – соединяющее их ребро. Тогда вершина u и ребро e инцидентны друг другу (также как и v и е). Два ребра, инцидентные одной вершине называются смежными. Две вершины, инцидентные одному ребру также называются смежными.
Вершины, инцидентные одному ребру, могут быть равноправными, т.е. записи (u, v) и (v, u) эквивалентны, а могут быть неравноправными, т.е. важен порядок записи. Направленные ребра называются дугами, а содержащий их граф – ориентированным (орграфом) Направленные ребра на рисунке снабжаются стрелками – от начала к концу. Граф, в котором все ребра не направлены, называется неориентированным. Ребро вида (v, v) называется петлей.
Def. Граф называется полным, если любые его две вершины смежны, E = V V. 0-граф – граф без ребер. Изолированная вершина – не смежная ни с одной другой вершиной.
Def. Дополнение графа , где= (VV) \ E.
Пример 1.1.
G
Свойства графов легко связать со свойствами соответствующих бинарных отношений, т.к. R и E означают одно и то же. Например:
R – симметрично G – неориентированный;
R – асимметрично G – ориентированный, без петель;
R – антисимметрично G – ориентированный, с неориентированными петлями;
R – рефлексивно G имеет петли;
отношению R–1 соответствует граф с обратной ориентацией дуг;
соответствует и т.д.
Изоморфизм. При изображении графа в виде точек с линиями такие понятия, как длина или кривизна линий не важны. Главное – изобразить, какие именно пара вершин соединяет данное ребро. Например, на рис. Графы а) и б) одинаковы, а а) и в) совпадают с точностью до нумерации вершин и ребер.
V3 V2 V3
E3
E2 E3 E2 E1
E2
E1
V2 V1 E1 E3
V1 V3 V2 V1
а)
б)
в)
Такие графы называются изоморфными. Более строго:
Def. Пусть G = (V, E), H = (U, F) – графы. Пусть f : V U – взаимно-однозначное отображение. Если для любых v, w V их образы f(v) и f(w) смежны тогда и только тогда, когда смежны v и w, то f называется изоморфизмом G на H, а сами графы – изоморфными (обозначается G H). Если f – тождественное отображение, то G = H.
Пример 1.2. G H I, а J и K не изоморфны.
3 2 1
5 1 1 5
4 2 2 6
6 5
4
3 4 3 6 I
G H
J K