|
|
Теорема Татта о совершенном паросочетании
|
|
|
-------------------------------------------
|
|
|
|
|
|
**_В графе G есть совершенное паросочетание $`\Leftrightarrow ∀S \in V(G) o(G-S) ≥ |S|`$_**
|
|
|
|
|
|
Здесь, как _o(G)_ обозначается _количество нечётных компонент связности графа, причём нечётной компонентой называется компонента, в которой нечётное число._ (А чётной компонентой, соответственно будет компонента связности, где чётное количество вершин.)
|
|
|
|
|
|
Доказательство:
|
|
|
|
|
|
($`\Rightarrow `$)
|
|
|
Докажем, что если в графе есть совершенное паросочетание выполняется условие: $`\Leftrightarrow ∀S \in V(G) o(G-S) ≥ |S|`$.
|
|
|
|
|
|
Заметим, что без S граф G разваливается на чётные и нечётные компоненты связности. Нечётные компоненты нельзя покрыть паросочетанием (потому что нечётное число нельзя разбить на пары), а совершенное паросочетание у нас всё таки есть, значит из каждой нечётной компоненты шло хотя бы одно ребро в вершины из S (это ребро мы и брали в паросочетание). Но тогда вершин в S не меньше, чем нечётных компонент связности в G-S. Т.е. $`o(G-S) ≥ |S|`$.
|
|
|
|
|
|
<img src="uploads/c9063e14dbd3267402ab9feb60147c7a/tatt-theorem-1.png" width="80%" height="80%">
|
|
|
|
|
|
($`\Leftarrow`$)
|
|
|
Докажем, что если выполняется условие: $`\Leftrightarrow ∀S \in V(G) o(G-S) ≥ |S|`$, в в графе есть совершенное паросочетание.
|
|
|
|
|
|
_Предположим_ что в графе G выполняется условие, но _совершенного паросочетания нет_.
|
|
|
Построим надграф G - $`G^*`$ такой, что при добавлении любого ребра в $`G^*`$ появится совершенное паросочетание. (НО в $`G^*`$ совершенного паросочетания нет! Т.е. полным $`G^*`$ быть тоже не может)
|
|
|
|
|
|
Понятно, что в G должно быть чётное число вершин, потому что иначе найдётся нечётная компонента связности и условие Татта для неё не выполнится, ведь если взять $`S = \emptyset`$, тогда $`o(G) ≥ 1`$ (у нас есть минимум одна нечётная компонента). В итоге: $`|S| = 0 < 1 \leq o(G)`$
|
|
|
|
|
|
Заметим, что добавление рёбер между компонентами в $`G^*`$ не меняет количества нечётных компонент (см картинку). Рёбра внутри компонент нас не особо волнуют.
|
|
|
|
|
|
$`\Rightarrow o(G^* - S) \leq o(G-S) \leq |S|`$
|
|
|
|
|
|
<img src="uploads/08c32ab06b1c05107e6008c087fca8b2/tatt-theorem-2.png" width="100%" height="100%">
|
|
|
|
|
|
Если вершина v соединена со всеми остальными вершинами, её степень $`d_G(v) = v(G) - 1`$. Поскольку $`G^*`$ -- не полный, то множество U вершин соседних со всеми остальными не совпадает с V(G). $`|U| \neq v(G^*)`$
|
|
|
|
|
|
**Докажем лемму -- _($`G^* - U`$ -- объединение полных графов не связанных между собой)_**
|
|
|
|
|
|
Будем доказывать от противного. Тогда в графе $`G^* - U`$ есть вершины x, y, z -- которые образуют галочку (см картинку). Т.е. в графе есть рёбра xy, yz, а xz -- нет. Такая галочка найдётся, потому что иначе мы получим треугольник -- это полный граф на 3х вершинах, а мы предположили, что таких нет.
|
|
|
|
|
|
Пусть есть ещё вершина w. Пусть она не соединена с y. Такая найдётся, т.к. мы выкинули все вершины, которые соединены со всеми остальными.
|
|
|
|
|
|
<img src="uploads/a2b8dbeb0cc866c947877847019d8212/tatt-theorem-3.png" width="50%" height="50%">
|
|
|
|
|
|
Вспомним, что при добавлении $`∀`$ ребра в $`G^*`$ появляется совершенное паросочетание.
|
|
|
Пусть тогда:
|
|
|
$`M_1`$ -- совершенное паросочетание на $`G^* + xz`$
|
|
|
$`M_2`$ -- совершенное паросочетание на $`G^* + yw`$
|
|
|
|
|
|
Т.к. до добавления этих рёбер совершенных паросочетаний не было -- добавленные рёбра входят в соответствующие паросочетания. $`xz \in M_1, yw \in M_2`$
|
|
|
|
|
|
Тогда пусть H -- объединение $`M_1`$ и $`M_2`$. Т.е. $`H = M_1 \Delta M_2`$.
|
|
|
Т.к. $`M_1`$ и $`M_2`$ -- совершенные паросочетания H -- объединение чётных циклов, в которых чередуются рёбра из $`M_1`$ и $`M_2`$.
|
|
|
|
|
|
<img src="uploads/619058b50bee0e8759281e4f1dec2e61/tatt-theorem-4.png" width="50%" height="50%">
|
|
|
|
|
|
Понятно, что наши рёбра zx и yw тоже попали в H. Потому что они были в $`M_1`$ и $`M_2`$ и не могли пропасть, потому что каждое было только в одном паросочетании. Но они могли попасть либо, в один либо в разные циклы. (См картинку)
|
|
|
|
|
|
<img src="uploads/dca43c9871081e8a8dce33aeb4a4eaf1/tatt-theorem-5.png" width="100%" height="100%">
|
|
|
|
|
|
1) Если они попали в разные циклы:
|
|
|
Тогда в каждом цикле возьмём рёбра цвета противоположного zx и yw соответственно. В остальных циклах возьмём любой цвет -- получится совершенное паросочетание в графе $`G^*`$. Противоречие.
|
|
|
2) Если они попали в один цикл:
|
|
|
Противоречие.
|
|
|
|
|
|
В обоих случаях мы получили противоречие => лемма доказана, потому что мы доказывали от противного.
|
|
|
|
|
|
|
|
|
|