49
правок
Изменения
→Формула Бержа
{{Лемма
|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=
Удалим из графа <tex>G</tex> множество <tex>S</tex>, получим <tex>t</tex> компонент связности, содержащих <tex>k_1, k_2 ... k_t</tex> вершин соответсвенносоответственно.<tex>|S|\; + \; \sum_{i=1}^{k}k_i \; = \; n\; </tex> , т. к . в сумме это все вершины исходного графа <tex>G</tex>.
Возьмем данное равенство по модулю два: <tex>(|S|\; mod\; 2 \; + \; \sum_{i=1}^{k}(k_i \; mod \; 2)) \; mod \; 2 = n \; mod \; 2</tex>
В сумме <tex>\sum_{i=1}^{k}(k_i \; mod \; 2)</tex> число единиц равно числу нечетных компонент <tex>odd(G \setminus S)</tex>. Таким образом, <tex> \forall S \in V : \; (odd(G \setminus S) + |S|) \; mod \; 2 \; = \; n \; mod \; 2 \;</tex>.
}}
|statement= <tex>def G = \max\limits_{S \in V} (odd(G \setminus S) - |S|)</tex>
|proof=
<tex> \forall S \in V : \; (odd(G \setminus S) + |S|) \; mod \; 2 = n \; mod \; 2</tex>
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>.
Если <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>.
==Источники информации==
[https://www.youtube.com/watch?v=1KggxCJZFRg {{---}} Лекция А.С. Станкевича]