52
правки
Изменения
→Теорема Эдмондса
Тогда в <tex>G</tex> существует удлиняющий путь тогда и только тогда, когда существует удлиняющий путь в <tex>G\setminus B</tex>
|proof=
Пусть граф <tex>G'</tex> - граф, полученный <tex>G</tex> сжатием цветка соцветия <tex>B</tex> в псевдо-вершину <tex>B'</tex>.<br />Заметим, что достаточно рассматривать случай, когда база соцветия является свободной вершиной (не принадлежащей паросочетанию). Действительно, в противном случае в базе соцветия оканчивается чередующийся путь чётной длины, начинающийся в свободной вершине. Прочередовав паросочетание вдоль этого пути, мощность паросочетания не изменится, а база соцветия станет свободной вершиной.
<tex>\Rightarrow</tex>
Пусть путь <tex>P</tex> является увеличивающим путём в графе <tex>G'</tex>. Если <tex>P</tex> не проходит через <tex>B'</tex>, то тогда он будет удлиняющим и в графе <tex>G</tex>. <br />
Рассмотрим отдельно случай, когда <tex>P</tex> начинается со сжатого соцветия <tex>B'</tex>, т.е. имеет вид <tex>(B', c, ...)</tex>. Тогда в соцветии <tex>B</tex> найдётся соответствующая вершина <tex>v</tex>, которая связана ребром с <tex>c</tex>. Заметим, что из базы соцветия всегда найдётся чередующийся путь чётной длины до вершины <tex>v</tex>. Учитывая всё вышесказанное, получаем, что путь <tex>P_1(b,...v,...c,..)</tex> является увеличивающим путём в графе <tex>G</tex>.
}}
