Теорема о существовании совершенного паросочетания в графе, полученном из регулярного удалением ребёр — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «{{Теорема |id = th_main. |author = J. Plesnik, 1972 |statement = Пусть <tex>G</tex> {{---}} <tex>k</tex>-[[Основные определения т...»)
 
Строка 8: Строка 8:
 
Предположим, что в <tex>G'</tex> нет совершенного паросочетания, тогда выберем [[Теорема Татта о существовании полного паросочетания#Tutt_set | множество Татта]] <tex>S \subset V(G')</tex>, тогда <tex>odd(G' \subset S) > |S|</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>|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>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>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> определим три величины:
Строка 22: Строка 22:
 
По лемме [[Совершенное паросочетание в кубическом графе#lemma1 | о сравнимости по модулю 2]] для нечётных компонент связности <tex>G' \setminus S</tex> (то есть <tex>i \in [1 \cdots n]</tex>) <tex>m_i \equiv k \pmod 2</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>. Отсюда получаем неравенство
+
<tex>m_i \geqslant \lambda(G) \geqslant k - 1</tex>. Из этого факта и того, что <tex>m_i \equiv k \pmod 2</tex> следует, что <tex>m_i \geqslant k</tex>. Отсюда получаем неравенство:
 +
 
 +
<tex>\sum\limits_1^n \alpha_i + \sum\limits_1^n \beta_i + \sum\limits_1^n \gamma_i \geqslant kn ~~~ \textbf{(2)}</tex>
 +
 
 +
Отметим два неравенства:
 +
 
 +
<tex>\sum\limits_1^t \alpha_i + \sum\limits_1^t \beta_i \leqslant k|S|</tex>
 +
 
 +
<tex>2 \sum\limits_1^t \beta_i + \sum\limits_1^t \gamma_i \leqslant 2|F| \leqslant 2k - 2</tex>
 +
 
 +
Сложив которые, получаем
 +
 
 +
<tex>\sum\limits_1^t \alpha_i + 3\sum\limits_1^t \beta_i + \sum\limits_1^n \gamma_i \leqslant k(|S| + 2) - 2 ~~~ \textbf{(3)}</tex>
 +
 
 +
Из неравенств <tex>\textbf{(2)}</tex> и <tex>\textbf{(3)}</tex> получаем, что <tex>kn \leqslant k(|S| + 2) - 2</tex>, и, следовательно, <tex>odd(G' \setminus S) = n < |S| + 2</tex>, что противоречит <tex>\textbf{(1)}</tex>. Таким образом, множество Татта найти нельзя, значит, в <tex>G'</tex> существует совершенное паросочетание.
 
}}
 
}}
 +
 +
==См. также==
 +
* [[Совершенное паросочетание в кубическом графе]]
 +
 +
==Источники информации==
 +
* Карпов В. Д. - Теория графов, стр 43
 +
 +
[[Категория: Алгоритмы и структуры данных]]
 +
[[Категория: Задача о паросочетании]]

Версия 14:26, 19 ноября 2017

Теорема (J. Plesnik, 1972):
Пусть [math]G[/math][math]k[/math]-регулярный граф, с чётным числом вершин, причём [math]\lambda(G) \geqslant k - 1[/math], а граф [math]G'[/math] получен из [math]G[/math] удалением не более [math]k - 1[/math] рёбер. Тогда в графе [math]G'[/math] есть совершенное паросочетание.
Доказательство:
[math]\triangleright[/math]

Пусть [math]G' = G \setminus F[/math], где [math]F \subset E(G)[/math], тогда [math]|F| \leqslant k - 1[/math]

Предположим, что в [math]G'[/math] нет совершенного паросочетания, тогда выберем множество Татта [math]S \subset V(G')[/math], тогда [math]odd(G' \subset S) \gt |S|[/math]

Так как [math]|V(G)|[/math] чётно, то и [math]odd(G' \setminus S) + |S|[/math] тоже чётно. Из этого следует, что [math]odd(G' \setminus S) \equiv |S| \pmod 2 [/math]. Из этого факта и того, что [math]odd(G' \setminus S) \gt |S|[/math] следует, что [math]odd(G' \setminus S) \geqslant |S| + 2 ~~~ \textbf{(1)}[/math]

Пусть [math]U_1, \cdot, U_n[/math] — нечётные компоненты связности [math]G' \setminus S[/math], тогда [math]|odd(G' \setminus S)| = n[/math], а [math]U_{n+1}, \cdot, U_t[/math] — его чётные компоненты связности. Для каждого [math]i \in [1 \cdots t][/math] определим три величины:

[math]\alpha_i[/math] — количество рёбер из [math]E(G')[/math], соединяющих [math]U_i[/math] с [math]S[/math],

[math]\beta_i[/math] — количество рёбер из [math]F[/math], соединяющих [math]U_i[/math] с [math]S[/math],

[math]\gamma_i[/math] — количество рёбер из [math]E(G')[/math], соединяющих [math]U_i[/math] с остальными компонентами связности графа [math]G' \setminus S[/math], тогда

[math]m_i := \alpha_i + \beta_i + \gamma_i[/math]. Тогда [math]m_i[/math] — это количество рёбер графа [math]G[/math], соединяющих [math]U_i[/math] с [math]V(G) \setminus U_i[/math].

По лемме о сравнимости по модулю 2 для нечётных компонент связности [math]G' \setminus S[/math] (то есть [math]i \in [1 \cdots n][/math]) [math]m_i \equiv k \pmod 2[/math].

[math]m_i \geqslant \lambda(G) \geqslant k - 1[/math]. Из этого факта и того, что [math]m_i \equiv k \pmod 2[/math] следует, что [math]m_i \geqslant k[/math]. Отсюда получаем неравенство:

[math]\sum\limits_1^n \alpha_i + \sum\limits_1^n \beta_i + \sum\limits_1^n \gamma_i \geqslant kn ~~~ \textbf{(2)}[/math]

Отметим два неравенства:

[math]\sum\limits_1^t \alpha_i + \sum\limits_1^t \beta_i \leqslant k|S|[/math]

[math]2 \sum\limits_1^t \beta_i + \sum\limits_1^t \gamma_i \leqslant 2|F| \leqslant 2k - 2[/math]

Сложив которые, получаем

[math]\sum\limits_1^t \alpha_i + 3\sum\limits_1^t \beta_i + \sum\limits_1^n \gamma_i \leqslant k(|S| + 2) - 2 ~~~ \textbf{(3)}[/math]

Из неравенств [math]\textbf{(2)}[/math] и [math]\textbf{(3)}[/math] получаем, что [math]kn \leqslant k(|S| + 2) - 2[/math], и, следовательно, [math]odd(G' \setminus S) = n \lt |S| + 2[/math], что противоречит [math]\textbf{(1)}[/math]. Таким образом, множество Татта найти нельзя, значит, в [math]G'[/math] существует совершенное паросочетание.
[math]\triangleleft[/math]

См. также

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

  • Карпов В. Д. - Теория графов, стр 43