Характеристика теории графов

Размещено на http://www.allbest.ru/

МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ

НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ “ХАРКІВСЬКИЙ ПОЛІТЕХНІЧНИЙ ІНСТИТУТ”

Кафедра “Системного аналізу та управління”

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

Дисципліна: „Дискретна математика”

Тема: „Теорія графів. Опис графів. Алгоритм Прима-Краскла”

Виконавець: ст. гр.

ИФ-50в В.В.Плющінов

Керівник роботи: доц.,

канд. техн. наук М.Н.Шаталін

Харків 2005

Завдання

на науково-дослідну курсову роботу

Дисципліна: “Дискретна математика”

Тема: „Теорія графів”(Варіант №38)

Короткий зміст роботи:

а) теоретична частина

Розробка методики дослідження графу наведеного на малюнку:

Провести математичний опис графу; пронумерувати вершини графу; проаналізувати граф на наявність Эйлерова циклу або Эйлерова шляху; двома алгоритмами перевірити граф на наявність циклів; знайти остовне дерево; знайти положення поліцейської дільниці; розмістити на графі магазин; вирішити задачу Дейкстри.

б) програмно-розрахункова частина

Розробка програмного забезпечення, яке реалізує перевірку наявності ейлерова циклу на графі, вирішає задачі Дейкстра та Флойда-Уоршала, розфарбовує граф за жадібним алгоритмом.

Дата видачі завдання: 15.03.2006 Термін захисту: 21.05.2006

Керівник курсової роботи: / канд. техн. наук, доц. САіУ

М.Н.Шаталін/

Содержание

Введение

1. Граф

1.1 Математическое описание графа

1.1.1 Описание графа Gор множествами вершин V и дуг X

1.1.2 Описание графа Gор списками смежности

1.1.3 Описание графа Gор матрицей инцидентности

1.1.4 Матрица весов соответствующего неориентированного графа

1.1.5 Описание графа Gор матрицей смежности

1.1.6 Степени вершин неориентированного графа

1.2 Нумерация вершин графа G «поисков в глубину»

1.2.1 Нумерация вершин графа G «поиском в ширину»

1.3 Эйлеров путь и Эйлеров цикл на графе

1.3.1 Для определения Эйлерова путь требуется выписать степенную последовательность вершин графа G и указать в графе G Эйлеров путь

1.3.2 Эйлеров цикл

1.4 Проверка ориентированного графа на наличие циклов путем отбрасывания «истоков» и «стоков»

1.5 Поиск остовного (остевого) дерева алгоритмом Прима-Краскала

1.6 Определение дерева кратчайших путей по алгоритму Дейкстры

2. Постановка задачи на программирование

2.1 Интерфейс программы

Заключение

Список использованных источников

Введение

Теория графов - это часть науки топологии.

Граф есть упорядоченная пара (V,E), где V - непустое множество, называемое множеством вершин; E - неупорядоченное бинарное отношение на V , т.е. V&V. E называют множеством ребер. Говорят, что ребро, принадлежащее множеству E, инцидентно вершинам, которые оно соединяет. Таким образом, мы определим неориентированный граф. Он полностью определяется списком вершин и указанием, какие пары вершин имеют соединяющие их ребра (в случае нагруженного графа каждому ребру или дуге еще приписывается вес). Во многом базовые определения теории графов обязаны своему появлению Л.Эйлеру (1707-1782), решившему в 1736 г. широко известную «задачу о кенигсбергских мостах».

Ориентированный граф - упорядоченная пара (V,E), где V - множество вершин, а E - упорядоченное отношение на V (т.е. V&V). В этом случае E называют множеством дуг. Первая и вторая вершины дуги называются соответственно начальной и конечной.

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

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

1. Граф

1.1 Математическое описание графа

Исходный граф из задания представлен на рис1.1.

Рисунок 1.1 Исходный граф для расчетов

Gор(V,X)

1.1.1 Описание графа Gор множествами вершин V и дуг X

Нумерация вершин см. рис. 1.1.

V={0,1,2,3,4,5,6,7,8,9}

X={{0,1},{0,2},{0,3},{1,2},{1,4},{1,5},{1,6},{1,7},{2,3},{2,5},{3,8},{3,9},

{4,5},{4,6},{5,3},{5,6},{5,8},{6,9},{7,8},{7,9},{8,9}}

1.1.2 Описание графа Gор списками смежности

Г0={1,2,3}; Г1={0,2,4,5,6,7}; Г2={0,1,3,5}; Г3={0,2,5,8,9};

