Алгоритм решения задачи отыскания наибольшего паросочетания
Автор: Elis25 • Апрель 28, 2019 • Курсовая работа • 8,216 Слов (33 Страниц) • 615 Просмотры
КАЗАНСКИЙ (ПРИВОЛЖСКИЙ) ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ
ФАКУЛЬТЕТ ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ И ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ
СПЕЦИАЛЬНОСТЬ «БИЗНЕС-ИНФОРМАТИКА»
КАФЕДРА АНАЛИЗА ДАННЫХ И ИССЛЕДОВАНИЯ ОПЕРАЦИЙ
Курсовая работа
«Алгоритм решения задачи отыскания наибольшего паросочетания»
Выполнила:
студентка группы 09-503
Алимова Элина Сергеевна
Научный руководитель:
Доцент кафедры анализа данных
и исследования операций
Шульгина Оксана Николаевна
Казань 2018
Содержание
Введение……………………………………………………….…..3
- Цель работы………………………………………………...4
- Постановка задачи………………………………………….5
- Алгоритм решения…………………….…………..……….6
- Описание работы программы……………………………...7
- Листинг…………………………………………………….14
Список использованной литературы……………………………22
Введение.
В XXI веке возникает огромное количество проблем, которые можно решить с помощью информационных технологий. Например, у нас появилась следующая ситуация: в некоторой развивающейся туристической корпорации существует задача отправить наибольшее количество клиентов в различные страны, при условии, что клиент уже знаком с данной страной, то есть посещал её. Для автоматизации решения появившейся проблемы с помощью электронных вычислительных машин, используется теория графов, а если быть точнее, теория паросочетаний.
Приведённый мною пример далеко не единственный случай применения этой теории. Например, можно помочь работодателям в подборе потенциальных сотрудников на работу, распределить студентов по группам или школьников по классам. Автоматизация данного процесса на данном этапе развития общества может приносить реальную прибыль, как частным, так и государственным предприятиям и с успехом решать задачи различного уровня масштабов.
Цель.
Цель моей работы заключается в разработке алгоритма поиска наибольшего паросочетания на языке программирование С#.
Поставленная мною цель определила следующие задачи:
- изучить алгоритм поиска наибольшего паросочетания в двудольном графе;
- применить алгоритм для нахождения наибольшего паросочетания в двудольном графе;
- выполнить программные реализации алгоритма на языке С#.
Постановка задачи.
Пусть G = G(V, R) – неориентированный граф, в котором отсутствуют петли. Если подмножество рёбер M ⸦ R такое, что его любые два ребра неинцидентны (то есть не имеют общей вершины) друг другу, то M называют паросочетанием в графе G. Договоримся, что любое ребро графа G будет являться паросочетанием в данном графе.
Пусть M(G) – множество всех паросочетаний в графе G. Совершенно понятно, что если R ≠ Ø, то и M(G) ≠ Ø. Паросочетание в графе G, которое содержит наибольшее количество рёбер, будем называть наибольшим паросочетанием в графе G. Отметим, что наибольшее паросочетание в графе может быть не единственным. Пусть
M*(G) = Arg max |M|, где M ∈ M(G).
Под задачей построения набольшего паросочетания в неориентированном графе G будем понимать задачу отыскания любого элемента M* из множества M*(G).
Пусть M ∈ M(G). Простая цепь графа G называется чередующейся относительно M, если её рёбра с нечётными номерами входят в M, а с чётными в R\M, или наоборот – чётные номера входят в M, а нечётные – в R\M. Обозначим эту цепь C (М). Пусть цепь, состоящая из любого ребра графа G, тоже назовём чередующейся относительно M. Рёбра цепи C(M) будем называть насыщенными или ненасыщенными паросочетанием M, если они принадлежат или, соответственно не принадлежат М. Вершины графа G, которые инцидентны рёбрам из М, называют насыщенными, а все остальные – ненасыщенными паросочетанием М.
...