49
правок
Изменения
→Формула Бержа
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>K_k</tex> соединим с каждой вершиной <tex>G</tex>. Получим новый граф <tex>H \; = \; K_k + G \;</tex>, докажем, что для него выполнено условие теоремы Татта. Докажем, что для любых <tex>\forall S \in V_{H}: odd(G H \setminus S) \; \leq \; |S| \; </tex>. Рассмотрим <tex>S \; \subset \; V_H\;</tex>.
Если <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>.
