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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 29: Строка 29:
 
}}
 
}}
  
[[Файл:Frinks_algorithm1.png|thumb|right|300x300px|Рисунок 1.]]
+
{|align="center"
 +
|-valign="center"
 +
|[[Файл:Frinks_algorithm1.png|thumb|400px|Рисунок 1.]]
 +
|[[Файл:Frinks_algorithm2.PNG|thumb|400px|Рисунок 2.]]
 +
|}
  
 
+
{|align="center"
 
+
|-valign="center"
 
+
|[[Файл:Frinks_algorithm3.PNG|thumb|400px|Рисунок 3.]]
==Алгоритм поиска совершенного паросочетания за <tex>O(n^2)</tex> (Frink's algorithm)==
+
|[[Файл:Frinks_algorithm4.PNG|thumb|400px|Рисунок 4.]]
Главная идея алгоритма заключается в предыдущей теореме.
+
|}

Версия 16:28, 28 января 2016

Теорема (Петерсон):
Кубический граф, у которого нет совершенного паросочетания, содержит как минимум [math]3[/math] моста.

Следствие теоремы Петерсона

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

Теорема (Фринк):
Пусть [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]\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.
Рисунок 2.
Рисунок 3.
Рисунок 4.