Применение теории графов в информатике

ВСЕРОССИЙСКИЙ ЗАОЧНЫЙ  ФИНАНСОВО-ЭКОНОМИЧЕСКИЙ                                                                                                      ИНСТИТУТ

 

КАФЕДРА АВТОМАТИЗИРОВАННОЙ ОБРАБОТКИ

ЭКОНОМИЧЕСКОЙ ИНФОРМАЦИИ

 

 

 

 

 

КУРСОВАЯ РАБОТА

 

по дисциплине «Информатика»

на тему «Применение теории графов в информатике»

 

 

 

 

 

 

 

                                                    Исполнитель:  Цейтлин К.А

Специальность: Финансы и Кредит

                               Группа  121100

                                                            № зачётной книжки 10ффд11596

                                                  Руководитель: Сысоев А.И.

 

 

                                Липецк  2010

                                               Содержание

Введение…………………………………………………………………………3

1. Теоретическая часть……………………………………………........……....4
1. История возникновения теории графов…………………………….….4
2. Основные понятия теории графов……………………………………...6
3. Основные теоремы теории графов……………………………………..9
4. Способы предоставления графов в компьютере…………………......13
1. Требования к предоставлению графов………………….......…..13
2. Матрица смежности……………………………………………...13
3. Матрица инциденций…………………………………………….14
4. Списки смежности………………………………………………..14
5. Массив дуг……………………………………………………......14

1.5. Обзор задач теории  графов……………………………………………15

1.6. Программа определения  кратчайшего пути в графах…………….…17

1.6.1. Язык программирования  Delphi……………………………....…17

1.6.2. Программа  «Определения кратчайшего пути  в графе»……......19

Заключение……………………………………………………………………..24

2. Практическая часть………………………………………………………....27
1. Общая характеристика задачи………………………………………....
2. Описание алгоритма решения задачи………………………………....

 

 

 

 

 

 

 

 

 

Введение

Начало теории графов как математической дисциплины было положено Эйлером в его знаменитом рассуждении о Кенигсбергских мостах. Однако эта статья Эйлера 1736 года была единственной в течение почти ста лет. Интерес к проблемам теории графов возродился около середины прошлого столетия и был сосредоточен главным образом в Англии. Имелось много причин для такого оживления изучения графов. Естественные науки оказали свое влияние на это благодаря исследованиям электрических цепей, моделей кристаллов и структур молекул. Развитие формальной логики привело к изучению бинарных отношений в форме графов. Большое число популярных головоломок подавалось формулировкам непосредственно в терминах графов, и это приводило к пониманию, что многие задачи такого рода содержат некоторое математическое ядро, важность которого  выходит за рамки конкретного вопроса. Наиболее знаменитая среди этих задач–проблема четырех красок, впервые поставленная перед математиками Де Морганом около 1850 года. Никакая проблема не вызывала столь многочисленных и остроумных работ в области теории графов.

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

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

1. Теоретическая часть

1.1 История возникновения теории  графов

Родоначальником теории графов принято считать математика Леонарда Эйлера (1707-1783) [3, стр. 36]. Однако теория графов многократно переоткрывалась разными авторами при решении различных прикладных задач.

1. Задача о Кенигсбергских мостах. На рис. 1 представлен схематический план центральной части города Кенигсберг (ныне Калининград), включающий два берега реки Перголя, два острова в ней и семь соединяющих мостов. Задача состоит в том, чтобы обойти все четыре части суши, пройдя по каждому мосту один раз, и вернуться в исходную точку. Эта задача была решена (показано, что решение не существует) Эйлером в 1736 году.

Рис. 1. Схематическое изображение Кенигсбергских мостов

2. Задача о трех домах и трех колодцах. Имеется три дома и три колодца, каким-то образом расположенные на плоскости. Провести от каждого дома к каждому колодцу тропинку так, чтобы тропинки не пересекались (рис. 2). Эта задача была решена (показано, что решение не существует) Куратовским в 1930 году [2, стр. 51].

Рис. 2 Схематичное изображение трех домов и трех колодцев

