84
правки
Изменения
Новая страница: «{{Теорема |id=th1. |author=Петерсон |statement=Кубический граф, у которого нет совершенного паросоче...»
{{Теорема
|id=th1.
|author=Петерсон
|statement=Кубический граф, у которого нет совершенного паросочетания, содержит как минимум 3 моста. }}
==Следствие теоремы Петерсона==
Для любого двусвязного кубического графа существует совершенное паросочетание.
{{Теорема
|id=th2.
|author=Фринк
|statement=
Пусть <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>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>) сохранит двусвязность графа.
|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>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>
}}
[[Файл:Frinks_algorithm1.png|thumb|right|300x300px|Рисунок 1.]]
==Алгоритм поиска совершенного паросочетания за <tex>O(n^2)</tex> (Frink's algorithm)==
Главная идея алгоритма заключается в предыдущей теореме.
|id=th1.
|author=Петерсон
|statement=Кубический граф, у которого нет совершенного паросочетания, содержит как минимум 3 моста. }}
==Следствие теоремы Петерсона==
Для любого двусвязного кубического графа существует совершенное паросочетание.
{{Теорема
|id=th2.
|author=Фринк
|statement=
Пусть <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>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>) сохранит двусвязность графа.
|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>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>
}}
[[Файл:Frinks_algorithm1.png|thumb|right|300x300px|Рисунок 1.]]
==Алгоритм поиска совершенного паросочетания за <tex>O(n^2)</tex> (Frink's algorithm)==
Главная идея алгоритма заключается в предыдущей теореме.
