Изменения

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

Участник:Masha

5 байт добавлено, 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> \max\limits_{S \in V}(odd(G \setminus S) - |S|) = k \; </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>. Заметим, что после удаления в графе осталось <tex>odd(G \setminus A)\; </tex> нечетных компонент и образовались новые непокрытые вершины, но при этом осталось  число нечетных компонент больше числа удаленных на <tex>k</tex> больше нечетных компонент, чем было удалено, значит, . Значит хотя бы <tex>k</tex> нечетных компонент содержали исходно непокрытую вершину, значит, следовательно <tex>k \; \leq \; def(G)</tex>. Значит, <tex>def(G) \; = \; k</tex>. Теорема доказана.
}}
49
правок

Навигация