Участник:Masha

Формула Бержа

Лемма:

$(n + |S| + odd(G \setminus S)) \; mod \; 2 = 0$, где $G$ - граф с $n$ вершинами, $S \in {V}_{G}$

Доказательство:

$\triangleright$

Удалим из графа $G$ множество $S$, получим $t$ компонент связности, содержащих $k_1, k_2 ... k_t$ вершин соответсвенно. $|S|\; + \; \sum_{i=1}^{k}k_i = n$ т. к в сумме это все вершины исходного графа $G$. Возьмем данное равенство по модулю два: $(|S|\; mod\; 2 \; + \; \sum_{i=1}^{k}(k_i \; mod \; 2)) \; mod \; 2 = n \; mod \; 2$ В сумме $\sum_{i=1}^{k}(k_i \; mod \; 2)$ число единиц равно числу нечетных компонент $odd(G \setminus S)$. Таким образом, $\forall S \in V \; (odd(G \setminus S) + |S|) \; mod \; 2 = n \; mod \; 2$.

$\triangleleft$

Теорема:

$def G = \max\limits_{S \in V} (odd(G \setminus S) - |S|)$

Доказательство:

$\triangleright$

$\forall S \in V \; (odd(G \setminus S) + |S|) \; mod \; 2 = n \; mod \; 2$ Рассмотрим несколько случаев: 1) Если $\max\limits_{S \in V}(odd(G \setminus S) - |S|) = 0$, тогда $\forall \; S \in \; V: \; odd(G \setminus S) \leq |S| \;$ и выполнен критерий Татта, значит, в графе есть совершенное паросочетание, т.е. его дефицит равен нулю. 2) Если $\max\limits_{S \in V}(odd(G \setminus S) - |S|) = k$, тогда рассмотрим исходный граф $G$ и полный граф $K_k$ с $k$ вершинами, множество вершин нового графа обозначим как $W$. Каждую вершину вспомогательного графа соединим с каждой вершиной $G$. Получим новый граф $H \; = \; K_k + G$, докажем, что для него выполнено условие Татта. Докажем, что $\forall S \in V_{H}: odd(G \setminus S) -leq |S|$. Рассмотрим S \from V_H. Если не $W \subset S$, тогда посколько граф $K_k$ полный, и все его вершины связаны с каждой вершиной графа $G$, то граф $H$ связный и $odd(H \setminus S) = 0$ или $odd(G \setminus S) = 1$. В случае $odd(H \setminus S) = 0$ условие очевидно выполняется т.к $\forall S \in G : 0 \; \leq \; |S|$. Рассмотрим случай $odd(H \setminus S) = 1$, $|V_H| = n + k = n + odd(G \setminus A) - |A|$, где $A = arg \max\limits_{S \in V}(odd(H \setminus S) - |S|)$. Разность $odd(G \setminus A) - |A|$ имеет ту же четность, что и $n$, поэтому $|V_H|$ четно, значит, по лемме мощность $S$ нечетна, следовательно, она не равна нулю, значит $1 \leq |S|$. Если $W \subset S$, то $odd(H \setminus S) = odd(G \setminus (S \cap V)) \leq |S \cap V| + k \leq |S|$. Таким образом, для графа $H$ выполнено условие Татта, следовательно, в нём есть полное паросочетание. Рассмотрим полное паросочетание в графе $H$, удалим вершины $W$ из графа $H$. Количество непокрытых вершин после удаления не больше, чем количество удаленных вершин $k$, значит, $def(G) \leq k$. Удалим множество вершин $A = arg \max\limits_{S \in V}(odd(H \setminus S) - |S|)$ из графа $G$. Заметим, что после удаление в графе осталось несколько нечетных компонент и образовались новые непокрытые вершины, но при этом осталось на k больше нечетных компонент, чем мы удалили, значит, хотя бы k нечетных компонент содержали исходно непокрытую вершину, значит, $k \leq def(G)$. Значит, $def(G) = k$. Теорема доказана.

$\triangleleft$

Источники информации

— Лекция А.С. Станкевича