Изменения

Перейти к: навигация, поиск

Участник:Masha

704 байта добавлено, 6 июнь
Формула Бержа
Если <tex>W \subset S</tex>, то <tex>odd(H \setminus S) = odd(G \setminus (S \cap V)) \leq |S \cap V| + k \leq |S| </tex>.
Таким образом, для графа <tex>H</tex> выполнено условие Татта, следовательно, в нём есть полное паросочетание. Рассмотрим полное паросочетание в графе <tex>H</tex>, удалим вершины <tex>W</tex> из графа <tex>H</tex>. Количество непокрытых вершин после удаления не больше, чем количество удаленных вершин <tex>k</tex>, значит, <tex>def(G) \leq k</tex>. Рассмотрим Удалим множество вершин <tex>A = arg \max\limits_{S \in V}(odd(H \setminus S) - |S|) </tex> из графа <tex>G</tex>. Заметим, что после удаление в графе осталось несколько нечетных компонент и образовались новые непокрытые вершины, но при этом осталось на k больше нечетных компонент, чем мы удалили, значит, хотя бы k нечетных компонент содержали исходно непокрытую вершину, значит, <tex>k \leq def(G)</tex>. Значит, <tex>def(G) = k</tex>. Теорема доказана.
}}
Анонимный участник

Навигация