3. Задача о четырех красках. Разбиение на плоскости на непересекающиеся области называется картой. Области на карте называются соседними, если они имеют общую границу. Задача состоит в раскрашивании карты таким образом, чтобы никакие две соседние области не были закрашены одним цветом (рис. 3). С конца позапрошлого века известна гипотеза, что для этого достаточно четырех красок. В 1976 году Аппель и Хейкен опубликовали решение задачи о четырех красках, которое базировалось на переборе вариантов с помощью компьютера. Решение этой задачи «программным путем» явилось прецедентом, породившим бурную дискуссию, которая отнюдь не закончена. Суть опубликованного решения состоит в том, чтобы перебрать большое, но конечное число (около 2000) типов потенциальных контрпримеров к теореме о четырех красках и показать, что ни один случай контрпримером не является. Этот перебор был выполнен программой примерно за тысячу часов работы суперкомпьютера. Проверить «вручную» полученное решение невозможно – объем перебора выходит далеко за рамки человеческих возможностей. Многие математики ставят вопрос: можно ли считать такое «программное доказательство» действительным доказательством? Ведь в программе могут быть ошибки… Методы формального доказательства правильности программ не применимы к программам такой сложности, как обсуждаемая. Тестирование не может гарантировать отсутствие ошибок и в данном случае вообще невозможно. Таким образом, остается уповать на программистскую квалификацию авторов и верить, что они сделали все правильно.

 

 

 

 

Рис. 3.  Схематичное изображение задачи о четырех красках

1.2 Основные понятия теории графов

1. Графом G(V,E) называется совокупность двух множеств – непустого множества V(множества вершин) и множества E двухэлементных подмножеств множества V(E – множество ребер).
2. Ориентированным называется граф, в котором - множество упорядоченных пар вершин вида (x,y), где x называется началом, а y – концом дуги. Дугу (x, y) часто записывают как . Говорят также, что дуга ведет от вершины x к вершине y, а вершина y смежная с вершиной x.
3. Если элементом множества E может быть пара одинаковых (не различных) элементов V, то такой элемент множества E называется петлей, а граф называется графом с петлями (или псевдографом).
4. Если E является не множеством, а набором, содержащим несколько одинаковых элементов, то эти элементы называются кратными ребрами, а граф называется мультиграфом.
5. Если элементами множества E являются не обязательно двухэлементные, а любые подмножества множества V, то такие элементы множества E называются гипердугами, а граф называется гиперграфом.
6. Если задана функция F : V → M и/или F : E → M, то множество M называется множеством пометок, а граф называется помеченным (или нагруженным). В качестве множества пометок обычно используются буквы или целые числа. Если функция F инъективна, то есть разные вершины (ребра)имеют разные пометки, то граф называют нумерованным.
7. Подграфом называется граф G′(V′,E′), где и/или .
1. Если V′ = V, то G′ называется остовным подграфом G.
2. Если , то граф G′ называется собственным подграфом графа G.
3. Подграф G′(V′,E′) называется правильным подграфом графа G(V,E), если G′ содержит все возможные рёбра G.
8. Степень (валентность) вершины – это количество ребер, инцидентных этой вершине (количество смежных с ней вершин).
9. Маршрутом в графе называется чередующаяся последовательность вершин и ребер , в которой любые два соседних элемента инциденты.
1. Если , то маршрут замкнут, иначе открыт.
2. Если все ребра различны, то маршрут называется цепью.
3. Если все вершины (а значит, и ребра) различны, то маршрут называется простой цепью.
4. Замкнутая цепь называется циклом.
5. Замкнутая простая цепь называется простым циклом.
6. Граф без циклов называется ациклическим.
7. Для орграфов цепь называется путем, а цикл – контуром.

Рис. 4. Маршруты, цепи, циклы

Пример

В графе, диаграмма которого приведена на рис.4:

1. v1, v3, v1, v4 – маршрут, но не цепь;
2. v1, v3, v5, v2, v3, v4 – цепь, но не простая цепь;
3. v1, v4, v3, v2, v5 – простая цепь;
4. v1, v3, v5, v2, v3, v4, v1 – цикл, но не простой цикл;
5. v1, v3, v4, v1 – простой цикл.

 

