Изменения

Перейти к: навигация, поиск

Участник:Masha

861 байт добавлено, 6 июнь
Формула Бержа
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>. Рассмотрим S \from V_H. Если в не <tex>W \in S</tex>, тогда посколько граф <tex>K_k</tex> полный, и все его вершины связаны с каждой вершиной графа <tex>G</tex>, то граф <tex>H</tex> связный и <tex>odd(G \setminus S) = 0</tex> или <tex>odd(G \setminus S) = 1</tex>. В случае <tex>odd(G \setminus S) = 0</tex> условие очевидно выполняется т.к <tex>\forall S \in G : 0 \; \leq \; |S|</tex>. В случае
}}
 
 
==Источники информации==
 
[https://www.youtube.com/watch?v=1KggxCJZFRg {{---}} Лекция А.С. Станкевича]
Анонимный участник

Навигация