Г4={1,5,6}; Г5={1,2,3,4,6,8}; Г6={1,4,5,9}; Г7={1,8,9};

Г8={1,3,5,7,9}; Г9={3,6,7,8};

1.1.3 Описание графа Gор матрицей инцидентности

Данный граф может описан матрицей инцидентности вершина-ребро (нумерация вершин и ребер приведена для удобства, обычно она не пишется)

	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20
0	1	1	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
1	1	0	0	1	1	1	1	1	0	0	0	0	0	0	0	0	0	0	0	0	0
2	0	1	0	1	0	0	0	0	1	1	0	0	0	0	0	0	0	0	0	0	0
3	0	0	1	0	0	0	0	0	1	0	1	1	0	0	1	0	0	0	0	0	0
4	0	0	0	0	1	0	0	0	0	0	0	0	1	1	0	0	0	0	0	0	0
5	0	0	0	0	0	1	0	0	0	1	0	0	1	0	1	1	1	0	0	0	0
6	0	0	0	0	0	0	1	0	0	0	0	0	0	1	0	1	0	1	0	0	0
7	0	0	0	0	0	0	0	1	0	0	0	0	0	0	0	0	0	0	1	1	0
8	0	0	0	0	0	0	0	0	0	0	1	0	0	0	0	0	1	0	1	0	1
9	0	0	0	0	0	0	0	0	0	0	0	1	0	0	0	0	0	1	0	1	1

1.1.4 Матрица весов соответствующего неориентированного графа

Соответствующий неориентированный граф можно представить матрицей весов:

	0	1	2	3	4	5	6	7	8	9
0	?	8	3	5	?	?	?	?	?	?
1		?	1	?	2	2	4	5	?	?
2			?	2	?	5	?	?	?	?
3				?	?	1	?	?	1	6
4					?	4	2	?	?	?
5						?	2	?	1	?
6							?	?	?	2
7								?	1	1
8									?	6
9										?

Примечание. Показана верхняя половина матрицы, т.к. матрица весов неориентированного графа симметрична относительно главной диагонали.

1.1.5 Описание графа Gор матрицей смежности

	0	1	2	3	4	5	6	7	8	9
0	?	1	1	1	?	?	?	?	?	?
1	-1	?	1	?	1	1	1	1	?	?
2	-1	-1	?	1	?	1	?	?	?	?
3	-1	?	-1	?	?	-1	?	?	1	1
4	?	-1	?	?	?	1	1	?	?	?
5	?	-1	-1	1	-1	?	1	?	1	?
6	?	-1	?	?	-1	-1	?	?	?	1
7	?	-1	?	?	?	?	?	?	1	1
8	?	?	?	-1	?	-1	?	-1	?	1
9	?	?	?	-1	?	?	-1	-1	-1	?

1.1.6 Степени вершин неориентированного графа

Степени вершин рассматриваемого неориентированного графа приведены в табл.1.1

Таблица 1.1 Степенная последовательность вершин графа G

Вершины	0	1	2	3	4	5	6	7	8	9
Степени	3	6	4	5	3	6	4	3	4	4

Выбираем из таблицы наибольшую и наименьшую степени:

Dmax = 6; Dmin = 3.

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

1.2 Нумерация вершин графа G «поисков в глубину»

Текущая вершина	Стек дополнения	Состояние стека
0	1,2,3	01,2,3
3	8,9	0,1,2,38,9
9	пусто	0,1,2,3,8,9
8	Пусто	0,1,2,3,8,9
2	(3),5	0,1,2,3,8,95
5	(3),6,(8)	0,1,2,3,8,9,56
6	(9)	0,1,2,3,8,9,5,6
1	(2),4,(5)	0,1,2,3,8,9,5,64,7
7	(8),(9)	0,1,2,3,8,9,5,6,4,7
4	(5),(6)	0,1,2,3,8,9,5,6,4,7

Рассмотрим стек нумерации «поиском в глубину». Правило построения LIFO - Last In First Out. Использованы номера вершин исходного графа. Просмотренные вершины выделены жирным шрифтом, уже внесенные в стек вершины заключены в скобки.

Перенумерация:

Старые номера	0	3	9	8	2	5	6	1	7	4
Новые номера	0	1	2	3	4	5	6	7	8	9

Реализация нумерации представлена на рис.1.2. Исходная вершина - .

Рисунок 1.2 - Нумерация «поиском в глубину»

1.2.1 Нумерация вершин графа G «поиском в ширину»

