МІНІСТЕРСТВО ОСВІТИ І НАУКИ МОЛОДІ ТА СПОРТУ

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

"ХАРКІВСЬКИЙ НАЦІОНАЛЬНИЙ ІНСТИТУТ"

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

Курсова робота

"Дискретна математика"

Тема

" Теорія графів . Опис графів . "

Варіант 9

Керівник роботи :

Доц . каф . САІУ . Кащеєв Л.Б.

Виконавець :

Студент групи ІФ 51-в Ляшенко С.С.

Харків 2012

МІНІСТЕРСТВО ОСВІТИ НАУКИ МОЛОДІ ТА СПОРТУ

НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ ИНСТИТУТ

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

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

Оцінка

________________________

голова комісії

доц. каф.САиУ

____________ /Кащеєв Л.Б./

« » ___________ 201 _ р.

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

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

Тема: „Теорія графів. Опис графів.”

(Варіант №9)

Виконавець: ст. гр. ИФ-51^в Ляшенко С.С.

“ ” 201 р.

Керівник роботи: доц.Кащеєв Л.Б.

“ ” 201 р.

Харків 2012

МІНІСТЕРСТВО ОСВІТИ НАУКИ МОЛОДІ ТА СПОРТУ

НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ ИНСТИТУТ

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

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

Студент Ляшенко С.С. групи ІФ 51-в

ЗАВДАННЯ

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

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

Тема: „Теорія графів. Опис графів ”(Варіант №9)

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

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

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

Описати граф за допомогою : множини дуг та вершин , списками суміжності,матрицею інцидентів,матрицею ваг,матрицею суміжності ,перечислити суміжності ,провести нумерацію вершин у ширину та глибину , замінити дуги на ребра (перетворити в не орієнтований граф ),з’ясувати граф Єйлеров , якщо так намалювати цикл , якщо ні намалювати ребра та намалювати цикл , найти основне дерево , знайти мінімальне значення вершин , знайти остове дерево алгоритмом Прима – Краскла , повернутися до орієнтованого графа, решити задачу коммивояжора .

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

На не орієнтованому графі розрахувати задачу Форда - Уоршала.

Перетворити неорієнтований граф в дводольний .

Розрахувати задачу з максимальним пара сходженням ,

Розрахувати задачу о призначеннях.

СОДЕРЖАНИЕ

Введение …….………..………………………………………………………..5

1 Расчетная часть работы ……………………………………………………..6

1.1 Задание на проектирование ………………………………………………6

1.2 Математическое описание графа ………………………………………...6

1.2.1 Описание графа G^ор множествами вершин V и дуг X ………...6

1.2.2 Описание графа G^ор списками смежности ……………………..6

1.2.3 Описание графа G^ор матрицей инцидентности ………………..7

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

1.2.5 Описание графа G^ор матрицей смежности ……………………..7

1.2.6 Степени вершин неориентированного графа …………………...7

1.3 Нумерация вершин графа ………………………………………………....8

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

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

1.4 Эйлеров путь и Эйлеров цикл на графе ………………………………….9

1.4.1 Поиск на графе Эйлерова пути ………………………………….9

1.4.2 Построение на графе Эйлерова цикла ………………………….9

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

1.6. Поиск остовного (остевого) дерева алгоритмом Прима-Краскала …..13

1.7. Расчет сетевого графа …………………………………………………...15

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

2.1. Постановка задачи ………………………………………………………16

2.2. Описание разработанного объекта ……………………………………..16

2.2.1. Иерархия наследования ………………………………………..16

2.2.2. Организация объекта ……………………..…………………….17

2.3. Интерфейс программы ………………………………………………….18

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

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

Введение

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

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

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

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

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

ГРАФ

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

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

G^ор(V,X)

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

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

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

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

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

{5,4},{5,7},{6,9},{7,6},{7,10},{8,5},{8,7},{8,10},{8,9},{9,11},{10,11}}

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

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

Г4={11,12}; Г5={13,14}; Г6={21}; Г7={16,20};

Г8={17,18,15,19}; Г9={22}; Г10={23}; Г9={null};

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

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

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