Участник:Masha — различия между версиями
(→Формула Бержа) |
Masha (обсуждение | вклад) (→Формула Бержа) |
||
(не показаны 23 промежуточные версии этого же участника) | |||
Строка 2: | Строка 2: | ||
{{Лемма | {{Лемма | ||
− | |statement= <tex>(n + |S| + odd(G \setminus S)) \; mod \; 2 = 0</tex>, где <tex>G</tex> - граф с <tex>n</tex> вершинами, <tex>S \in {V}_{G}</tex> | + | |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= | |proof= | ||
− | Удалим из графа <tex>G</tex> множество <tex>S</tex>, получим <tex>t</tex> компонент связности, содержащих <tex>k_1, k_2 ... k_t</tex> вершин | + | Удалим из графа <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|\; + \; \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>(|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>. | + | В сумме <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>. |
}} | }} | ||
Строка 15: | Строка 15: | ||
|statement= <tex>def G = \max\limits_{S \in V} (odd(G \setminus S) - |S|)</tex> | |statement= <tex>def G = \max\limits_{S \in V} (odd(G \setminus S) - |S|)</tex> | ||
|proof= | |proof= | ||
− | <tex> \forall S \in V \; (odd(G \setminus S) + |S|) \; mod \; 2 = n \; mod \; 2</tex> | + | <tex> \forall S \in V : \; (odd(G \setminus S) + |S|) \; mod \; 2 = n \; mod \; 2</tex> |
Строка 21: | Строка 21: | ||
− | 1) Если <tex> \max\limits_{S \in V}(odd(G \setminus S) - |S|) = 0 </tex>, тогда <tex>\forall \; S \in | + | 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>. Рассмотрим <tex>S \subset V_H\;</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>. Рассмотрим <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>. | |
+ | Рассмотрим случай <tex>odd(H \setminus S) \; = \; 1 \;</tex>, <tex>|V_H| \; = \; n \; + \; k \; = \; n \; + \; odd(G \setminus A) \; - \; |A| \; </tex>, где <tex>A \; = \; arg \max\limits_{S \in V}(odd(H \setminus S) \; - \; |S|) \; </tex>. Разность <tex>odd(G \setminus A) \; - \; |A| \; </tex> имеет ту же четность, что и <tex>n</tex>, поэтому <tex>|V_H|</tex> четно, значит, по лемме, мощность <tex>S</tex> нечетна, следовательно она не равна нулю, значит <tex> 1 \leq |S| </tex>. | ||
+ | Если <tex>W \subset S \;</tex>, то <tex>odd(H \setminus S) \; = \; odd(G \setminus (S \cap V)) \; \leq \; |S \cap V| \; + \; k \leq |S| \; </tex> т.к. <tex> \max\limits_{S \in V}(odd(G \setminus S) - |S|) = k \; </tex>. | ||
− | + | Таким образом, для графа <tex>H</tex> выполнено условие Татта, следовательно в нём есть полное паросочетание. Рассмотрим полное паросочетание в графе <tex>H</tex>, удалим вершины <tex>W</tex> из графа <tex>H</tex>. Количество непокрытых вершин после удаления не больше, чем количество удаленных вершин <tex>k</tex>, значит <tex>def(G) \; \leq \; k</tex>. Удалим множество вершин <tex>A \; = \; arg \max\limits_{S \in V}(odd(H \setminus S) \; - \; |S|) \; </tex> из графа <tex>G\;</tex>. Заметим, что после удаления в графе осталось <tex>odd(G \setminus A)\; </tex> нечетных компонент и образовались новые непокрытые вершины, но при этом число нечетных компонент больше числа удаленных на <tex>k</tex>. Значит хотя бы <tex>k</tex> нечетных компонент содержали исходно непокрытую вершину, следовательно <tex>def(G) \; \geq \; k \; </tex>. | |
− | + | Из <tex>def(G) \; \leq \; k</tex> и <tex>def(G) \; \geq \; k \; </tex> следует <tex>def(G) \; = \; k \; </tex>. | |
+ | }} | ||
− | + | ==См. также== | |
− | |||
==Источники информации== | ==Источники информации== | ||
[https://www.youtube.com/watch?v=1KggxCJZFRg {{---}} Лекция А.С. Станкевича] | [https://www.youtube.com/watch?v=1KggxCJZFRg {{---}} Лекция А.С. Станкевича] |
Версия 17:17, 6 июня 2021
Формула Бержа
Лемма: |
, где - граф с вершинами, |
Доказательство: |
Удалим из графа В сумме множество , получим компонент связности, содержащих вершин соответственно. , т. к. в сумме это все вершины исходного графа . Возьмем данное равенство по модулю два: число единиц равно числу нечетных компонент . Таким образом, . |
Теорема: |
Доказательство: |
2) Если , тогда рассмотрим исходный граф и полный граф с вершинами, множество вершин нового графа обозначим как . Каждую вершину вспомогательного графа соединим с каждой вершиной . Получим новый граф , докажем, что для него выполнено условие Татта. Докажем, что . Рассмотрим .Если , тогда поскольку граф полный и все его вершины связаны с каждой вершиной графа , то граф связный и или . В случае условие очевидно выполняется т.к . Рассмотрим случай , , где . Разность имеет ту же четность, что и , поэтому четно, значит, по лемме, мощность нечетна, следовательно она не равна нулю, значит .Если , то т.к. .Таким образом, для графа Из выполнено условие Татта, следовательно в нём есть полное паросочетание. Рассмотрим полное паросочетание в графе , удалим вершины из графа . Количество непокрытых вершин после удаления не больше, чем количество удаленных вершин , значит . Удалим множество вершин из графа . Заметим, что после удаления в графе осталось нечетных компонент и образовались новые непокрытые вершины, но при этом число нечетных компонент больше числа удаленных на . Значит хотя бы нечетных компонент содержали исходно непокрытую вершину, следовательно . и следует . |