Однако существует куча простых и эффективных алгоритмов, позволяющих найти это самое максимальное паросочетание в графе двудольном. Решение даже такой задачи является достаточно актуальным. Наиболее известная задача на применение подобных алгоритов имеет следующую формулировку: "Имеется X мальчиков и Y девочек. Каждый согласен танцевать на балу только с определёнными индивидами противополжного пола, причём это отношение коммутативно - если мальчик согласен танцевать с какой-то девочкой, то она тоже согласна танцевать с ним и наоборот. Организаторам бала необходимо набрать наибольшее количество пар на танец. Логично, что каждый индивид танцует не более, чем с одним другим".
На основе данных задачи можно построить двудольный граф, в котором вершины одной доли обозначают мальчиков, а другой - девочек. Две вершины соединяются ребром, если соответствующие мальчик и девочка согласны танцевать друг с другом. Построив в данном графе максимальное паросочетание, мы и сформируем необходимое множество пар.
Для реализации приведённых алгоритмов граф удобно хранить не матрицей смежности, не списком рёбер, а этаким мутантом, смахивающим более всё-таки на матрицу смежности. Эту структуру мы будем называть матрицей смежности двудольного графа:
| Var A: array[1..MaxX, 1..MaxY] of Boolean; |
Если элемент матрицы A[I, J] равен True это значит, что из I-ой вершины одной доли и J-ой вершиной другой есть ребро. Если элемент равен False, то ребра, логично, нет.
Заметим, что, хотя хранимый граф неориентирован (а задача о нахождении максимального паросочетания имеет смысл лишь на таком графе), элементы A[I, J] и A[J, I] не обязательно равны и обозначают наличие разных рёбер. Этим фактом подчёркивается разница рассматриваемой структуры и матрицы смежности графа, не путайте их! Баги будут.
Ниже приведена сравнительная таблица работы алгоритмов данной главы. Аналогично аналогичной таблице в предыдущей главе, она будет более интересна Вам после изучения самих алгоритмов.
| Алгоритм | Объект работы | Действие | Сложность | Доп. память | Полезн. |
| Алгоритм Куна |
Двудольный неориентированный невзвешенный граф | Нахождение максимального паросочетания в графе | O(N3) | O(N) | 9 |
| Алгоритм Хопкрофта-Карпа | O(MN1/2) | O(?) | 3 |
Значение заголовков такое же, как и в аналагочной таблице в предыдущей главе, только здесь нет разделения сложности работы алгоритма при раличных способах хранения графа, т.к. предпологается одна лишь матрица смежности двудольного графа.
Как видим, особого разнообразия нашему вниманию не предлагается. Да к тому же второй алгоритм вообще имеет рейтинг всего-навсего 3. Это не случайно - он весьма сложен, а необходимость в нём возникает очень редко.
Если Вы сей час обратитесь ко второму абзацу текущей страницы, то увидете фразу о большом количестве способов построения паросочетания в двудольном графе, хотя в предыдущем абзаце утверждалось обратное. Дело в том, что в данной главе будут рассматриваться алгоритмы, ориентированные именно на построение паросочетания, коих действительно не так много. А вот в главе следующей будет рассказано о способах построения максимального потока, к задаче о нахождении которого может быть легко сведена задача построения максимального паросочетания в двудольном графе. Способов же построения максимального потока много больше, чем представлено в данном учебнике.