ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ

––––––––––––––

ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

“МОСКОВСКАЯ ГОСУДАРСТВЕННАЯ АКАДЕМИЯ

ПРИБОРОСТРОЕНИЯ И ИНФОРМАТИКИ”

––––––––––––––––––––––

Кафедра “Персональные компьютеры и сети”

Федоров В.Н.

ВВЕДЕНИЕ В ТЕОРИЮ ГРАФОВ

Учебное пособие

(конспект лекций)

Москва

2005

УДК: 519.21(075.8)

ББК 32.973.3

Введение в теорию графов / В.Н. Федоров – М.: МГАПИ, 2005. – 120 с.

Рекомендовано Ученым Советом МГАПИ в качестве учебного пособия для специальности 2201.

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

Предназначено для студентов, обучающихся по направлению “Информатика и вычислительная техника”. Для специальности 2201 учебное пособие предназначено для использования в курсе “Дискретная математика”.

___________________

Печатается по решению Редакционно–издательского совета Московской государственной академии приборостроения и информатики.

Научный редактор: д.т.н., проф. Михайлов Б.М.

Рецензенты: к.т.н., проф. Рощин А.В.,

к.т.н., проф. Степанова Т.А.

Работа рассмотрена и одобрена на заседании кафедры ИТ4 “Персональные компьютеры и сети” 23 декабря 2004г., протокол № 5.

 Федоров, 2005

Содержание

Введение 6

1. Основные определения 7

1.1. Вершины, ребра (дуги), графы 7

1.2. Подграфы и части графа 11

1.3. Гомоморфизм и изоморфизм графов 11

1.4. Взвешенные графы 12

1.5. Степени вершин 12

1.6. Связность и достижимость 16

1.7. Метрические характеристики графа 19

1.8. Обхват и окружение графа 22

1.9. Граф – дерево 22

1.10. Обходы графа 23

1.11. гамильтоновы и эйлеровы графы 24

1.12. Контрольные вопросы 26

2. Представление графов в ЭВМ 27

2.1. Матричная форма представления графов 27

2.1.1. Матрица смежности 27

2.1.2. Матрица инцидентности 28

2.2. Векторная форма представления графов 29

2.2.1. Задание графа массивом преемников вершин 29

2.2.2. Задание графа массивом предшественников вершин 30

2.3. Контрольные вопросы 30

3. Операции над графами 30

3.1. Дополнение графа 30

3.2. Объединение 31

3.3. Пересечение 31

3.4. Кольцевая сумма 31

3.5. Соединение 32

3.6. Произведение 32

3.7. Композиция 32

3.8. Разность 33

3.9. Удаление вершины 33

3.10. Удаление ребра 33

3.11. Добавление вершины 33

3.12. Добавление ребра 34

3.13. Стягивание подграфа A в вершину 34

3.14. Замыкание или отождествление вершин 34

3.15. Подразбиение ребра 34

3.16. Контрольные вопросы 34

4. Маршруты и циклы 35

4.1. Есть ли в графе маршруты длины k? 35

4.2. Сколько маршрутов длины k имеется в графе? 36

4.3. Какие маршруты длины k имеются в графе? 36

4.4. Контрольные вопросы 38

5. Кратчайший маршрут во взвешенном связном графе 39

5.1. Волновой алгоритм 39

5.2. Контрольные вопросы 42

6. Эйлеровы графы 42

6.1. Алгоритм построения эйлерова цикла 42

6.2. Алгоритм построения эйлеровой цепи 43

6.3. Модифицированный алгоритм построения эйлерова цикла 43

6.4. Покрытие графа непересекающимися по ребрам цепями 44

6.5. Контрольные вопросы 47

7. Внешне устойчивые множества вершин и вершинная база графа 48

7.1. Внешне устойчивые множества вершин графа 48

7.2. Алгоритм определения внешне устойчивых множеств вершин 49

7.3. Вершинная база 50

7.4. Контрольные вопросы 51

8. Внутренняя устойчивость и раскраска графа 52

8.1. Внутренне устойчивые множества вершин графа 52

8.2. Алгоритм определения внутренне устойчивых множеств вершин 52

8.3. Раскраска вершин графа 55

8.4. Алгоритм последовательной раскраски вершин графа 57

8.5. Приближенный алгоритм поиска МНМВ 58

8.6. Реберная раскраска графа 59

8.7. Контрольные вопросы 60

9. Связность графов 61

9.1. Определение компонент сильной связности орграфа 61

9.2. Определение компонент связности 65

