Патенты с меткой «паросочетания»

Номер патента: 669360

Опубликовано: 25.06.1979

Авторы: Садовой, Чернышев

МПК: G06G 7/48

Метки: максимального, паросочетания, сетях, транспортных

...У 6 У с вершиной С ребром спропускными способностями равными 1. 35Получим транспортную сеть, изображенную на фиг. 3.Задача нахождения максимального.гаросочетания для полученной транспортной сети сводится к нахождениюмаксимального потока н ней, при условии, что ребра, соединяющие вершины (Х и У) имеют пропускнуюспособность, равную соАлгоритм нахождения максимальногопотока состоит из нескольких этапов,Находим первоначальное паросочетание. Для этого пропускаем потоквеличины 1 от источника И по какомулибо пути к стоку С, удаляем из графа насыщенные дуги, а дугу, вошедшуюн паросочетание, отмечаем знаком (дуги Инцидентные ей(Х) отмечаемметкой .х) (см, фиг. 4).Далее происходит увеличение паросочетания. 55Для этого находим вершины...