Совершенное паросочетание в кубическом графе

Лемма о сравнимости по модулю 2

Лемма:

Пусть [math]G[/math] — [math]k[/math]- регулярный граф, [math]U \in V(G)[/math], [math]|U|[/math] нечётно, [math]m[/math]—число рёбер, соединяющих вершины множества [math]U[/math] с вершинами из [math]V(G) \setminus U[/math]. Тогда [math]m \equiv k \pmod 2[/math]

Доказательство:

[math]\triangleright[/math]

[math]m = (\sum\limits_{v \in U} d_G(v)) - 2e(G(U))[/math], где [math]e(G(U))[/math] - количество рёбер, соединяющих вершину из [math]U[/math] с другой вершиной из [math]U[/math]. тогда [math]m = k|U| - 2e(G(U))[/math]. [math]2e(G(U))[/math] чётно, поэтому [math]m \equiv k|U| \pmod 2[/math]. Так как [math] |U|[/math] нечётно, [math]m \equiv k \pmod 2[/math], что и требовалось доказать.

[math]\triangleleft[/math]

Теорема Петерсона (Petersen)

Определение:

Кубический граф (англ. Cubic graph) — граф, в котором все вершины имеют степень три. Другими словами, кубический граф является [math]3[/math]-регулярным.

Теорема (Петерсон):

Пусть [math]G[/math]— связный кубический граф, в котором не более [math]3[/math] мостов. Тогда в [math]G[/math] есть совершенное паросочетание.

Доказательство:

[math]\triangleright[/math]

Предположим, что совершенного паросочетания в [math]G[/math] нет, тогда можно выбрать множество Татта [math]S \subset V(G)[/math]. Пусть [math]U_1, \ldots, U_n[/math]—все нечётные компоненты связности графа [math]G \setminus S[/math]. [math]m_i[/math]—количество ребёр [math]G[/math], связывающих вершины [math]U_i[/math] с вершинами [math]S[/math]. По предыдущей лемме, все [math]m_i[/math] нечётны. Так как не более чем два ребра графа [math]G[/math]—мосты, то не более, чем два числа из [math]m_1, \ldots, m_n[/math] равны [math]1[/math], остальные числа не менее [math]3[/math]. Так как [math]S[/math]—множество Татта, то [math]odd(G \setminus S) \gt |S|[/math]. Так как количество вершин кубического графа [math]G[/math] чётно, мы имеем [math]S \neq \emptyset, odd(G \setminus S) \equiv S \pmod 2[/math], следовательно, [math]n = odd(G \setminus S) \geqslant |S| + 2[/math]. Тогда [math]\sum\limits_{v \in S} d_G(v) \geqslant \sum\limits_{i = 1}^n m_i \geqslant 3n - 4 \geqslant 3(|S| + 2) - 4 = 3|S| + 2 \gt 3|S| = \sum\limits_{v \in S} d_G(v)[/math], что, очевидно, невозможно. Найдено противоречие, следовательно, множество Татта выбрать невозможно, следовательно, в [math]G[/math] есть совершенное паросочетание.

[math]\triangleleft[/math]

Следствие из данной теоремы: для любого двусвязного кубического графа существует совершенное паросочетание.

Теорема Фринка (Frink)

Теорема (Фринк):

Пусть [math]G = (V, E)[/math] — двусвязный кубический граф. Возьмём ребро [math]p = (c, d)[/math]. Пусть вершины [math]a[/math] и [math]b[/math] смежны с вершиной [math]c[/math], а вершины [math]e[/math] и [math]f[/math] смежны с вершиной [math]d[/math] (рисунок [math]1 (a)[/math]). Как минимум одно из двух сокращений графа [math]G[/math], состоящее из удаления вершин [math]c, d[/math] и пересоединения вершин [math]a, b, e, f[/math] рёбрами [math](a, e), (b, f)[/math] или [math](a, f), (b, e)[/math] (рисунок [math]1 (b), (c)[/math], рисунок [math]2[/math]) сохранит двусвязность графа.

Доказательство:

[math]\triangleright[/math]

