Участник:Masha

Материал из Викиконспекты
Версия от 13:12, 3 июня 2021; Masha (обсуждение | вклад) (Формула Бержа)
Перейти к: навигация, поиск

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

Лемма:
[math](n + |S| + odd(G \setminus S)) \; mod \; 2 = 0[/math], где [math]G[/math] - граф с [math]n[/math] вершинами, [math]S \in {V}_{G}[/math]
Доказательство:
[math]\triangleright[/math]

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

В сумме [math]\sum_{i=1}^{k}(k_i \; mod \; 2)[/math] число единиц равно числу нечетных компонент [math]odd(G \setminus S)[/math]. Таким образом, [math] \forall S \in V \; (odd(G \setminus S) + |S|) \; mod \; 2 = n \; mod \; 2 [/math].
[math]\triangleleft[/math]


Теорема:
[math]def G = \max\limits_{S \in V} (odd(G \setminus S) - |S|)[/math]
Доказательство:
[math]\triangleright[/math]

[math] \forall S \in V \; (odd(G \setminus S) + |S|) \; mod \; 2 = n \; mod \; 2 [/math] Рассмотрим несколько случаев:

1) Если [math] \max\limits_{S \in V}(odd(G \setminus S) - |S|) = 0 [/math], тогда [math]\forall \; S \in \; V: \; odd(G \setminus S) \leq |S| \; [/math] и выполнен критерий Татта, значит, в графе есть совершенное паросочетание, т.е. его дефицит равен нулю.
[math]\triangleleft[/math]