Участник:Masha — различия между версиями
Masha (обсуждение | вклад) (→Алгоритм декодирования кодa Прюфера) |
Masha (обсуждение | вклад) (→Формула Бержа) (Метки: правка с мобильного устройства, правка из мобильной версии) |
||
(не показано 7 промежуточных версий этого же участника) | |||
Строка 1: | Строка 1: | ||
− | == | + | == Формула Бержа == |
− | + | {{Лемма | |
+ | |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>G</tex>. Получим новый граф <tex>H \; = \; K_k + G</tex>, докажем, что для него выполнено условие Татта. | ||
+ | }} |
Версия 13:20, 3 июня 2021
Формула Бержа
Лемма: |
, где - граф с вершинами, |
Доказательство: |
Удалим из графа В сумме множество , получим компонент связности, содержащих вершин соответсвенно. т. к в сумме это все вершины исходного графа . Возьмем данное равенство по модулю два: число единиц равно числу нечетных компонент . Таким образом, . |
Теорема: |
Доказательство: |
|