когда в G не существует
когда в G не существует чередующейся цепи относительно M.
Теорема подсказывает реальный путь нахождения
наибольшего паросочетания. Пусть найдено некоторое паросочетание в графе G, на рисунке оно выделено “жирными” линиями. Ищем чередующуюся цепь - ее дуги выделены линиями со стрелками.
Она состоит из “тонких” дуг и “жирных”, причем начинается и заканчивается в свободных вершинах. Длина цепи нечетна. Делаем “тонкие” дуги “жирными” и наоборот. Паросочетание увеличено на единицу.
Общая логика.
begin
<ввод и инициализация данных>;
<найти первое паросочетание>;
while <есть чередующаяся цепочка?> do <изменить паросочетание>;
<вывод результата>;
end.
Очередь за определением данных и последовательным уточнением логики. Граф описывается матрицей А[N,M], где N - количество вершин в множестве X, а M в Y. Паросочетание будем хранить в двух одномерных массивах XN и YM. Для рассмотренного примера XN=[0,1,2,4] и YM=[2,3,0,4,0]. Уточнение фрагмента “найти
Индекс
Элементарные функции
Линейные уравнения
Нелинейные уравнения
Случайные числа
