Задача нахождения максимального паросочетания в графах

СОДЕРЖАНИЕСОДЕРЖАНИЕ2
ВВЕДЕНИЕ3
1. ОСНОВНЫЕ ПОНЯТИЯ ТЕОРИИ ГРАФОВ4
1.1 Основные определения4
1.1.1 Граф4
1.1.2 Пути и маршруты5
1.1.3 Вес и длина пути7
1.1.4 Петли, ориентированные циклы и циклы7
1.1.5 Степени вершины9
1.1.6 Подграфы10
1.1.7 Типы графов11
1.1.8 Компоненты графа13
1.1.9 Деревья13
1.2 Матричные представления14
1.2.1 Матрица смежности14
1.2.2 Матрица инциденций14
2. ПРОЕКТНАЯ ЧАСТЬ16
2.1 Актуальность и цель работы16
2.2 Описание предметной области16
2.2.1 Паросочетания16
2.2.2 Альтернирующие цепи и деревья19
2.2.3 Цветки21
2.2.4 Венгерские деревья21
2.2.5 Алгоритм для ЗМП23
2.3 Программная реализация24
2.3.1 Выбор языка программирования24
2.3.2 Использованные программы25
2.3.3 Описание алгоритма26
Описание алгоритма27
2.3.4 Сценарий28
2.3.5 Написание кода программы28
2.3.6 Тестирование43
ЗАКЛЮЧЕНИЕ45
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ И ЛИТЕРАТУР46
ПРИЛОЖЕНИЕ А49

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ И ЛИТЕРАТУР

Кристофидес Н. Теория графов. Алгоритмический подход. – М.: Мир, 1978. – 432с.
Свами М., Тхуласираман К. Графы, сети и алгоритмы: Пер. с англ. – М.: Мир, 1984. – 455с.
Захарова Л.Е. Алгоритмы дискретной математики: Учебное пособию – М.: Моск. гос. Ин-т электроники и математики, 2002. – 120с.
Емеличев В.А. Лекции по теории графов/ В.А. Емеличев, О.И. Мельников, В.И. Сарванов, Р.И. Тышкевич – М.: Наука, 1990. – 384с.
Макоха А.Н. Дискретная математика. / А.Н. Макоха, П.А. Сахнюк, Н.И. Червяков: Учеб. пособие. – М.: ФИЗМАТЛИТ, 2005. – 368с.
Берж К. Теория графов и ее применения. – М.:Изд. иностр. лит., 1962. – 320с.
Белоусов А.И. Дискретная математика: учебник для вузов/А.И. Белоусов, С.Б. Ткачев; под ред. В.С. Зарубина, А.П. Крищенко. – М.: Изд-во МГТУ им. Н.Э. Баумана, 2015. – 743с.
Кормен Т.Х. Алгоритмы: Построение и анализ. – 3-е изд.: пер. с англ. – М.: ООО «И.Д. Вильямс», 2013. – 1328с.
Майника Э. Алгоритмы оптимизации на сетях и графах. – М.: Мир, 1981. – 324с.
Новиков Ф.А. Дискретная математика для программистов. – СПб.: Питер, 2003. – 304с.
Уилсон Р. Дж. Введение в теорию графов. – 5-е изд., пер. с англ. – СПб.: ООО «Диалектика», 2019. – 240с.
Харари Ф. Теория графов. – М.: Мир, 1973. – 300с.
Ерусалимский Я.М. Дискретная математика: теория, задачи, приложения. – 3-е изд. – М.: Вузовская книга, 2000. – 280с.
Ловас Л., Пламмер М. Прикладные задачи теории графов. Теория паросочетаний в математике, физике, химии. – М.: Мир, 1988. – 653с.
H.N. Gabow. An Efficient Implementation of Edmonds Algorithm for Maximum Matching of Graphs. J. ASM, vol, 23, 221-234 (1976)
Макоха А.Н. Дискретная математика. / А.Н. Макоха, П.А. Сахнюк, Н.И. Червяков: Учеб. пособие. – М.: ФИЗМАТЛИТ, 2005. – 368 с.
Златопольский Д.М. Основы программирования на языке Python. – М.: ДМК Пресс, 2017. – 284 с.
Лутц М. Программирование на Python, том I, 4-е издание. – Пер. с англ. – СПб.: Символ-Плюс,

Здесь все вершины, лежащие в конце максимальных цепей, начинающихся с корня, в соответствии
Рис. 2.2 I – внутренние вершины, Ф – внешние вершины
с условием (c) будут «внешними». Степень любой внутренней вершины альтернирующего дерева равна 2, в то время как степень внешней вершины может быть любым целым положительным числом.
Аугментальное дерево – это альтернирующее дерево относительно данного паросочетания, удовлетворяющее условию: существует рёбро от какой-нибудь внешней вершины дерева xo, до некоторой экспонированной вершины xe, не принадлежащей дереву. Единственная цепь, идущая от корня дерева до вершины xo и далее – по ребру (xo, xe), будет тогда аугментальной цепью.
2.2.3 Цветки

Цветком по отношению к паросочетанию M называется аугментальная цепь, начальная и конечная экспонированные вершины которой совпадают, т.е. эта цепь является циклом, так как число рёбер этой цепи нечетно. На рис. 2.3 изображен цветок