Цел: Да се намери най-голямото разбиване по двойки за двуделен неориентиран граф G с N женски и N мъжки върха и M ребра.
Един граф е двуделен, ако множеството от върховете му се разбива на две подмножества - Vf (женски) и Vm (мъжки), така че краищата на всички ребра са в различни подмножества.
Разбиване по двойки (или назначаване на срещи) наричаме такова подмножество A от ребра на G, че всеки връх да попада в най-много едно ребро от A.
С други думи, ако ребрата на G означават харесване между съответните женски и мъжки върхове, търси се максимално количество двойки, които да се срещнат едновременно.
Идея на алгоритъма:
1. Ребрата се прочитат.
2. Тръгваме от празно разбиване.
3. Търси се нарастваща верига.
Ако се намери, ребрата по веригата се обръщат, което увеличава с 1
ребрата в разбиването.
Тази стъпка се повтаря за всеки женски връх.
Коректността на алгоритъма се дължи на:
Забележки:
1. Не се проверява коректност на данните.
Бързодействие:
Приведеният алгоритъм има сложност O(N^3).
Сходни задачи и допълнителни свойства:
Най-голямото разбиване и най-малкото покритие на граф са пряко свързани задачи. Математическите свойства на тази връзка ни дават тривиален алгоритъм за намиране минимално покритие, стига да сме намерили максимално разбиване.
ИМЕ НА ЗАДАЧАТА: matchs ВХОДЕН ФОРМАТ: * Ред 1: Две цели числа, разделени с интервал: N и M N е броят на върховете в графа (N<=100), а M е броят на ребрата (M<=10000). * Редове от 2 до M+1: Всеки ред съдържа 2 параметъра: I и J, които описват ребро. I е женският, а J - мъжкият връх на реброто. ПРИМЕРЕН ВХОД (файл matchs.in): 5 9 1 4 2 5 5 3 1 1 2 2 3 3 4 4 5 4 3 2 ИЗХОДЕН ФОРМАТ: * Ред 1: брой K на срещите в масималното разбиване * Редове от 2 до K+1: ребра на разбиването, показващи кой женски с кой мъжки връх трябва да се срещне. ПРИМЕРЕН ИЗХОД: mathcs=5 1 1 2 5 3 2 4 4 5 3