Текущая вершина	Стек дополнения	Состояние стека
0	1,2,3	01,2,3
1	(2),4,5,6,7	0,1,2,34,5,6,7
2	(3),(5)	0,1,2,3,4,5,6,7
3	8,9	0,1,2,3,4,5,6,78,9
4	(5),(6)	0,1,2,3,4,5,6,7,8,9
5	(3),(6),(8)	0,1,2,3,4,5,6,7,8,9
6	(9)	0,1,2,3,4,5,6,7,8,9
7	(8),(9)	0,1,2,3,4,5,6,7,8,9
8	(9)	0,1,2,3,4,5,6,7,8,9
9	Пусто	0,1,2,3,4,5,6,7,8,9

Рассмотрим стек нумерации «поиском в глубину». Правило построения FIFO - First In First Out. Использованы номер а вершин исходного графа. Просмотренные вершины выделены жирным шрифтом, уже внесенные в стек вершины заключены в скобки.

Перенумерация в данном случае не нужна, поскольку граф уже пронумерован «поиском в ширину», рис.1.3. Исходная вершина - .

Рисунок 1.3 - Нумерация «поиском в ширину»

1.3 Эйлеров путь и Эйлеров цикл на графе

1.3.1 Для определения Эйлерова путь требуется выписать степенную последовательность вершин графа G и указать в графе G Эйлеров путь

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

Степенная последовательность вершин графа G:

(3,6,4,5,3,6,4,3,4,4)

Для существования Эйлерова пути допустимо только две вершины с нечетными степенями, поэтому необходимо добавить одно ребро, скажем между вершинами 4 и 7.

Полученный Эйлеров путь: 0,3,2,0,1,2,5,1,4,5,6,1,7,4,6,9,7,8,9,3,8,5,3.

Схема Эйлерова пути приведена на рис.1.4 (добавленное ребро показано пунктиром):

Рисунок 1.4 - Эйлеров путь, полученный путем добавления ребра

1.3.2 Эйлеров цикл

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

Аналогично пункту 1.4.1 добавляем ребро {3,0}, замыкая Эйлерову цепь (при этом выполняя условие существования Эйлерова цикла - четность степеней всех вершин). Ребро {3,0} кратное, что не противоречит заданию, но при необходимости можно ввести ребра {0,7} и {4,3} вместо ранее введенных. Полученный Эйлеров цикл: 0,3,2,0,1,2,5,1,4,5,6,1,7,4,6,9,7,8,9,3,8,5,3,0. Схема Эйлерова цикла (добавленные ребра показаны пунктиром):



Рисунок 1.5 - добавление двух ребер для получения Эйлерова цикла

1.4 Проверка ориентированного графа на наличие циклов путем отбрасывания «истоков» и «стоков»

У нас исток вершина V0, ее исходящие дуги X0={(0,1),(0,2),(0,3)}, рис.1.6.

Рисунок 1.6 - Выделение первого истока

Теперь за исток принимаем вершину V1, отбрасываем ее и дуги X1={(1,2), (1,4), (1,5), (1,6)}, рис.1.7.



Рисунок 1.7 - Новые истоки после отбрасывания V0

Теперь истоком стала вершина V2, отбрасываем ее и дуги X2={(2,3), (2,5)}, рис.1.8. математический граф вершина матрица

Рисунок 1.8 - Истоки после отбрасывания V2.

В оставшемся подграфе истоком является вершина V4, отбрасываем ее и дуги X4={(4,6), (4,5)}.

Рисунок 1.9 - Истоки после отбрасывания V4

В оставшемся подграфе истоком является вершина V5, отбрасываем ее и дуги X5 ={(5,3), (5,6), (5,8)}, рис.1.10.

Рисунок 1.10 - Подграф, полученный путем отбрасывания вершины V5

В оставшемся подграфе два истока - 3 и 6, выбираем вершину V3, отбрасываем ее и дуги X3 ={(3,8), (3,9)}, рис.1.11.

Рисунок 1.11 - Подграф, полученный отбрасыванием вершины V3

В оставшемся подграфе два истока - 6 и 7, выбираем вершину V6, отбрасываем ее и ее дугу X6 ={(6,9)}, рис.1.12.

Рисунок 1.12 - Подграф, полученный отбрасыванием вершины V6

В оставшемся подграфе истоком является вершина V7, отбрасываем ее и дуги X7 ={(7,8), (7,9)}, рис.1.13.

Рисунок 1.13 - Подграф, полученный отбрасыванием вершины V7

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

1.5 Поиск остовного (остевого) дерева алгоритмом Прима-Краскала

Выписываем таблицу весов ребер, упорядоченную по убыванию, табл.1.2.

