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

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

Алгоритм за O(n^2 log n)

Идея алгоритма

Рассмотрим граф [math]G^d[/math], двойственный данному графу [math]G[/math]. Рассмотрим кратчайший путь [math]\Pi[/math] между вершинами [math]\xi^s[/math] и [math]\xi^t[/math], принадлежащими граням [math]\varphi_s[/math] и [math]\varphi_t[/math], соответствующим вершинам [math]s[/math] и [math]t[/math] в исходном графе. Определим [math]\Pi[/math]-левые и [math]\Pi[/math]-правые ребра, [math]\Pi[/math]-левые будут лежать "слева" по пути из [math]\xi^s[/math] в [math]\xi^t[/math], а [math]\Pi[/math]-правые "справа". Формальное определение будет дано в следующем разделе. Тогда минимальный цикл в [math]G^d[/math], ограничивающий [math]\varphi_t[/math], будет [math]\xi_i[/math]-циклом — циклом, содержащим ровно одно [math]\Pi[/math]-левое и одно [math]\Pi[/math]-правое ребро, причем [math]\Pi[/math]-левое ребро входит в вершину [math]\xi_i[/math].

Кси-циклы

Каждый такой цикл соответствует разрезу в [math]G[/math]. Тогда алгоритм можно записать так:

1. Построим граф [math]G^d[/math], двойственный исходному графу [math]G[/math]
2. Найдем кратчайший путь [math]\Pi[/math] между вершинами [math]\xi^s[/math] и [math]\xi^t[/math]
3. Для каждой вершины [math]\xi_i\in\Pi[/math] найдем кратчайший [math]\xi_i[/math]-цикл
4. Найдем среди этих циклов цикл минимальной длины и построим соответствующий ему разрез в [math]G[/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 \mid \alpha^d\in C\}[/math] — цикл минимальной длины, ограничивающий [math]\varphi_t[/math].

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

[math]\triangleright[/math]

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

[math]\triangleleft[/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]\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\leftrightarrow 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