9.3. Контрольные вопросы 69

10. Фундаментальные циклы и разрезы графа 69

10.1. Остов графа 69

10.2. Нахождение остова минимальной длины 70

10.3. Фундаментальные циклы 70

10.4. Фундаментальные разрезы 72

10.5. Контрольные вопросы 74

11. Планарные графы 74

11.1. Условия планарности 75

11.2. Грани плоского графа 77

11.3. Алгоритм построения плоского изображения графа 77

11.4. Контрольные вопросы 81

12. Двудольные графы 81

12.1. Минимальное покрытие двудольного графа 82

12.1.1. Алгоритм с использованием матрицы инцидентности 83

12.1.2. Алгоритм с подсчетом единиц в строках и столбцах матрицы смежности графа 84

12.2. Паросочетание двудольного графа 87

12.3. Контрольные вопросы 90

13. Сети 90

13.1. Максимальный поток в минимальном разрезе 92

13.2. Алгоритм нахождения максимального потока 95

13.3. Результаты исследования сети 100

13.4. Контрольные вопросы 101

14. Примерные темы заданий 101

Список литературы 103

Приложение:Термины и определения теории графов 104

1. Элементы графов 104

2. Структуры графов 107

3. Части графов 114

Введение

Теория графов – это математический язык для формализации понятий, связанных с анализом и синтезом структур объектов, систем и процессов.

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

Возникновение теории графов принято датировать 1936 годом, когда появилась книга Денеша Кёнига «Теория конечных и бесконечных графов». Однако отдельные задачи по теории графов возникали и решались много раньше, например, Леонард Эйлер (1707 – 1782) в 1736 году сформулировал задачу о Кенигсбергских мостах:

М ожно ли обойти все участки суши и вернуться к исходной точке, пройдя один раз по каждому мосту? (На рисунке A и D – два острова, C и B – берега реки, ребра – семь мостов.)

Занимаясь этой задачей, Эйлер доказал теорему:

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

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

1. Основные определения

1.1. Вершины, ребра (дуги), графы

Совокупность множества вершин V и множества связей Е между ними называется графом и обозначается G(V, E).

На рис. 1.1 показан пример графа G(4,6), где обозначено:

V = {x₁, x₂, x₃, x₄} – множество вершин,

n = |V| = 4 – число вершин графа G(4,6),

E = {e₁, e₂, e₃, e₄, e₅, e₆} – множество ребер,

m = |E| = 6 – число ребер графа G(4,6).

E – это отображение V в V (E: V V).

Р
исунок 1.1

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

В качестве другого примера на рис. 1.2 показано семейство графов на четырех вершинах.

Обратите внимание на общепринятые обозначения некоторых графов:

N₄ – нуль граф;

P₄ – цепь;

C₄ – цикл;

W₄ – звезда;

K₄ – полный граф, в нем каждая вершина имеет связь со всеми другими вершинами.

В общем случае эти типы графов обозначаются так:

N_n, P_n, C_n, W_n, K_n.

Обратим внимание на граф C₄. Этот граф можно представить и так, как показано на рис. 1.3. Такой граф обозначается K_2,2 и называется полным двудольным графом.

В двудольном графе множество вершин V разбито на два подмножества X и Y таких, что между вершинами внутри каждого из них нет связей. Число ребер в полном двудольном графе

m = n₁n₂, где n₁ =|X|, n₂ = |Y|, n = n₁ + n₂.

Р
исунок 1.2

Р
исунок 1.3

Если связь имеет направление, то она называется дугой, в противном случае – ребром. (Графы с дугами и ребрами показаны на рис. 1.4.)

Р
исунок 1.4

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

e = (v₁,v₂) – дуга e, (e = [v₁,v2] – ребро e).

Граф, у которого все связи являются ребрами, называется неориентированным графом или сокращенно неорграфом (рис. 1.4, а).

Граф с дугами называется ориентированным графом или орграфом (рис. 1.4, б).

Р
ебро (дуга), оба конца которого связаны с одной и той же вершиной, называется петлей (рис. 1.5).

Рисунок 1.5

Если у графа существуют кратные ребра, т.е. несколько ребер, соединяющих одну и туже пару вершин, то такой граф называется мультиграфом. Если все ребра мультиграфа имеют одинаковую кратность k, то такой граф называется k–кратным или просто k–графом. На рис. 1.6 показан мультиграф G(6,20):

а, в – две вершины графа; e₁, e₂, e₃, e₄ – кратные ребра, соединяющие вершины а и в.

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

Рисунок 1.6