Изменения

Перейти к: навигация, поиск
Нет описания правки
[[Файл:Фрагмент_паросочетания.png‎ | thumb | right | рис. 2]]
<br>Существование паросочетания очевидно - это ребра <tex>(a_i,b_i)</tex>.
<br>Предположим, что существует другое паросочетание <tex>(a_i, b_{jij_i})</tex>. Тогда пусть <tex>i_0 = min \{ i \: | \: j_i < i \}</tex>. Обозначим <tex>j_{i_0}</tex> как <tex>i_1</tex>. Заметим, что <tex>i_1 < i_0</tex> и поэтому не может быть <tex>j_{i_1} < i_1</tex>, ведь <tex>i_0</tex> - минимальное из соответствующего множества. Так же невозможно <tex>j_{i_1} = i_1</tex>, поскольку тогда <tex>a_{i_0}</tex> и <tex>a_{i_1}</tex> имели бы одинаковую пару. Следовательно, <tex>j_{i_1} > i_1</tex> (рис.2). Это значит, что существует путь <tex>P_1 = (a_1, b_1, \ldots, a_{i_1}, b_{j_{i_1}}, a_{j_{i_1} + 1}, \ldots, a_k, b_k )</tex> короче, чем <tex>P</tex>.
<br> Противоречие.
}}
Анонимный участник

Навигация