МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ “ХАРКІВСЬКИЙ ПОЛІТЕХНІЧНИЙ ІНСТИТУТ” Кафедра “Системного аналізу та управління” Курсова робота Дисципліна “Дискретна математика" Тема “ Двочасткові графи. Опис графів. Задача о призначеннях ” (Варіант №58-63) Керівник роботи: доц. каф. САіУ, канд.техн.наук Жданов А.П. Виконавець: студентка групи ІФ-50в Пушкарьова К.В. Харків – 2007 |
МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ “ХАРКІВСЬКИЙ ПОЛІТЕХНІЧНИЙ ІНСТИТУТ”
Кафедра “Системного аналізу та управління”
Оцінка
________________________
голова комісії
доц. каф.САиУ
____________ /Кащеєв Л.Б./
« » ___________ 200 _ р.
КУРСОВА РОБОТА
Дисципліна: „Дискретна математика”
Тема: „Двочасткові графи. Опис графів. Задача о призначеннях”
(Варіант №58-63)
Виконавець:
ст. гр. ИФ-50в
С.М.Лук’яненко
“ ” 200 р.
Керівник
роботи:
доц., канд. техн. наук Н.М.Перумов
“ ” 200 р.
Харків 2007
МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ “ХАРКІВСЬКИЙ ПОЛІТЕХНІЧНИЙ ІНСТИТУТ”
Кафедра “Системного аналізу та управління”
Студент С.М.Лук’яненко Група ИФ-50в
ЗАВДАННЯ на науково-дослідну курсову роботу
Дисципліна: “Дискретна математика”
Тема: „Двочасткові графи. Опис графів. Задача о призначеннях”(Варіант №58-63)
Короткий зміст роботи:
а) теоретична частина
Розробка методики дослідження дводольного графу наведеного на малюнку:
Провести математичний опис графу; проаналізувати граф на наявність Эйлерова циклу або Эйлерова шляху; знайти остовне дерево; не вважаючи на вагу ребер розв’язати задачу о максимальному паросполученні, розв’язати задачу о призначеннях з мінімізацією та максимізацією збитків.
б) програмно-розрахункова частина
Розробка програмного забезпечення, яке реалізує графічний ввод графу, виводить на екран відповідні матриці, розв’язує максимізаційну задачу о призначеннях (без використання операції Егервари)
Дата видачі завдання: 15.03.2007 Термін захисту: 21.05.2007
Керівник курсової роботи: / канд. техн. наук, доц. САіУ
Н.М.Перумов/
Содержание
Введение …….………..………………………………………………………..5
1 Граф ………………………………………………………………………….6
1.1 Задание на проектирование ………………………………………………6
1.1.1 Описание графа K1,2 множествами вершин V и дуг X ………...6
1.1.2 Описание графа K1,2 списками смежности ……………………..6
1.1.3 Описание графа K1,2 матрицей инцидентности …………………6
1.1.4 Матрица весов двудольного графа ………………………………7
1.1.5 Описание графа K1,2 матрицей смежности (вершина-вершина) .7
1.1.6 Степени вершин двудольного графа …………..………………...8
1.2 Эйлеров путь и Эйлеров цикл на графе ………………………………….8
1.3.1 Поиск на графе Эйлерова пути …………………………………..8
1.3.2 Эйлеров цикл …………………………..………………………….9
1.3 Поиск остовного (остевого) дерева алгоритмом Прима-Краскала ….....9
1.4 Решение задачи о максимальном паросочетании ………………….…...10
1.5 Задача о назначениях ……………………………………………………..11
1.5.1 Задача о назначениях с минимизацией потерь …………………11
1.5.2 Задача о назначениях с максимизацией потерь ………………...13
2. Постановка задачи на программирование ………………………………..15
2.1. Постановка задачи ………………………………………………………15
2.2. Описание разработанного объекта ……………………………………..15
2.2.1. Иерархия наследования ………………………………………..15
2.2.2. Организация объекта ……………………..…………………….16
2.3. Интерфейс программы ………………………………………………….17
Заключение …………………………………………………………………...20
Список использованных источников ……………………………………….21
Введение
Двудольные графы (Bipartite graph) – относительно небольшой подраздел теории графов. Под этим термином понимается граф, у которого существует такое разбиение множества вершин на две части (доли), что концы каждого ребра принадлежат разным долям (студенты – преподаватели, предметы – аудитории, женихи – невесты, должности – назначенцы). Если при этом любые две вершины, входящие в разные доли, смежны, то граф называется полным двудольным. Специфика объекта определяет относительно небольшое количество алгоритмов, разработанных для двудольных графов – в основном речь идет о задаче о максимальном паросочетании и задаче о назначениях, которым, в общем, и посвящена данная работа. Причем задача о назначениях имеет настолько большую практическую значимость, что для ее решения разработан весьма сложный «венгерский алгоритм».
Вместе с тем, двудольный граф в основе своей остается графом, а потому на нем можно решать целый ряд обычных «графовых» задач – описание графа матрицами, поиск циклов, деревьев, раскраска графа (хоть в принципе и известно, что двудольный граф является двухроматическим). Эти вопросы с той или иной степенью проработки также отражены в данной работе.
1 ГРАФ
1.1 Математическое описание графа
Исходный граф из задания представлен на рис. 1.1.
K1,2(V,X)
Рисунок 1.1 Исходный граф для расчетов
1.1.1 Описание графа K1,2 множествами вершин V и дуг X:
Нумерация вершин см. рис. 1.1.
Первая доля V1={1, 2, 3, 4}; вторая доля V2={A, B, C, D};
X={{1,A},{1,B},{1,C},{2,A},{2,B},{2,C},{3,BA},{3,C},{3,D},{4,A},{4,C}}
1.1.2 Описание графа K1,2 списками смежности:
K1={A,B,C}; K2={A,B,C}; K3={A,B,C}; K4={A,C,D};
KA={1,2,4}; KB={1,2,3}; KC={1,2,4}; KD={3};
1.1.3 Описание графа K1,2 матрицей инцидентности:
Данный граф может описан матрицей инцидентности вершина-ребро (нумерация вершин и ребер приведена для удобства, обычно она не пишется)
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
2 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
3 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
0 |
4 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
A |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
B |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
C |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
1 |
D |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
Соответствующая нумерация ребер представлена на рис.1.2.
Рисунок 1.2 - Нумерация вершин и ребер графа для матрицы инциденции