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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показано 18 промежуточных версий 2 участников)
Строка 6: Строка 6:
 
Пусть <tex>G' = G \setminus F</tex>, где <tex>F \subset E(G)</tex>, тогда <tex>|F| \leqslant k - 1</tex>
 
Пусть <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>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>|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>G' \setminus S</tex> всего <tex>t</tex> компонент связности, <tex>n</tex> из которых нечётны. Тогда пусть <tex>U_1, \cdots, U_n</tex> {{---}} нечётные компоненты связности <tex>G' \setminus S</tex>, тогда <tex>|odd(G' \setminus S)| = n</tex>, а <tex>U_{n+1}, \cdots, 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>,
+
[[Файл:Плешник 1.png|300px|thumb|right|Чёрные ребра {{---}} рёбра из <tex>A_i</tex>, красные рёбра {{---}} рёбра из <tex>B_i</tex>, синие рёбра {{---}} рёбра из <tex>C_i</tex>. Обратите внимание, что только чёрные рёбра есть в графе <tex>G'</tex>, синие и красные {{---}} рёбра из <tex>F</tex>]]
  
<tex>\beta_i</tex> {{---}} количество рёбер из <tex>F</tex>, соединяющих <tex>U_i</tex> с <tex>S</tex>,
+
<tex>A_i</tex> {{---}} рёбра из <tex>E(G')</tex>, соединяющие <tex>U_i</tex> с <tex>S</tex>, <tex>\alpha_i</tex> {{---}} их количество, то есть <tex>\alpha_i = |A_i|</tex>
  
<tex>\gamma_i</tex> {{---}} количество рёбер из <tex>E(G')</tex>, соединяющих <tex>U_i</tex> с остальными компонентами связности графа <tex>G' \setminus S</tex>, тогда
+
<tex>B_i</tex> {{---}} рёбра из <tex>F</tex>, соединяющие <tex>U_i</tex> с <tex>S</tex>, <tex>\beta_i</tex> {{---}} их количество, то есть <tex>\beta_i = |B_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>.
+
<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>.
 
По лемме [[Совершенное паросочетание в кубическом графе#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)</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_{i=1}^t \alpha_i + \sum\limits_{i=1}^t \beta_i \leqslant k|S| ~~~ \textbf{(3.1)}</tex>
 +
 
 +
Заметим, что множества рёбер <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>2 \sum\limits_{i=1}^t \beta_i + \sum\limits_{i=1}^t \gamma_i \leqslant 2|F| \leqslant 2k - 2 ~~~ \textbf{(3.2)}</tex> (так как <tex>|F| \leqslant k - 1</tex>)
 +
 
 +
Сложив <tex>\textbf{(3.1)}</tex> и <tex>\textbf{(3.2)}</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>\sum\limits_{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_{i=1}^t \beta_i + \sum\limits_{i=1}^t \gamma_i</tex> из неравенств <tex>\textbf{(2)}</tex> и <tex>\textbf{(3)}</tex> получаем <tex>kn \leqslant k(|S| + 2) - 2</tex>
 +
 
 +
Тогда <tex>k(n - |S| - 2) \leqslant -2</tex>, следовательно, <tex>k(n - |S| - 2) \leqslant 0</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>k > 0</tex>, следовательно <tex>n - |S| - 2 \leqslant 0</tex>
  
Отметим два неравенства:
+
и, следовательно, <tex>odd(G' \setminus S) = n < |S| + 2</tex>, что противоречит <tex>\textbf{(1)}</tex>. Таким образом, множество Татта найти нельзя, значит, в <tex>G'</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>
+
Заметим, что [[Совершенное паросочетание в кубическом графе#th1 | Теорема Петерсона]] является следствием из этой теоремы, так как в графах Петерсена <tex>k = 3</tex>, <tex>\lambda(G) \leqslant 2 = k - 1</tex>, <tex>|V|</tex> чётно и <tex>|F| = 0 \leqslant k - 1</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> существует совершенное паросочетание.
+
{{Утверждение
 +
|id = statement2
 +
|statement = Пусть <tex>G</tex> {{---}} <tex>k</tex>-[[Основные определения теории графов#defRegularGraph |регулярный граф]], с чётным числом вершин, причём <tex>\lambda(G) \geqslant k - 1</tex>. Тогда для любого ребра <tex>e \in E(G)</tex> существует совершенное паросочетание графа <tex>G</tex>, содержащее <tex>e</tex>.
 +
|proof =
 +
Пусть <tex>e = uv</tex>, а <tex>e_1 \cdots e_{k-1}</tex> {{---}} остальные рёбра, инцидентные вершине <tex>u</tex>. Согласно теореме, в графе <tex>G \setminus \{ e_1 \cdots e_{k-1} \}</tex> есть совершенное паросочетание <tex>M</tex>. Так как <tex>u</tex> покрывается <tex>M</tex>, а <tex>e</tex> {{---}} единственное ребро <tex>G \setminus \{ e_1 \cdots e_{k-1} \}</tex>, инцидентное <tex>u</tex>, <tex>u \in M</tex>
 
}}
 
}}
  

Текущая версия на 19:17, 4 сентября 2022

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

Чёрные ребра — рёбра из [math]A_i[/math], красные рёбра — рёбра из [math]B_i[/math], синие рёбра — рёбра из [math]C_i[/math]. Обратите внимание, что только чёрные рёбра есть в графе [math]G'[/math], синие и красные — рёбра из [math]F[/math]

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

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

[math]C_i[/math] — рёбра из [math]F[/math], соединяющие [math]U_i[/math] с остальными компонентами связности графа [math]G' \setminus S[/math], [math]\gamma_i[/math] — их количество, то есть [math]\gamma_i = |C_i|[/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)[/math] (так как граф потерял связность), а [math]\lambda(G) \geqslant k - 1[/math]. Из этого факта и того, что [math]m_i \equiv k \pmod 2[/math] следует, что [math]m_i \geqslant k[/math]. Отсюда получаем неравенство:

[math]\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)}[/math]

Заметим, что все множества рёбер [math]A_i \subset E(G')[/math] и [math]B_j \subset F[/math] не пересекаются(так как [math]E(G') = E(G) \setminus F[/math]) и ведут во множество [math]S[/math]. Поэтому сумма [math]\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[/math] не превосходит суммарную степень вершин в [math]S[/math]. Во множестве [math]S[/math] находится всего [math]|S|[/math] вершин, степень каждой не превосходит [math]k[/math]. Поэтому суммарная степень вершин в [math]S[/math] не превосходит [math]k|S|[/math]. Отсюда получаем неравенство:

[math]\sum\limits_{i=1}^t \alpha_i + \sum\limits_{i=1}^t \beta_i \leqslant k|S| ~~~ \textbf{(3.1)}[/math]

Заметим, что множества рёбер [math]B_i[/math] и [math]C_j[/math], не пересекаются, так как [math]B_i[/math] ведут из [math]U_i[/math] в [math]S[/math], а [math]C_j[/math] ведут из [math]U_j[/math] в [math]U_k[/math], ([math]k \neq j[/math]). Так как [math]B_i \subset F[/math] и [math]C_j \subset F[/math], то сумма [math]\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[/math] не превосходит мощности [math]F[/math], откуда имеем:

[math]2 \sum\limits_{i=1}^t \beta_i + \sum\limits_{i=1}^t \gamma_i \leqslant 2|F| \leqslant 2k - 2 ~~~ \textbf{(3.2)}[/math] (так как [math]|F| \leqslant k - 1[/math])

Сложив [math]\textbf{(3.1)}[/math] и [math]\textbf{(3.2)}[/math], получаем

[math]\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)}[/math]

Так как [math]\sum\limits_{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_{i=1}^t \beta_i + \sum\limits_{i=1}^t \gamma_i[/math] из неравенств [math]\textbf{(2)}[/math] и [math]\textbf{(3)}[/math] получаем [math]kn \leqslant k(|S| + 2) - 2[/math]

Тогда [math]k(n - |S| - 2) \leqslant -2[/math], следовательно, [math]k(n - |S| - 2) \leqslant 0[/math]

[math]k \gt 0[/math], следовательно [math]n - |S| - 2 \leqslant 0[/math]

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

Следствия

Заметим, что Теорема Петерсона является следствием из этой теоремы, так как в графах Петерсена [math]k = 3[/math], [math]\lambda(G) \leqslant 2 = k - 1[/math], [math]|V|[/math] чётно и [math]|F| = 0 \leqslant k - 1[/math]


Утверждение:
Пусть [math]G[/math][math]k[/math]-регулярный граф, с чётным числом вершин, причём [math]\lambda(G) \geqslant k - 1[/math]. Тогда для любого ребра [math]e \in E(G)[/math] существует совершенное паросочетание графа [math]G[/math], содержащее [math]e[/math].
[math]\triangleright[/math]
Пусть [math]e = uv[/math], а [math]e_1 \cdots e_{k-1}[/math] — остальные рёбра, инцидентные вершине [math]u[/math]. Согласно теореме, в графе [math]G \setminus \{ e_1 \cdots e_{k-1} \}[/math] есть совершенное паросочетание [math]M[/math]. Так как [math]u[/math] покрывается [math]M[/math], а [math]e[/math] — единственное ребро [math]G \setminus \{ e_1 \cdots e_{k-1} \}[/math], инцидентное [math]u[/math], [math]u \in M[/math]
[math]\triangleleft[/math]

См. также

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

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