Совершенное паросочетание в кубическом графе — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показано 85 промежуточных версий 4 участников)
Строка 1: Строка 1:
 +
==Лемма о сравнимости по модулю 2==
 +
{{Лемма
 +
|id = lemma1
 +
|statement =
 +
Пусть <tex>G</tex> {{---}} <tex>k</tex>-[[Основные определения теории графов#defRegularGraph |регулярный граф]], <tex>U \in V(G)</tex>, <tex>|U|</tex> нечётно, <tex>m</tex> {{---}} число рёбер, соединяющих вершины множества <tex>U</tex> с вершинами из <tex>V(G) \setminus U</tex>. Тогда <tex>m \equiv k \pmod 2</tex>
 +
|proof =
 +
[[Файл:Сравнимость.png|300px|thumb|left|Иллюстрация к лемме]]
 +
<tex>m = (\sum\limits_{v \in U} d_G(v)) - 2e(G(U))</tex>, где <tex>e(G(U))</tex> {{---}} количество рёбер, соединяющих вершину из <tex>U</tex> с другой вершиной из <tex>U</tex>.
 +
 +
тогда <tex>m = k|U| - 2e(G(U))</tex>.
 +
 +
<tex>2e(G(U))</tex> чётно, поэтому <tex>m \equiv k|U| \pmod 2</tex>. Так как <tex> |U|</tex> нечётно, <tex>m \equiv k \pmod 2</tex>.
 +
}}
 +
 +
==Теорема Петерсона (Petersen)==
 +
{{Определение
 +
|id=cube_graf_def
 +
|definition= '''Кубический граф''' (англ. ''Cubic graph'') {{---}} [[Основные определения: граф, ребро, вершина, степень, петля, путь, цикл| граф]], в котором все вершины имеют степень три. Другими словами, кубический граф является <tex>3</tex>-регулярным.}}
 +
 
{{Теорема
 
{{Теорема
|id=th1.
+
|id=th1  
 
|author=Петерсон
 
|author=Петерсон
|statement=Кубический граф, у которого нет совершенного паросочетания, содержит как минимум <tex>3</tex> моста. }}
+
|statement = Пусть <tex>G</tex>{{---}}[[Отношение связности, компоненты связности#connected_graph | связный]] кубический граф, в котором не более <tex>2</tex> [[Мост, эквивалентные определения | мостов]]. Тогда в <tex>G</tex> есть [[Паросочетания: основные определения, теорема о максимальном паросочетании и дополняющих цепях#perfect_matching | совершенное паросочетание]].
 +
|proof =
 +
Предположим, что совершенного паросочетания в <tex>G</tex> нет, тогда можно выбрать [[Теорема Татта о существовании полного паросочетания#Tutt_set | множество Татта]] <tex>S \subset V(G)</tex>.
 +
 
 +
Пусть <tex>U_1, \ldots, U_n</tex> {{---}} все нечётные компоненты связности графа <tex>G \setminus S</tex>. <tex>m_i</tex> {{---}} количество ребёр <tex>G</tex>, связывающих вершины <tex>U_i</tex> с вершинами <tex>S</tex>.
 +
 
 +
По предыдущей лемме, все <tex>m_i</tex> нечётны. Так как не более чем два ребра графа <tex>G</tex> {{---}} мосты, то не более, чем два числа из <tex>m_1, \ldots, m_n</tex> равны <tex>1</tex>, остальные числа не менее <tex>3</tex>.
  
==Следствие теоремы Петерсона==
+
Так как <tex>S</tex> {{---}} множество Татта, то <tex>odd(G \setminus S) > |S|</tex>. Так как количество вершин кубического графа <tex>G</tex> чётно, мы имеем <tex>S \neq \emptyset, odd(G \setminus S) \equiv S \pmod 2</tex>, следовательно, <tex>n = odd(G \setminus S) \geqslant |S| + 2</tex>. Тогда
Для любого двусвязного кубического графа существует совершенное паросочетание.
 
  
 +
<tex>\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 > 3|S| = \sum\limits_{v \in S} d_G(v)</tex>, что, очевидно, невозможно.
 +
 +
Найдено противоречие, следовательно, множество Татта выбрать невозможно, следовательно, в <tex>G</tex> есть совершенное паросочетание.
 +
}}
 +
 +
[[Файл:Петерсен 3 моста.png|300px|thumb|left|Кубический граф с тремя мостами, в котором не существует совершенного паросочетания.]]
 +
Заметим, что утверждение теоремы не может быть усилено до большего числа мостов, так как для случая с тремя мостами существует контрпример.
 +
 +
==Теорема Фринка (Frink)==
 
{{Теорема
 
{{Теорема
 
|id=th2.  
 
|id=th2.  
Строка 12: Строка 46:
 
|statement=
 
|statement=
  
Пусть <tex>G(V, E)</tex> двусвязный кубический граф.  
+
Пусть <tex>G = (V, E)</tex> {{---}}  двусвязный кубический граф.  
Возьмём ребро <tex>p = (c, d)</tex>. Пусть вершины <tex>a</tex> и <tex>b</tex> смежены с вершиной <tex>c</tex>, а вершины <tex>e</tex> и <tex>f</tex> смежны с вершиной <tex>d</tex> (рисунок <tex>1 (a)</tex>).  
+
Возьмём ребро <tex>p = (c, d)</tex>. Пусть вершины <tex>a</tex> и <tex>b</tex> смежны с вершиной <tex>c</tex>, а вершины <tex>e</tex> и <tex>f</tex> смежны с вершиной <tex>d</tex> (рисунок <tex>1 (a)</tex>).  
Как минимум одно из двух сокращений графа <tex>G</tex>, состоящее из удаления вершин <tex>c, d</tex> и пересоединения вершин <tex>a, b, e, f</tex> рёбрами <tex>(a, e), (b, f)</tex> или <tex>(a, f), (b, e)</tex> (рисунок <tex>1 (b), (c)</tex>) сохранит двусвязность графа.
+
Как минимум одно из двух сокращений графа <tex>G</tex>, состоящее из удаления вершин <tex>c, d</tex> и пересоединения вершин <tex>a, b, e, f</tex> рёбрами <tex>(a, e), (b, f)</tex> или <tex>(a, f), (b, e)</tex> (рисунок <tex>1 (b), (c)</tex>, рисунок <tex>2</tex>) сохранит двусвязность графа.
  
 
|proof=
 
|proof=
Обозначим компоненты графа <tex>G(V - {c, d})</tex>  как <tex>A, B, E, F</tex>, которые содержат вершины <tex>a, b, e, f</tex> соответственно. Так как <tex>G</tex> не имеет мостов (соответственно <tex>p</tex> не является мостом) должно существовать ребро, соединяющее одну из компонент <tex>A</tex> или <tex>B</tex>, с одной из компонент <tex>E</tex> или <tex>F</tex>. Без потери общности предположим, что <tex>A</tex> соединено с <tex>E</tex>. Заметим, что рёбра <tex>(b, c), (d, f)</tex> так же не являются мостами, значит возможны три случая (с учётом изоморфизма) (рисунок <tex>3</tex>):
+
Обозначим компоненты графа <tex>G(V - \{c, d\})</tex>  как <tex>A, B, E, F</tex>, которые содержат вершины <tex>a, b, e, f</tex> соответственно. Так как <tex>G</tex> не имеет мостов (соответственно <tex>p</tex> не является мостом) должно существовать ребро, соединяющее одну из компонент <tex>A</tex> или <tex>B</tex>, с одной из компонент <tex>E</tex> или <tex>F</tex>. Без потери общности предположим, что <tex>A</tex> соединено с <tex>E</tex>. Заметим, что рёбра <tex>(b, c), (d, f)</tex> так же не являются мостами, значит возможны три случая (с учётом изоморфизма) (рисунок <tex>3</tex>):
* компонента <tex>B</tex> соединена с <tex>F</tex>
+
* компонента <tex>B</tex> соединена с <tex>F</tex>,
* компонента <tex>B</tex> соединена с <tex>E</tex> и компонента <tex>E</tex> соединена с <tex>F</tex>
+
* компонента <tex>B</tex> соединена с <tex>E</tex> и компонента <tex>E</tex> соединена с <tex>F</tex>,
* компонента <tex>A</tex> соединена с <tex>B</tex> и компонента <tex>E</tex> соединена с <tex>F</tex>
+
* компонента <tex>A</tex> соединена с <tex>B</tex> и компонента <tex>E</tex> соединена с <tex>F</tex>.
Во всех трёх случаях если <tex>G(V - {c, d})</tex> расширить рёбрами <tex>(a, f), (b, e)</tex> (получим граф <tex>G'</tex>), добавленные рёбра будут лежать на некотором цикле в <tex>G'</tex> (рисунок <tex>4</tex>). Так же, для любой пары вершин <tex>u, v</tex> <math>\in</math> <tex>{a, b, e, f}</tex> существует цикл в <tex>G'</tex>, содержащий данные вершины. Чтобы доказать, что <tex>G'</tex> двусвязен, нужно показать, что каждое ребро <tex>r</tex> из <tex>G'</tex> лежит на некотором цикле в <tex>G'</tex>. Пусть цикл <tex>C</tex> в <tex>G</tex> содержит <tex>r</tex> (такой цикл существует, так как <tex>G</tex> двусвязен). Если <tex>C</tex> не проходит через вершины <tex>c, d</tex> тогда <tex>C</tex> так же является циклом в <tex>G'</tex>, иначе построим цикл <tex>C'</tex> графа <tex>G'</tex> из <tex>C</tex> следующим образом:  
+
Во всех трёх случаях если <tex>G(V - \{c, d\})</tex> расширить рёбрами <tex>(a, f), (b, e)</tex> (получим граф <tex>G'</tex>), добавленные рёбра будут лежать на некотором [[Основные определения: граф, ребро, вершина, степень, петля, путь, цикл| цикле]] в <tex>G'</tex> (рисунок <tex>4</tex>). Так же для любой пары вершин <tex>u, v</tex> <math>\in</math> <tex>\{a, b, e, f\}</tex> существует цикл в <tex>G'</tex>, содержащий данные вершины. Чтобы доказать, что <tex>G'</tex> двусвязен, нужно показать, что каждое ребро <tex>r</tex> из <tex>G'</tex> лежит на некотором цикле в <tex>G'</tex>. Пусть цикл <tex>C</tex> в <tex>G</tex> содержит <tex>r</tex> (такой цикл существует, так как <tex>G</tex> двусвязен). Если <tex>C</tex> не проходит через вершины <tex>c, d</tex> тогда <tex>C</tex> так же является циклом в <tex>G'</tex>, иначе построим цикл <tex>C'</tex> графа <tex>G'</tex> из <tex>C</tex> следующим образом:  
 
* если путь <tex> x - c - d - y </tex> <math>\in</math> <tex> C </tex>, <tex> x </tex> <math>\in</math> <tex> \{a, b\} </tex>, <tex> y </tex> <math>\in</math> <tex> \{e, f\} </tex>, удалим этот путь и добавим любой другой из <tex> x </tex> в <tex> y </tex> в <tex> G' </tex>, не содержащий <tex>r</tex> (такой путь всегда существует, так как <tex> x </tex> и <tex> y </tex> принадлежат некоторому циклу в <tex> G' </tex>),
 
* если путь <tex> x - c - d - y </tex> <math>\in</math> <tex> C </tex>, <tex> x </tex> <math>\in</math> <tex> \{a, b\} </tex>, <tex> y </tex> <math>\in</math> <tex> \{e, f\} </tex>, удалим этот путь и добавим любой другой из <tex> x </tex> в <tex> y </tex> в <tex> G' </tex>, не содержащий <tex>r</tex> (такой путь всегда существует, так как <tex> x </tex> и <tex> y </tex> принадлежат некоторому циклу в <tex> G' </tex>),
 
* если путь <tex> a - c - b </tex> <math>\in</math> <tex> C </tex>, удалим этот путь и добавим любой другой из <tex> a </tex> в <tex> b </tex> в <tex> G' </tex>, не содержащий <tex>r</tex>,
 
* если путь <tex> a - c - b </tex> <math>\in</math> <tex> C </tex>, удалим этот путь и добавим любой другой из <tex> a </tex> в <tex> b </tex> в <tex> G' </tex>, не содержащий <tex>r</tex>,
Строка 31: Строка 65:
 
{|align="center"
 
{|align="center"
 
  |-valign="center"
 
  |-valign="center"
  |[[Файл:Frinks_algorithm1.png|thumb|400px|Рисунок 1.]]
+
  |[[Файл:Frinks_algorithm1.png|thumb|500px|Рисунок 1. Сокращение двусвязного кубического графа. <tex>(a)</tex> Нужно удалить вершины <tex>c, d</tex>. <tex>(b)</tex> первый тип сокращения {{---}} вершина <tex>a</tex> соединена с <tex>e</tex>, вершина <tex>b</tex> соединена с <tex>f</tex>. <tex>(c)</tex> второй тип сокращений {{---}} вершина <tex>a</tex> соединена с <tex>f</tex>, вершина <tex>b</tex> соединена с <tex>e</tex>.]]
  |[[Файл:Frinks_algorithm2.PNG|thumb|400px|Рисунок 2.]]
+
  |[[Файл:Frinks_algorithm2.PNG|thumb|500px|Рисунок 2. Особые случаи сокращения графа. <tex>(a)</tex> ребро <tex>(c, d)</tex>, которое нужно удалить, кратное. Сокращение удаляет вершины <tex>c, d</tex> из графа и соединяет <tex>a</tex> и <tex>e</tex> новым ребром. <tex>(b)</tex> ребро <tex>(c, d)</tex> инцидентно двум двойным рёбрам <tex>(a, c)</tex> и <tex>(d, e)</tex>. Сокращение удаляет вершины <tex>c, d</tex> и добавляет новое кратное ребро <tex>(a, e)</tex>. <tex>(c)</tex> Ребро <tex>(c, d)</tex> инцидентно одному ребру <tex>(d, e)</tex>. Сокращение удаляет вершины <tex>c, d</tex> и добавляет два новых ребра <tex>(a, e)</tex> и <tex>(b, e)</tex>. <tex>(d)</tex> Ребро <tex>(c, d)</tex> тройной кратности. Сокращение удаляет вершины <tex>c, d</tex>.  ]]
 
  |}
 
  |}
  
 
{|align="center"
 
{|align="center"
 
  |-valign="center"
 
  |-valign="center"
  |[[Файл:Frinks_algorithm3.PNG|thumb|400px|Рисунок 3.]]
+
  |[[Файл:Frinks_algorithm3.PNG|thumb|500px|Рисунок 3. Все возможные соединения двусвязных компонент графа <tex>G[V - \{c,d\}]</tex>. <tex>(a)</tex> Компонента <tex>A</tex> соединена с компонентой <tex>E</tex>, компонента <tex>B</tex> соединена с компонентой <tex>F</tex>. <tex>(b)</tex> Компонента <tex>E</tex> соединена с компонентами <tex>A, B, F</tex>. <tex>(c)</tex> Компонента <tex>A</tex> соединена с компонентами <tex>B, E</tex>, компонента <tex>E</tex> соединена с компонентой <tex>F</tex>. ]]
  |[[Файл:Frinks_algorithm4.PNG|thumb|400px|Рисунок 4.]]
+
  |[[Файл:Frinks_algorithm4.PNG|thumb|500px|Рисунок 4. Возможные соединения двусвязный компонент <tex>A, B, E, F</tex> после удаления ребра <tex>(c, d)</tex> и добавления рёбер <tex>(a, f)</tex> и <tex>(b, e)</tex>.]]
 
  |}
 
  |}
  
 
+
==Алгоритм поиска совершенного паросочетания (Frink's algorithm)==
==Алгоритм поиска совершенного паросочетания за O(n^2) (Frink's algorithm)==
+
Будем сокращать данный граф <tex>G</tex> вышеизложенным способом (на каждой итерации можем выбирать любое ребро) пока не удалим все вершины.
*будем сокращать данный граф <tex>G</tex> вышеизложенным способом (на каждой итерации можем выбирать любое ребро) пока не удалим все вершины,
+
Когда все вершины закончились, создадим пустое совершенное паросочетание <tex>M</tex> и начнём обратный процесс для всех сокращений, то есть будем восстанавливать граф (начиная с последних удалённых вершин). Каждый такой шаг будет приводить к одному из четырёх базовых случаев, представленных в рисунке <tex>5</tex> или к одному из специальных случаев из рисунка <tex>6</tex>. Восстановление для всех специальных случаев, а так же для первых трёх базовых выполняется по строгому алгоритму, т.е. разрешимо за <tex>O(1)</tex>. Единственный проблемный случай, когда оба ребра принадлежат совершенному паросочетанию. В этой ситуации необходимо найти альтернативный цикл, содержащий как минимум одно из этих рёбер и обновить паросочетание с этим циклом. Эти действия сводят четвёртый базовый случай к одному из первых трёх.
*когда все вершины закончились, создадим пустое совершенное паросочетание <tex>M</tex> и начнём обратный процесс для всех сокращений, то есть восстановление графа (начиная с последних удалённых вершин). Каждый такой шаг будет приводить к одному из четырёх базовых случаев, представленных в рисунке <tex>5</tex> или к одному из специальных случаев из рисунка <tex>6</tex>. Восстановление для всех специальных случаев, а так же для первых трёх базовых выполняется по строгому алгоритму, т.е. разрешим за <tex>O(1)</tex>. Единственный проблемный случай, когда оба ребра принадлежат совершенному паросочетанию. В этой ситуации необходимо найти альтернативный цикл, содержащий как минимум одно из этих рёбер и обновить паросочетание с этим циклом. Эти действия сводят четвёртый базовый случай к одному из первых трёх.
 
  
  
 
{|align="center"
 
{|align="center"
 
  |-valign="center"
 
  |-valign="center"
  |[[Файл:Frinks_algorithm5.PNG|thumb|400px|Рисунок 5.]]
+
  |[[Файл:Frinks_algorithm5.PNG|thumb|400px|Рисунок 5. Базовые случаи восстановления графа.]]
  |[[Файл:Frinks_algorithm6.PNG|thumb|400px|Рисунок 6.]]
+
  |[[Файл:Frinks_algorithm6.PNG|thumb|400px|Рисунок 6. Особые случаи восстановления графа.]]
 
  |}
 
  |}
  
==Реализация==
+
==Псевдокод алгоритма Фринка==
* <tex>G</tex> двусвязный кубический граф,
+
*<tex>G</tex> {{---}} двусвязный кубический граф,  
* <tex>M</tex> совершенное паросочетание <tex>G</tex>.
+
*<tex>M</tex> {{---}} совершенное паросочетание <tex>G</tex>,
 +
*функция <tex>\mathtt{bridgeless}</tex> возвращает <tex>true</tex> если у графа нет моста или <tex>false</tex> в противном случае,
 +
*функция <tex>\mathtt{alternatingCycle}</tex> принимает три параметра: граф, совершенное паросочетание и ребро. Возвращает альтернативный цикл,  включающий в себя данное ребро и обновляет совершенное паросочетание,
 +
*функция <tex>\mathtt{reductions}</tex> сокращает граф,
 +
*функция <tex>\mathtt{simpleReversion}</tex> восстанавливает граф,
 +
*функция <tex>\mathtt{reductedGraph}</tex> принимает три параметра: граф, удаляемые вершины, добавляемые рёбра. Возвращает новый граф, у которого удалены выбранные вершины, вместе c инцидентными рёбрами и добавлены другие рёбра, переданные в параметрах. При этом исходный граф не меняется.
  
  '''if''' <tex>|V| = 0</tex> '''then'''
+
  '''function''' frinkMatching<tex>(G)</tex>:
    '''return''' <tex>\varnothing</tex>
+
    '''if''' <tex>|V| = 0</tex>  
'''else'''
+
        '''return''' <tex>\varnothing</tex>
 
     <tex>v - w = E[0]</tex>
 
     <tex>v - w = E[0]</tex>
     <tex>R = reductions(G, v - w)</tex>
+
     <tex>R = </tex> reductions<tex>(G, v - w)</tex>
     '''if''' <tex> bridgeless(G[V − {v, w}, E \cup R[0]])</tex> '''then'''
+
     '''if''' bridgeless<tex>(</tex>reductedGraph<tex>(G, \{v, w\}, R[0]))</tex>  
 
         <tex>r = R[0]</tex>
 
         <tex>r = R[0]</tex>
 
     '''else'''
 
     '''else'''
 
         <tex>r = R[1]</tex>
 
         <tex>r = R[1]</tex>
    '''end if'''
+
     <tex>M =</tex> frinkMatching<tex>(</tex>reductedGraph<tex>(G,\{v, w\}, r))</tex>
     <tex>M \leftarrow frink\_matching(G[V - \{v, w\}, E \cup r])</tex>
+
     '''if''' <tex>|r \cap M| = 2 </tex>  
     '''if''' <tex>|r \cap M| = 2 </tex> '''then'''
+
         <tex>C =</tex> alternatingCycle<tex>(G, M, r[0])</tex>
         <tex>C \leftarrow alternating\_cycle(G, M, r[0])</tex>
+
         <tex>M = M \oplus C</tex>
         <tex>M \leftarrow M \oplus C</tex>
+
     <tex>M = (M - r)\cup </tex> simpleReversion<tex>(G, v, w, r, M)</tex>
    '''end if'''
 
     <tex>M \leftarrow (M - r) \cup simple\_reversion(G, v, w, r, M)</tex>
 
 
     '''return''' <tex>M</tex>
 
     '''return''' <tex>M</tex>
'''end if'''
 
  
 +
==Время работы алгоритма Фринка==
 +
Операция сокращения должна на каждом шаге проверять граф на наличие мостов за <tex>O(n)</tex>, кроме того, при возникновении четвёртого базового случая требуется найти альтернативный цикл за <tex>O(n)</tex>. В алгоритме <tex>O(n)</tex> операций сокращения и восстановления графа, причем каждая из этих операций требует <tex>O(n)</tex> времени. Таким образом, весь этот алгоритм исполняется за время <tex>O(n^2)</tex>.
 +
 +
==См. также==
 +
 +
* [[Использование обхода в глубину для поиска цикла]]
 +
* [[Использование обхода в глубину для поиска мостов]]
 +
* [[Паросочетания: основные определения, теорема о максимальном паросочетании и дополняющих цепях]]
 +
 +
== Источники информации ==
 +
* [https://www.lektorium.tv/course/22771 Лекториум {{---}} Дополнительные главы теории паросочетаний]
 +
* [https://ru.wikipedia.org/wiki/%D0%9A%D1%83%D0%B1%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B8%D0%B9_%D0%B3%D1%80%D0%B0%D1%84 Wikipedia {{---}} Кубический граф]
 +
* Piotr Stanczyk {{---}} THEORY AND PRACTICE OF COMPUTING MAXIMUM MATCHINGS IN GRAPHS стр. 21-28.
 +
* Карпов В. Д. - Теория графов, стр 42
  
==Время работы==
+
[[Категория: Алгоритмы и структуры данных]]
Операция сокращения должна на каждом шаге проверять граф на наличие мостов<tex>O(n)</tex>, кроме того, при возникновении четвёртого базового случая требуется найти альтернативный цикл за <tex>O(n)</tex>. В алгоритме <tex>O(n)</tex> операций сокращения и восстановления графа, причем каждая из этих операций требует <tex>O(n)</tex> времени. Таким образом, весь этот алгоритм исполняется за время <tex>O(n^2)</tex>.
+
[[Категория: Задача о паросочетании]]

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

Лемма о сравнимости по модулю 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]2[/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].

См. также

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