80
правок
Изменения
→Идея алгоритма
==Идея алгоритма==
Пусть дан неориентированный двудольный граф <tex>G(V, E)</tex> и требуется найти [[Теорема о максимальном паросочетании и дополняющих цепях|максимальное паросочетание]] в нём. Обозначим доли исходного графа как [[Файл:GrafG.png|thumb|200px|right|граф G]][[Файл:GrafG2.png|thumb|200px|right|граф G']]<tex>L</tex> и <tex>R</tex>. Построим граф <tex>G'(V', E')</tex> следующим образом:
<tex>V' = V \cup \{s, t\}</tex> (т.е. добавим новый исток <tex>s</tex> и сток <tex>t</tex>);