10. Если граф имеет цикл (не обязательно простой), содержащий все ребра графа по одному разу, то такой цикл называется эйлеровым циклом.
11. Если граф имеет простой цикл, содержащий все вершины графа (по одному разу), то такой цикл называется гамильтоновым циклом.
12. Деревом называется связный граф без циклов.
13. Остовом называется дерево, содержащее все вершины графа.
14. Паросочетанием называется множество ребер, в котором никакие два не смежны.
15. Паросочетание называется максимальным, если никакое его надмножество не является независимым.
16. Две вершины в графе связаны, если существует соединяющая их простая цепь.
17. Граф, в котором все вершины связаны, называется связным.
18. Граф, состоящий только из изолированных вершин, называется вполне несвязным.
19. Длиной маршрута называется количество ребер в нем (с повторениями).
20. Расстоянием между вершинами u и v называется длина кратчайшей цепи , а сама кратчайшая цепь называется геодезической.
21. Диаметром графа G называется длина длиннейшей геодезической.
22. Эксцентриситетом вершины v в связном графе G(V,E) называется максимальное расстояние от   вершины v до других вершин графа G.
23. Радиусом графа G называется наименьший из эксцентриситетов вершин.
24. Вершина v называется центральной, если ее эксцентриситет совпадает с радиусом графа.
25. Множество центральных вершин называется центром графа.

 

Рис. 5 Эксцентриситеты вершин и центры графов (выделены)

 

1.3 Основные теоремы теории графов

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

Теорема 1. Удвоенная  сумма степеней вершин любого графа равна   числу его ребер. [1, стр. 66]

Доказательство. Пусть А1, А2, А3, ..., An — вершины данного графа, a p(A1), p(А2), ..., p(An) – степени этих вершин. Подсчитаем число ребер, сходящихся в каждой вершине, и просуммируем эти числа. Это равносильно нахождению суммы степеней всех вершин. При таком подсчете каждое ребро будет учтено дважды (оно ведь всегда соединяет две вершины).

Отсюда следует: p(A1)+p(А2)+ ... +p(An)=0,5N, или 2(p(A1)+p(А2)+ ... +p(An))=N , где N — число ребер.

Теорема 2. Число нечетных вершин любого графа четно.

Доказательство. Пусть a1, a2, a3, …, ak — это степени четных вершин графа, а b1, b2, b3, …, bm — степени нечетных вершин графа. Сумма a1+a2+a3+…+ak+b1+b2+b3+…+bm ровно в два раза превышает число ребер графа. Сумма a1+a2+a3+…+ak четная (как сумма четных чисел), тогда сумма b1+b2+b3+…+bm должна быть четной. Это возможно лишь в том случае, если m — четное, то есть четным является и число нечетных вершин графа. Что и требовалось доказать.

Следствие 1. Нечетное число знакомых в любой компании всегда четно.

Следствие 2. Число вершин многогранника, в которых сходится нечетное число  ребер,  четно.

Следствие 3. Число всех людей, когда-либо пожавших руку другим людям, нечетное число раз, является четным.

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

Доказательство. Если граф имеет n вершин, то каждая из них может иметь степень 0, 1, 2, ..., (n-1). Предположим, что в некотором графе все его вершины имеют различную степень, то есть, и покажем, что этого быть не может. Действительно, если р(А)=0, то это значит, что А — изолированная вершина, и поэтому в графе не найдется вершины Х со степенью р(Х)=n-1. В самом деле, эта вершина должна быть соединена с (n-1) вершиной, в том числе и с А, но ведь А оказалась изолированной. Следовательно, в графе, имеющем n вершин, не могут быть одновременно вершины степени 0 и (n-1). Это значит, что из n вершин найдутся две, имеющие одинаковые степени.

Теорема 4. Если в графе с n вершинами (n больше или равно 2) только одна пара имеет одинаковую степень, то в этом графе всегда найдется либо единственная изолированная вершина, либо единственная вершина, соединенная со всеми другими.

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

Теорема 5. Если у графа все простые циклы четной длины, то он не содержит ни одного цикла четной длины.

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

Теорема 6. Для того, чтобы граф был эйлеровым, необходимо и достаточно, чтобы он был связным и все его вершины имели четную степень.

Теорема 7. Для того чтобы на связном графе можно было бы проложить цепь АВ, содержащую все его ребра в точности по одному разу, необходимо и достаточно, чтобы А и В были единственными нечетными вершинами этого графа.