Таблица 1.2 Веса ребер графа G

Вес	Ребра
1	(1,2), (3,8), (5,3), (5,8), (7,8), (7,9)
2	(1,5), (2,3), (4,6), (5,6), (6,9)
3	(0,2)
4	(1,6), (4,5)
5	(1,7), (2,5)
6	(3,9), (8,9)
8	(0,1)

Последовательность шагов по решению задачи Прима-Краскла:

1) выбираем ребро (1,2), окрашиваем вершины V1 и V2 в красный цвет;

2) выбираем ребро (3,8), обе его вершины V3 и V8 пока бесцветны, окрашиваем их в синий цвет;

3) следующим выбираем ребро (3,5), вершина V3 синяя, V5 - бесцветная, следовательно, заливаем V5 синим цветом;

4) пытаемся выбрать ребро (5,8), но обе его вершины уже синего цвета: это ребро в решение не войдет;

5) выбираем ребро (7,8), вершина V8 синяя, вершина V7 пока бесцветная, закрашиваем V7 в синий цвет;

6) выбираем ребро (7,9), вершина V9 бесцветная, теперь будет синей;

7) выбираем ребро (1,5), его вершины разноцветные, красный цвет был задействован раньше синего, так что все синие вершины перекрашиваем теперь в красные;

8) пытаемся выбрать ребро (2,3), но обе его вершины уже красного цвета: это ребро в решение не войдет;

9) берем ребро (4,6), вершина V6 бесцветная, теперь будет красной;

10) пытаемся выбрать ребра (5,6) и (6,9), но все их вершины уже красного цвета: эти ребра в решение не войдут;

11) берем ребро (0,2), вершина V0 бесцветная, теперь будет красной;

12) мы выбрали 8 ребер на графе из 9 вершин, дерево построено.

Вес найденного дерева - 14. Построенное дерево приведено на рис.1.14.

Рисунок 1.14 - Остовное дерево, полученное по алгоритму Прима-Краскла

1.6 Определение дерева кратчайших путей по алгоритму Дейкстры

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

Достижимость минимальных весов:

q0,2 = 3;

q0,3 = 5;

q0,8 = 6;

q0,7 = 7;

q0,1 = 8;

q0,9 = 8.

Можно продолжать расчеты по алгоритму Дейкстры для вершин 4, 5 и 6, но они уже не повлияют на полученное решение.

Рис.1.15 Кратчайшие пути, полученные по алгоритму Дейкстры

2. Постановка задачи на программирование

2.1 Интерфейс программы

Интерфейс программы приведен на рис.2.2.

Рисунок 2.1 - Интерфейс программы

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

Верхнее иконочное меню в основном ориентировано на создание графа. Каждый пункт меню имеет собственный hint-подсказку, а потому на рисунке не прокомментирован. Тем не менее перечислим все выполняемые этими кнопками функции (слева направо):

- очистить поле от нарисованного графа;

- сохранить нарисованный граф для последующей загрузки и расчетов;

- произвести вычисления;

- режим «бездействия» (верхнее меню неактивно);

- создание вершин (щелчок мыши на черном поле, кружки-shape вершин нумеруются автоматически);

- соединение вершин ребрами (щелчок мышью на исходной и конечной вершинах, щелчок на черном поле ни к каким действиям не ведет);

- указание направления дуг (осуществляется двумя щелчками мыши от стартовой к финишной вершинам);

- ввод веса ребер или дуг;

- соединение всех вершин (автоматические получение полносвязного неориентированного графа);

- вызов справки (обращение к собственному hlp-файлу).

Нижний многостраничный компонент после нажатия зеленой стрелки «Вычислить» выводит результаты расчетов. Например, как это показано на рис.2.1.

Рисунок 2.1 - Результаты расчетов в многостраничном компоненте

Заключение

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

Разработана программа на языке Object Pascal в среде Delphi 7.0, позволяющая выполнить это в автоматизированном режиме.

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

Список использованных источников

Иванов И.И., Петров П.П., Сидоров С.С. Наблюдение звезд на даче с крыши сарая и душевой. - Киев: Веселка, 1975. - 768 с.

Рулез Дж., Маздай Ф. Как выучить Delphi, чтобы тебя любили? - М.: Изд-во иностранной литературы, 1962. - 319 с.

Эминем Э. Delphi для не умеющих читать и писать: Алгоритмический подход. - М.: Мир, 1898. - 432 с.

Кличко В. Машинная графика для тех, у кого заплыли оба глаза // Мой компьютер. - 2003, № 44. - С.12-14.

Размещено на Allbest.ru

...