| ... | ... | @@ -36,7 +36,7 @@ $`\Rightarrow o(G^* - S) \leq o(G-S) \leq |S|`$ |
|
|
|
|
|
|
|
Пусть есть ещё вершина w. Пусть она не соединена с y. Такая найдётся, т.к. мы выкинули все вершины, которые соединены со всеми остальными.
|
|
|
|
|
|
|
|
<img src="uploads/a2b8dbeb0cc866c947877847019d8212/tatt-theorem-3.png" width="50%" height="50%">
|
|
|
|
<img src="uploads/a2b8dbeb0cc866c947877847019d8212/tatt-theorem-3.png" width="30%" height="30%">
|
|
|
|
|
|
|
|
Вспомним, что при добавлении $`∀`$ ребра в $`G^*`$ появляется совершенное паросочетание.
|
|
|
|
Пусть тогда:
|
| ... | ... | @@ -57,9 +57,13 @@ $`M_2`$ -- совершенное паросочетание на $`G^* + yw`$ |
|
|
|
1) Если они попали в разные циклы:
|
|
|
|
Тогда в каждом цикле возьмём рёбра цвета противоположного zx и yw соответственно. В остальных циклах возьмём любой цвет -- получится совершенное паросочетание в графе $`G^*`$. Противоречие.
|
|
|
|
2) Если они попали в один цикл:
|
|
|
|
Противоречие.
|
|
|
|
Тогда в "ушках", которые обозначены на картинке будет чётное число рёбер, потому что H -- объединение чётных циклов. при этом там будет существовать путь $`P = xCyzCw`$ через весь цикл. А поскольку в этом пути чётное число рёбер можно выбрать паросочетание покрывающее весь этот цикл. В остальных циклах можно выбрать любое из паросочетаний $`M_1`$ и $`M_2`$ и у нас получится совершенное паросочетание на графе $`G^*`$, возникает противоречие.
|
|
|
|
|
|
|
|
В обоих случаях мы получили противоречие => лемма доказана, потому что мы доказывали от противного.
|
|
|
|
В обоих случаях мы получили противоречие $`\Rightarrow`$ лемма доказана, потому что мы доказывали от противного.
|
|
|
|
|
|
|
|
**Продолжим доказательство теоремы Татта:**
|
|
|
|
|
|
|
|
|
|
|
|
<img src="uploads/c21acaf3b41d4dcd3a37b1883b7d4d8b/tatt-theorem-7.png" width="100%" height="100%">
|
|
|
|
|
|
|
|
Из леммы мы получаем, что $`G^* - U`$ -- объединение несвязных полных графов.
|
|
|
|
Эти графы снова могут быть чётными и нечётными компонентами. Нечётных полных графов $`\leq |U|`$ т.к. $`G^*`$ -- чётный. Во всех чётных компонентах можно выделить паросочетание покрывающее все вершины компоненты (потому что компоненты -- полные графы). В нечётных одну не покрытую паросочетанием вершину соединим с U (там все вершины соединены со всеми остальными, и их $`o(G*-U) \leg |U|`$ значит такое ребро есть и его можно взять в паросочетание). Не покрытые вершины в U можно соединить друг с другом и тоже взять в паросочетание. Значит мы сможем покрыть все вершины паросочетанием и получить совершенное паросочетание. А значит у нас есть противоречие с тем, что мы брали $`G^*`$ -- как надграф G без совершенного паросочетания -- такого графа не существует. Значит и в исходном G есть совершенное паросочетание. Значит теорема доказана. |
