Участник:Masha — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Формула Бержа)
(Формула Бержа)
Строка 23: Строка 23:
 
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> и выполнен критерий Татта, значит, в графе есть совершенное паросочетание, т.е. его дефицит равен нулю.  
 
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>. В случае
+
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>. Рассмотрим случай <tex>odd(G \setminus S) = 1</tex>, <tex>|V_H| = n + k = n + odd(G \setminus A) - |A|</tex>, где <tex> A = \argmax\limits_{S \in V}(odd(G \setminus S) - |S|) </tex>. Разность <tex>odd(G \setminus A) - |A|</tex> имеет ту же четность, что и <tex>n</tex>, поэтому <tex>|V_H|</tex> четно, значит, по лемме мощность <tex>S</tex> нечетна.
 
}}
 
}}
 
  
 
==Источники информации==
 
==Источники информации==
  
 
[https://www.youtube.com/watch?v=1KggxCJZFRg {{---}} Лекция А.С. Станкевича]
 
[https://www.youtube.com/watch?v=1KggxCJZFRg {{---}} Лекция А.С. Станкевича]

Версия 14:09, 6 июня 2021

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

Лемма:
[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] и выполнен критерий Татта, значит, в графе есть совершенное паросочетание, т.е. его дефицит равен нулю.

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

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

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