137
правок
Изменения
Новая страница: «{{Теорема |id = th_main. |author = J. Plesnik, 1972 |statement = Пусть <tex>G</tex> {{---}} <tex>k</tex>-[[Основные определения т...»
{{Теорема
|id = th_main.
|author = J. Plesnik, 1972
|statement = Пусть <tex>G</tex> {{---}} <tex>k</tex>-[[Основные определения теории графов#defRegularGraph |регулярный граф]], с чётным числом вершин, причём <tex>\lambda(G) \geqslant k - 1</tex>, а граф <tex>G'</tex> получен из <tex>G</tex> удалением не более <tex>k - 1</tex> рёбер. Тогда в графе <tex>G'</tex> есть совершенное паросочетание.
|proof =
Пусть <tex>G' = G \setminus F</tex>, где <tex>F \subset E(G)</tex>, тогда <tex>|F| \leqslant k - 1</tex>
Предположим, что в <tex>G'</tex> нет совершенного паросочетания, тогда выберем [[Теорема Татта о существовании полного паросочетания#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</tex>
Пусть <tex>U_1, \cdot, U_n</tex> {{---}} нечётные компоненты связности <tex>G' \setminus S</tex>, тогда <tex>|odd(G' \setminus S)| = n</tex>, а <tex>U_{n+1}, \cdot, U_t</tex> {{---}} его чётные компоненты связности. Для каждого <tex>i \in [1 \cdots t]</tex> определим три величины:
<tex>\alpha_i</tex> {{---}} количество рёбер из <tex>E(G')</tex>, соединяющих <tex>U_i</tex> с <tex>S</tex>,
<tex>\beta_i</tex> {{---}} количество рёбер из <tex>F</tex>, соединяющих <tex>U_i</tex> с <tex>S</tex>,
<tex>\gamma_i</tex> {{---}} количество рёбер из <tex>E(G')</tex>, соединяющих <tex>U_i</tex> с остальными компонентами связности графа <tex>G' \setminus S</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) \geqslant k - 1</tex>. Из этого факта и того, что <tex>m_i \equiv k \pmod 2</tex> следует, что <tex>m_i \geqslant k</tex>. Отсюда получаем неравенство
}}
|id = th_main.
|author = J. Plesnik, 1972
|statement = Пусть <tex>G</tex> {{---}} <tex>k</tex>-[[Основные определения теории графов#defRegularGraph |регулярный граф]], с чётным числом вершин, причём <tex>\lambda(G) \geqslant k - 1</tex>, а граф <tex>G'</tex> получен из <tex>G</tex> удалением не более <tex>k - 1</tex> рёбер. Тогда в графе <tex>G'</tex> есть совершенное паросочетание.
|proof =
Пусть <tex>G' = G \setminus F</tex>, где <tex>F \subset E(G)</tex>, тогда <tex>|F| \leqslant k - 1</tex>
Предположим, что в <tex>G'</tex> нет совершенного паросочетания, тогда выберем [[Теорема Татта о существовании полного паросочетания#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</tex>
Пусть <tex>U_1, \cdot, U_n</tex> {{---}} нечётные компоненты связности <tex>G' \setminus S</tex>, тогда <tex>|odd(G' \setminus S)| = n</tex>, а <tex>U_{n+1}, \cdot, U_t</tex> {{---}} его чётные компоненты связности. Для каждого <tex>i \in [1 \cdots t]</tex> определим три величины:
<tex>\alpha_i</tex> {{---}} количество рёбер из <tex>E(G')</tex>, соединяющих <tex>U_i</tex> с <tex>S</tex>,
<tex>\beta_i</tex> {{---}} количество рёбер из <tex>F</tex>, соединяющих <tex>U_i</tex> с <tex>S</tex>,
<tex>\gamma_i</tex> {{---}} количество рёбер из <tex>E(G')</tex>, соединяющих <tex>U_i</tex> с остальными компонентами связности графа <tex>G' \setminus S</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) \geqslant k - 1</tex>. Из этого факта и того, что <tex>m_i \equiv k \pmod 2</tex> следует, что <tex>m_i \geqslant k</tex>. Отсюда получаем неравенство
}}
