Изменения

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

Участник:Masha

96 байт добавлено, 16:44, 6 июня 2021
Формула Бержа
== Формула Бержа ==
{{Лемма(1)
|statement= <tex>(n + |S| + odd(G \setminus S)) \; mod \; 2 = 0</tex>, где <tex>G</tex> - граф с <tex>n</tex> вершинами, <tex>S \in {V}_{G}</tex>
|proof=
1) Если <tex> \max\limits_{S \in V}(odd(G \setminus S) \; - \; |S|) \; = 0 \; </tex>, тогда <tex>\forall \; S \in \; V: \; odd(G \setminus S) \leq |S| \; </tex> и выполнен [[Теорема Татта о существовании полного паросочетания|критерий Татта]], значит, в графе есть совершенное паросочетание, т.е. его дефицит равен нулю.
2) Если <tex> \max\limits_{S \in V}(odd(G \setminus S) - |S|) = k </tex>, тогда рассмотрим исходный граф <tex>G</tex> и [[Полный граф|полный граф]] <tex>K_k</tex> с <tex>k</tex> вершинами, множество вершин нового графа обозначим как <tex>W</tex>. Каждую вершину вспомогательного графа соединим с каждой вершиной <tex>G</tex>. Получим новый граф <tex>H \; = \; K_k + G</tex>, докажем, что для него выполнено условие Татта. Докажем, что <tex>\forall S \in V_{H}: odd(G \setminus S) \; \leq \; |S| \; </tex>. Рассмотрим <tex>S \; \subset \; V_H\;</tex>.
a) Если <tex>W \not\subset S</tex>, тогда посколько граф <tex>K_k</tex> полный и все его вершины связаны с каждой вершиной графа <tex>G</tex>, то граф <tex>H</tex> связный и <tex>odd(H \setminus S) \; = \; 0\;</tex> или <tex>odd(G \setminus S) \; = \; 1\;</tex>. В случае <tex>odd(H \setminus S) \; = \; 0</tex> условие очевидно выполняется т.к <tex>\forall S \in G : 0 \; \leq \; |S|</tex>. Рассмотрим случай <tex>odd(H \setminus S) \; = \; 1 \;</tex>, <tex>|V_H| \; = \; n \; + \; k \; = \; n \; + \; odd(G \setminus A) - |A|</tex>, где <tex>A = arg \max\limits_{S \in V}(odd(H \setminus S) - |S|) </tex>. Разность <tex>odd(G \setminus A) - |A|</tex> имеет ту же четность, что и <tex>n</tex>, поэтому <tex>|V_H|</tex> четно, значит, по лемме (1), мощность <tex>S</tex> нечетна, следовательно, она не равна нулю, значит <tex> 1 \leq |S|</tex>.
Если <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>odd(H \setminus S) = 1</tex>, <tex>|V_H| = n + k = n + odd(G \setminus A) - |A|</tex>, где <tex>A = arg \max\limits_{S \in V}(odd(H \setminus S) - |S|) </tex>. Разность <tex>odd(G \setminus A) - |A|</tex> имеет ту же четность, что и <tex>n</tex>, поэтому <tex>|V_H|</tex> четно, значит, по лемме мощность <tex>S</tex> нечетна, следовательно, она не равна нулю, значит <tex> 1 \leq |S| </tex>. Если <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>. Заметим, что после удаление в графе осталось несколько нечетных компонент и образовались новые непокрытые вершины, но при этом осталось на <tex>k</tex> больше нечетных компонент, чем было удалено, значит, хотя бы <tex>k</tex> нечетных компонент содержали исходно непокрытую вершину, значит, <tex>k \; \leq \; def(G)</tex>. Значит, <tex>def(G) \; = \; k</tex>. Теорема доказана.
}}
49
правок

Навигация