GitLab

Теорема Татта о совершенном паросочетании

В графе 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|.

(\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|

Если вершина 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. Такая найдётся, т.к. мы выкинули все вершины, которые соединены со всеми остальными.

Вспомним, что при добавлении ∀ ребра в 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.

Понятно, что наши рёбра zx и yw тоже попали в H. Потому что они были в M_1 и M_2 и не могли пропасть, потому что каждое было только в одном паросочетании. Но они могли попасть либо, в один либо в разные циклы. (См картинку)

1. Если они попали в разные циклы: Тогда в каждом цикле возьмём рёбра цвета противоположного zx и yw соответственно. В остальных циклах возьмём любой цвет -- получится совершенное паросочетание в графе G^*. Противоречие.
2. Если они попали в один цикл: Противоречие.

В обоих случаях мы получили противоречие => лемма доказана, потому что мы доказывали от противного.