Участник:Masha — различия между версиями
(→Формула Бержа) |
(→Формула Бержа) |
||
| Строка 12: | Строка 12: | ||
| − | {{Теорема | + | {{Теорема Бержа |
|statement= <tex>def G = \max\limits_{S \in V} (odd(G \setminus S) - |S|)</tex> | |statement= <tex>def G = \max\limits_{S \in V} (odd(G \setminus S) - |S|)</tex> | ||
|proof= | |proof= | ||
| Строка 27: | Строка 27: | ||
Если не <tex>W \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> четно, значит, по лемме мощность <tex>S</tex> нечетна, следовательно, она не равна нулю, значит <tex> 1 \leq |S| </tex>. | Если не <tex>W \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> четно, значит, по лемме мощность <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>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>. Рассмотрим | ||
}} | }} | ||
Версия 15:59, 6 июня 2021
Формула Бержа
| Лемма: |
, где - граф с вершинами, |
| Доказательство: |
|
Удалим из графа множество , получим компонент связности, содержащих вершин соответсвенно. т. к в сумме это все вершины исходного графа . Возьмем данное равенство по модулю два: В сумме число единиц равно числу нечетных компонент . Таким образом, . |
