1632
правки
Изменения
м
Отметим два неравенстваЗаметим, что множества рёбер <tex>B_i</tex> и <tex>C_j</tex>, не пересекаются, так как <tex>B_i</tex> ведут из <tex>U_i</tex> в <tex>S</tex>, а <tex>C_j</tex> ведут из <tex>U_j</tex> в <tex>U_k</tex>, (<tex>k \neq j</tex>). Так как <tex>B_i \subset F</tex> и <tex>C_j \subset F</tex>, то сумма <tex>\sum\limits_{i=1}^t |B_i| + \sum\limits_{i=1}^t |C_i| = \sum\limits_{i=1}^t \beta_i + \sum\limits_{i=1}^t \gamma_i</tex> не превосходит мощности <tex>F</tex>, откуда имеем:
Сложив которые, получаем<tex>\sum\limits_{i=1}^t \alpha_i + 3\sum\limits_{i=1}^t \beta_i + \sum\limits_{i=1}^t \gamma_i \leqslant k(|S| + 2) - 2 ~~~ \textbf{(3)}</tex>
Из неравенств Тогда <tex>\textbf{k(n - |S| - 2)}\leqslant -2</tex> и , следовательно, <tex>\textbf{k(3n - |S| - 2)}\leqslant 0</tex> <tex>k > 0</tex> получаем, что следовательно <tex>kn \leqslant k(n - |S| + 2) - 2\leqslant 0</tex>, и, следовательно, <tex>odd(G' \setminus S) = n < |S| + 2</tex>, что противоречит <tex>\textbf{(1)}</tex>. Таким образом, множество Татта найти нельзя, значит, в <tex>G'</tex> существует совершенное паросочетание.
rollbackEdits.php mass rollback
Пусть <tex>G' = G \setminus F</tex>, где <tex>F \subset E(G)</tex>, тогда <tex>|F| \leqslant k - 1</tex>
Предположим, что в <tex>G'</tex> нет [[Паросочетания: основные определения, теорема о максимальном паросочетании и дополняющих цепях#perfect_matching | совершенного паросочетания]]., тогда выберем [[Теорема Татта о существовании полного паросочетания#Tutt_set | множество Татта]] <tex>S \subset V(G')</tex>, тогда <tex>odd(G' \subset S) > |S|</tex>
Так как <tex>|V(G)|</tex> чётно, то и <tex>odd(G' \setminus S) + |S|</tex> тоже чётно. Из этого следует, что <tex>odd(G' \setminus S) \equiv |S| \pmod 2 </tex>. Из этого факта и того, что <tex>odd(G' \setminus S) > |S|</tex> следует, что <tex>odd(G' \setminus S) \geqslant |S| + 2 ~~~ \textbf{(1)}</tex>
Пусть в графе <tex>G' \setminus S</tex> всего <tex>t</tex> компонент связности, <tex>n</tex> из которых нечётны. Тогда пусть <tex>U_1, \cdotcdots, U_n</tex> {{---}} нечётные компоненты связности <tex>G' \setminus S</tex>, тогда <tex>|odd(G' \setminus S)| = n</tex>, а <tex>U_{n+1}, \cdotcdots, U_t</tex> {{---}} его чётные компоненты связности. Для каждого <tex>i \in [1 \cdots t]</tex> определим три величинымножества:
[[Файл:Плешник 1.png|300px|thumb|right|Чёрные ребра {{---}} рёбра из <tex>\alpha_iA_i</tex> , красные рёбра {{---}} количество рёбер рёбра из <tex>E(G')B_i</tex>, соединяющих синие рёбра {{---}} рёбра из <tex>U_iC_i</tex> с . Обратите внимание, что только чёрные рёбра есть в графе <tex>SG'</tex>,синие и красные {{---}} рёбра из <tex>F</tex>]]
<tex>\beta_iA_i</tex> {{---}} количество рёбер рёбра из <tex>FE(G')</tex>, соединяющих соединяющие <tex>U_i</tex> с <tex>S</tex>,<tex>\alpha_i</tex> {{---}} их количество, то есть <tex>\alpha_i = |A_i|</tex>
<tex>\gamma_iB_i</tex> {{---}} количество рёбер рёбра из <tex>E(G')F</tex>, соединяющих соединяющие <tex>U_i</tex> с остальными компонентами связности графа <tex>G' S</tex>, <tex>\setminus Sbeta_i</tex>{{---}} их количество, тогдато есть <tex>\beta_i = |B_i|</tex>
<tex>C_i</tex> {{---}} рёбра из <tex>F</tex>, соединяющие <tex>U_i</tex> с остальными компонентами связности графа <tex>G' \setminus S</tex>, <tex>\gamma_i</tex> {{---}} их количество, то есть <tex>\gamma_i = |C_i|</tex>. Тогда определим <tex>m_i := \alpha_i + \beta_i + \gamma_i</tex>. Тогда <tex>m_i</tex> {{---}} это количество рёбер графа <tex>G</tex>, соединяющих <tex>U_i</tex> с <tex>V(G) \setminus U_i</tex>.
По лемме [[Совершенное паросочетание в кубическом графе#lemma1 | о сравнимости по модулю 2]] для нечётных компонент связности <tex>G' \setminus S</tex> (то есть <tex>i \in [1 \cdots n]</tex>) <tex>m_i \equiv k \pmod 2</tex>.
<tex>m_i \geqslant \lambda(G)</tex> (так как граф потерял связность), а <tex>\lambda(G) \geqslant k - 1</tex>. Из этого факта и того, что <tex>m_i \equiv k \pmod 2</tex> следует, что <tex>m_i \geqslant k</tex>. Отсюда получаем неравенство: <tex>\sum\limits_{i=1}^n m_i = \sum\limits_{i=1}^n (\alpha_i + \beta_i + \gamma_i) = \sum\limits_{i=1}^n \alpha_i + \sum\limits_{i=1}^n \beta_i + \sum\limits_{i=1}^n \gamma_i \geqslant kn ~~~ \textbf{(2)}</tex> Заметим, что все множества рёбер <tex>A_i \subset E(G')</tex> и <tex>B_j \subset F</tex> не пересекаются(так как <tex>E(G') = E(G) \setminus F</tex>) и ведут во множество <tex>S</tex>. Поэтому сумма <tex>\sum\limits_{i=1}^t |A_i| + \sum\limits_{i=1}^t |B_i| = \sum\limits_{i=1}^t \alpha_i + \sum\limits_{i=1}^t \beta_i</tex> не превосходит суммарную степень вершин в <tex>S</tex>. Во множестве <tex>S</tex> находится всего <tex>|S|</tex> вершин, степень каждой не превосходит <tex>k</tex>. Поэтому суммарная степень вершин в <tex>S</tex> не превосходит <tex>k|S|</tex>. Отсюда получаем неравенство:
<tex>\sum\limits_1limits_{i=1}^n t \alpha_i + \sum\limits_1limits_{i=1}^n t \beta_i + \sum\limits_1^n \gamma_i \geqslant kn leqslant k|S| ~~~ \textbf{(23.1)}</tex>
<tex>2 \sum\limits_1limits_{i=1}^t \alpha_i beta_i + \sum\limits_1limits_{i=1}^t \beta_i gamma_i \leqslant 2|F| \leqslant k2k - 2 ~~~ \textbf{(3.2)}</tex> (так как <tex>|SF|\leqslant k - 1</tex>)
Сложив <tex>2 \sum\limits_1^t \beta_i + \sum\limits_1^t \gamma_i \leqslant 2|F| textbf{(3.1)}</tex> и <tex>\leqslant 2k - textbf{(3.2)}</tex>, получаем
Так как <tex>\sum\limits_1limits_{i=1}^n \alpha_i + \sum\limits_{i=1}^n \beta_i + \sum\limits_{i=1}^n \gamma_i \leqslant \sum\limits_{i=1}^t \alpha_i + \sum\limits_{i=1}^t \beta_i + \sum\limits_{i=1}^t \gamma_i \leqslant \sum\limits_{i=1}^t \alpha_i + 3\sum\limits_1limits_{i=1}^t \beta_i + \sum\limits_1limits_{i=1}^n t \gamma_i </tex> из неравенств <tex>\textbf{(2)}</tex> и <tex>\textbf{(3)}</tex> получаем <tex>kn \leqslant k(|S| + 2) - 2 ~~~ \textbf{(3)}</tex>
}}
==Следствия==
Заметим, что [[Совершенное паросочетание в кубическом графе#th1 | Теорема Петерсона]] является следствием из этой теоремы, так как в графах Петерсена <tex>k = 3</tex>, <tex>\lambda(G) \leqslant 2 = k - 1</tex>, <tex>|V| чётно</tex> чётно и <tex>|F| = 0 \leqslant k - 1</tex>
{{Утверждение
