Изменения

|id=th1.

|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|Кубический граф с тремя мостами, в котором не существует совершенного паросочетания.]]Заметим, что утверждение теоремы: не может быть усилено до большего числа мостов, так как для любого двусвязного кубического графа случая с тремя мостами существует совершенное паросочетаниеконтрпример.

Пусть <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>B</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>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> следующим образом:

|[[Файл: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|500px|Рисунок 4. Возможные соединения двусвязный компонент <tex>A, B, E, F</tex> после удаления ребра <tex>(c, d)</tex> и добавления рёбер <tex>(a, f)</tex> и <tex>(b, e)</tex>.]]

==Алгоритм поиска совершенного паросочетания за <tex>O(n^2)</tex> (Frink's algorithm)==*будем Будем сокращать данный граф <tex>G</tex> вышеизложенным способом (на каждой итерации можем выбирать любое ребро) пока не удалим все вершины,.*когда Когда все вершины закончились, создадим пустое совершенное паросочетание <tex>M</tex> и начнём обратный процесс для всех сокращений, то есть восстановление графа будем восстанавливать граф (начиная с последних удалённых вершин). Каждый такой шаг будет приводить к одному из четырёх базовых случаев, представленных в рисунке <tex>5</tex> или к одному из специальных случаев из рисунка <tex>6</tex>. Восстановление для всех специальных случаев, а так же для первых трёх базовых выполняется по строгому алгоритму, т.е. разрешим разрешимо за <tex>O(1)</tex>. Единственный проблемный случай, когда оба ребра принадлежат совершенному паросочетанию. В этой ситуации необходимо найти альтернативный цикл, содержащий как минимум одно из этих рёбер и обновить паросочетание с этим циклом. Эти действия сводят четвёртый базовый случай к одному из первых трёх.

|[[Файл:Frinks_algorithm5.PNG|thumb|400px|Рисунок 5. Базовые случаи восстановления графа.]] |[[Файл:Frinks_algorithm6.PNG|thumb|400px|Рисунок 6. Особые случаи восстановления графа.]]

==Реализация Псевдокод алгоритма Фринка==* <tex>G</tex> {{---}} двусвязный кубический граф,* <tex>M</tex> {{---}} совершенное паросочетание <tex>G</tex>.,* функция <tex>\mathtt{bridgeless}</tex> сообщаетвозвращает <tex>true</tex> если у графа нет моста или <tex>false</tex> в противном случае, имеет ли граф мост.* функция <tex>alternating\_cyclemathtt{alternatingCycle}</tex> принимает три параметра: граф, совершенное паросочетание и ребро. Возвращает альтернативный цикл, включающий в себя данное ребро и обновляет совершенное паросочетание. , * функции функция <tex>\mathtt{reductions}</tex> сокращает граф,*функция <tex>\mathtt{simpleReversion}</tex> и восстанавливает граф,*функция <tex>simple\_reversionmathtt{reductedGraph}</tex> сокращают принимает три параметра: граф, удаляемые вершины, добавляемые рёбра. Возвращает новый граф, у которого удалены выбранные вершины, вместе c инцидентными рёбрами и восстанавливают добавлены другие рёбра, переданные в параметрах. При этом исходный граф соответственноне меняется.

'''function''' frinkMatching<tex>(G)</tex>: '''if''' <tex>|V| = 0</tex> '''then''' '''return''' <tex>\varnothing</tex> '''else'''

<tex>R = </tex> reductions<tex>(G, v - w)</tex> '''if''' bridgeless<tex>(</tex>reductedGraph<tex> bridgeless(G[V − , \{v, w\}, E \cup R[0]]))</tex> '''then'''

'''end if''' <tex>M \leftarrow frink\_matching=</tex> frinkMatching<tex>(</tex>reductedGraph<tex>(G[V - ,\{v, w\}, E \cup r]))</tex> '''if''' <tex>|r \cap M| = 2 </tex> '''then''' <tex>C \leftarrow alternating\_cycle=</tex> alternatingCycle<tex>(G, M, r[0])</tex> <tex>M \leftarrow = M \oplus C</tex> '''end if''' <tex>M \leftarrow = (M - r) \ \cup simple\_reversion</tex> simpleReversion<tex>(G, v, w, r, M)</tex>

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

==СсылкиСм. также==