Обозначим компоненты графа [math]G(V - \{c, d\})[/math] как [math]A, B, E, F[/math], которые содержат вершины [math]a, b, e, f[/math] соответственно. Так как [math]G[/math] не имеет мостов (соответственно [math]p[/math] не является мостом) должно существовать ребро, соединяющее одну из компонент [math]A[/math] или [math]B[/math], с одной из компонент [math]E[/math] или [math]F[/math]. Без потери общности предположим, что [math]A[/math] соединено с [math]E[/math]. Заметим, что рёбра [math](b, c), (d, f)[/math] так же не являются мостами, значит возможны три случая (с учётом изоморфизма) (рисунок [math]3[/math]): компонента [math]B[/math] соединена с [math]F[/math], компонента [math]B[/math] соединена с [math]E[/math] и компонента [math]E[/math] соединена с [math]F[/math], компонента [math]A[/math] соединена с [math]B[/math] и компонента [math]E[/math] соединена с [math]F[/math]. Во всех трёх случаях если [math]G(V - \{c, d\})[/math] расширить рёбрами [math](a, f), (b, e)[/math] (получим граф [math]G'[/math]), добавленные рёбра будут лежать на некотором цикле в [math]G'[/math] (рисунок [math]4[/math]). Так же для любой пары вершин [math]u, v[/math] [math]\in[/math] [math]\{a, b, e, f\}[/math] существует цикл в [math]G'[/math], содержащий данные вершины. Чтобы доказать, что [math]G'[/math] двусвязен, нужно показать, что каждое ребро [math]r[/math] из [math]G'[/math] лежит на некотором цикле в [math]G'[/math]. Пусть цикл [math]C[/math] в [math]G[/math] содержит [math]r[/math] (такой цикл существует, так как [math]G[/math] двусвязен). Если [math]C[/math] не проходит через вершины [math]c, d[/math] тогда [math]C[/math] так же является циклом в [math]G'[/math], иначе построим цикл [math]C'[/math] графа [math]G'[/math] из [math]C[/math] следующим образом: если путь [math] x - c - d - y [/math] [math]\in[/math] [math] C [/math], [math] x [/math] [math]\in[/math] [math] \{a, b\} [/math], [math] y [/math] [math]\in[/math] [math] \{e, f\} [/math], удалим этот путь и добавим любой другой из [math] x [/math] в [math] y [/math] в [math] G' [/math], не содержащий [math]r[/math] (такой путь всегда существует, так как [math] x [/math] и [math] y [/math] принадлежат некоторому циклу в [math] G' [/math]), если путь [math] a - c - b [/math] [math]\in[/math] [math] C [/math], удалим этот путь и добавим любой другой из [math] a [/math] в [math] b [/math] в [math] G' [/math], не содержащий [math]r[/math], если путь [math] e - d - f [/math] [math]\in[/math] [math] C [/math], удалим этот путь и добавим любой другой из [math] e [/math] в [math] f [/math] в [math] G' [/math], не содержащий [math]r[/math]. [math]C'[/math] это набор циклов (так как [math]C'[/math] получен из [math]C[/math] путём преобразования некоторых путей) и содержит [math]r[/math]. Из этого следует, что каждое ребро графа [math]G'[/math] лежит на некотором цикле, то есть граф не содержит мостов. Значит [math]G'[/math] двусвязен.

[math]\triangleleft[/math]

Рисунок 1. Сокращение двусвязного кубического графа. [math](a)[/math] Нужно удалить вершины [math]c, d[/math]. [math](b)[/math] первый тип сокращения — вершина [math]a[/math] соединена с [math]e[/math], вершина [math]b[/math] соединена с [math]f[/math]. [math](c)[/math] второй тип сокращений — вершина [math]a[/math] соединена с [math]f[/math], вершина [math]b[/math] соединена с [math]e[/math].

Рисунок 2. Особые случаи сокращения графа. [math](a)[/math] ребро [math](c, d)[/math], которое нужно удалить, кратное. Сокращение удаляет вершины [math]c, d[/math] из графа и соединяет [math]a[/math] и [math]e[/math] новым ребром. [math](b)[/math] ребро [math](c, d)[/math] инцидентно двум двойным рёбрам [math](a, c)[/math] и [math](d, e)[/math]. Сокращение удаляет вершины [math]c, d[/math] и добавляет новое кратное ребро [math](a, e)[/math]. [math](c)[/math] Ребро [math](c, d)[/math] инцидентно одному ребру [math](d, e)[/math]. Сокращение удаляет вершины [math]c, d[/math] и добавляет два новых ребра [math](a, e)[/math] и [math](b, e)[/math]. [math](d)[/math] Ребро [math](c, d)[/math] тройной кратности. Сокращение удаляет вершины [math]c, d[/math].

Рисунок 3. Все возможные соединения двусвязных компонент графа [math]G[V - \{c,d\}][/math]. [math](a)[/math] Компонента [math]A[/math] соединена с компонентой [math]E[/math], компонента [math]B[/math] соединена с компонентой [math]F[/math]. [math](b)[/math] Компонента [math]E[/math] соединена с компонентами [math]A, B, F[/math]. [math](c)[/math] Компонента [math]A[/math] соединена с компонентами [math]B, E[/math], компонента [math]E[/math] соединена с компонентой [math]F[/math].

Рисунок 4. Возможные соединения двусвязный компонент [math]A, B, E, F[/math] после удаления ребра [math](c, d)[/math] и добавления рёбер [math](a, f)[/math] и [math](b, e)[/math].

Алгоритм поиска совершенного паросочетания (Frink's algorithm)

Будем сокращать данный граф [math]G[/math] вышеизложенным способом (на каждой итерации можем выбирать любое ребро) пока не удалим все вершины. Когда все вершины закончились, создадим пустое совершенное паросочетание [math]M[/math] и начнём обратный процесс для всех сокращений, то есть будем восстанавливать граф (начиная с последних удалённых вершин). Каждый такой шаг будет приводить к одному из четырёх базовых случаев, представленных в рисунке [math]5[/math] или к одному из специальных случаев из рисунка [math]6[/math]. Восстановление для всех специальных случаев, а так же для первых трёх базовых выполняется по строгому алгоритму, т.е. разрешимо за [math]O(1)[/math]. Единственный проблемный случай, когда оба ребра принадлежат совершенному паросочетанию. В этой ситуации необходимо найти альтернативный цикл, содержащий как минимум одно из этих рёбер и обновить паросочетание с этим циклом. Эти действия сводят четвёртый базовый случай к одному из первых трёх.

Рисунок 5. Базовые случаи восстановления графа.

Рисунок 6. Особые случаи восстановления графа.

Псевдокод алгоритма Фринка

• [math]G[/math] — двусвязный кубический граф,
• [math]M[/math] — совершенное паросочетание [math]G[/math],
• функция [math]\mathtt{bridgeless}[/math] возвращает [math]true[/math] если у графа нет моста или [math]false[/math] в противном случае,
• функция [math]\mathtt{alternatingCycle}[/math] принимает три параметра: граф, совершенное паросочетание и ребро. Возвращает альтернативный цикл, включающий в себя данное ребро и обновляет совершенное паросочетание,
• функция [math]\mathtt{reductions}[/math] сокращает граф,
• функция [math]\mathtt{simpleReversion}[/math] восстанавливает граф,
• функция [math]\mathtt{reductedGraph}[/math] принимает три параметра: граф, удаляемые вершины, добавляемые рёбра. Возвращает новый граф, у которого удалены выбранные вершины, вместе c инцидентными рёбрами и добавлены другие рёбра, переданные в параметрах. При этом исходный граф не меняется.

function frinkMatching[math](G)[/math]:
    if [math]|V| = 0[/math] 
        return [math]\varnothing[/math]
    [math]v - w = E[0][/math]
    [math]R = [/math] reductions[math](G, v - w)[/math]
    if bridgeless[math]([/math]reductedGraph[math](G, \{v, w\}, R[0]))[/math] 
        [math]r = R[0][/math]
    else
        [math]r = R[1][/math]
    [math]M =[/math] frinkMatching[math]([/math]reductedGraph[math](G,\{v, w\}, r))[/math]
    if [math]|r \cap M| = 2 [/math] 
        [math]C =[/math] alternatingCycle[math](G, M, r[0])[/math]
        [math]M = M \oplus C[/math]
    [math]M = (M - r)\  \cup [/math] simpleReversion[math](G, v, w, r, M)[/math]
    return [math]M[/math]

Время работы алгоритма Фринка

Операция сокращения должна на каждом шаге проверять граф на наличие мостов за [math]O(n)[/math], кроме того, при возникновении четвёртого базового случая требуется найти альтернативный цикл за [math]O(n)[/math]. В алгоритме [math]O(n)[/math] операций сокращения и восстановления графа, причем каждая из этих операций требует [math]O(n)[/math] времени. Таким образом, весь этот алгоритм исполняется за время [math]O(n^2)[/math].

См. также

• Использование обхода в глубину для поиска цикла
• Использование обхода в глубину для поиска мостов
• Паросочетания: основные определения, теорема о максимальном паросочетании и дополняющих цепях

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

• Лекториум — Дополнительные главы теории паросочетаний
• Wikipedia — Кубический граф
• Piotr Stanczyk — THEORY AND PRACTICE OF COMPUTING MAXIMUM MATCHINGS IN GRAPHS стр. 21-28.
• Карпов В. Д. - Теория графов, стр 42