Разрез в планарных графах

Особенности планарных графов позволяют реализовать поиск минимального разреза в планарном графе с лучшей асимптотикой, чем в произвольном графе. Лучший известный алгоритм работает с асимптотикой [math]O(n\log n)[/math].

Алгоритм за [math]O(n^2 \log n)[/math]

Рассмотрим неориентированный граф [math]G=(V, E)[/math]. Будем считать его трёхсвязным, если это не так, триангулируем его, используя ребра нулевой пропускной способности, это не изменит значение минимального [math](s-t)-[/math] разреза. Минимальный разрез исходного графа будет состоять из ребер минимального разреза нового графа, которые есть и в исходном графе.

[math]G[/math] трёхсвязен, поэтому существует единственный двойственный ему граф [math]G^d=(X, A)[/math], при этом [math]G^d[/math] также трёхсвязен. Будем обозначать множество граней [math]G[/math] как [math]F[/math], множество граней [math]G^d[/math] как [math]\Phi[/math]. Между элементами каждой из пар множеств [math]V-\Phi[/math], [math]E-A[/math] и [math]F-X[/math] существует взаимно однозначное соответствие. Будем обозначать как [math]\alpha^d\in E[/math] элемент, соответствующий [math]\alpha\in A[/math]. Тогда длину ребра [math]\alpha[/math] определим как [math]l(\alpha)=c(\alpha^d)[/math].

Будем обозначать грани [math]G^d[/math], соответствующие вершинам [math]s[/math] и [math]t[/math], как [math]\varphi_s[/math] и [math]\varphi_t[/math] соответственно. Далее будем считать, что [math]\varphi_s[/math] — внешняя грань [math]G^d[/math].

Лемма:

[math]C[/math] — минимальный [math](s-t)-[/math] разрез, тогда [math]C^d=\{\alpha | \alpha^d\in C\}[/math] — цикл минимальной длины, ограничивающий [math]\varphi_t[/math].

Формальное доказательство леммы громоздкое и здесь приведено не будет, однако сама лемма достаточно интуитивно понятна.

Пусть [math]\xi^s\in\varphi_s[/math], [math]\xi^t\in\varphi_t[/math], [math]\Pi=(\xi^s=\xi_1, \ldots, \xi_k=\xi^t)[/math] — кратчайший путь между [math]\xi^s[/math] и [math]\xi^t[/math] в [math]G^d[/math], [math]\alpha_i[/math] — ребро между [math]\xi_{i-1}[/math] и [math]\xi_i[/math] для [math]i=2,\ldots,k[/math]. Будем называть ребро [math]\xi-\xi_i\in A[/math] [math]\Pi-[/math] левым, если оно находится между [math]\alpha_i[/math] и [math]\alpha_{i+1}[/math] при обходе ребер, входящих в [math]\xi_i[/math], по часовой стрелке от [math]\alpha_i[/math], и [math]\Pi-[/math] правым, если оно находится между [math]\alpha_{i+1}[/math] и [math]\alpha_i[/math]. Для того, чтобы это определение имело смысл для первой и последней вершин пути, можно добавить две вершины [math]\xi_0[/math] и [math]\xi_{k+1}[/math] и два ребра [math]\alpha_1=\xi_0-\xi_1[/math] и [math]\alpha_{k+1}=\xi_k-\xi_{k+1}[/math]. Важно, что никакое ребро не является одновременно [math]\Pi-[/math] левым и [math]\Pi-[/math] правым.

Будем называть [math]\xi_i[/math] - циклом простой цикл, который содержит ровно одно [math]\Pi-[/math] левое и одно [math]\Pi-[/math] правое ребро, при этом [math]\Pi-[/math] левое ребро входит в вершину [math]\xi_i[/math]. Любой [math]\xi_i[/math] - цикл ограничивает [math]\varphi_t[/math].

Лемма:

Пусть [math]C[/math] — кратчайший ограничивающий [math]\varphi_t[/math] цикл. Тогда существует [math]\xi_i[/math] - цикл такой же длины.

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

[math]\triangleright[/math]

[math]\Pi[/math] — кратчайший путь между [math]\xi^s[/math] и [math]\xi^t[/math], поэтому любой содержащийся в [math]\Pi[/math] путь между [math]\xi_i[/math] и [math]\xi_j[/math] также кратчайший. При этом любой ограничиващий [math]\varphi_t[/math] цикл обязан пересекать [math]\Pi[/math]. Цикл, не являющийся [math]\xi_i[/math] - циклом, не будет кратчайшим, так как его можно будет сократить вдоль пути [math]\Pi[/math].

[math]\triangleleft[/math]

Из леммы следует алгоритм нахождения минимального ограничивающего [math]\varphi_t[/math] цикла:

1. Для [math]i=1,\ldots,k[/math] найдем минимальный [math]\xi_i[/math] - цикл
2. Кратчайший из этих [math]k[/math] путей будет минимальным ограничивающим [math]\varphi_t[/math] циклом

Для поиска минимального [math]\xi_i[/math] - цикла построим из неориентированного графа [math]G[/math] ориентированный граф [math]\vec{G}^d[/math] следующим образом: все [math]\Pi-[/math] левые ребра ориентируем из вершин [math]\xi\in\Pi[/math], все [math]\Pi-[/math] правые ребра ориентируем в вершины [math]\xi\in\Pi[/math], а остальные ребра [math]u-v[/math] заменим на два ребра [math]u\rightarrow v[/math] и [math]v\rightarrow u[/math].

Лемма:

Пусть [math]\xi_i\in\Pi[/math], [math]P_i[/math] — кратчайший нетривиальный путь из [math]\xi_i[/math] в [math]\xi_i[/math] в [math]\vec{G}^d[/math]. Тогда соответствующий путь в [math]G^d[/math] является кратчайшим [math]\xi_i[/math] - циклом.

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

[math]\triangleright[/math]

Из определения [math]\vec{G}^d[/math] следует, что если нетривиальный путь из [math]\xi_i[/math] в [math]\xi_i[/math] содержит больше одного [math]\Pi-[/math] правого или [math]\Pi-[/math] левого ребра, то в нем есть самопересечение, то есть он не является простым, следовательно, не является кратчайшим [math]\xi_i[/math] - циклом.

[math]\triangleleft[/math]

Таким образом, нахождение минимального [math]\xi_i[/math] - цикла эквивалентно нахождению кратчайшего нетривиального пути из [math]\xi_i[/math] в [math]\xi_i[/math] в [math]\vec{G}^d[/math]. Это можно сделать за [math]O(m\log n)[/math], например, с помощью алгоритма Дейкстры. Так как в планарных графах [math]m=O(n)[/math], это равно [math]O(n\log n)[/math]. Максимум [math]n[/math] таких поисков дадут итоговую асимптотику [math]O(n^2\log n)[/math].

См. также

• Двойственный граф планарного графа
• Разрез, лемма о потоке через разрез
• Укладка графа на плоскости

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

• Improved Algorithms for Min Cuts and Max Flows in Undirected Planar Graphs
• Maximum flow in planar networks, Itai & Shiloach, 1979