SPQR-дерево

SPQR-дерево — это древесная структура данных, используемая в информатике, а именно, в алгоритмах на графах, для представления трёхсвязных компонент графа. Трёхсвязные компоненты двусвязного графа — это система более мелких графов, описывающих все 2-вершинные сечения графа. SPQR-дерево графа может быть построено за линейное время^[1]^[2] и имеет некоторые приложения в алгоритмах динамических графов и визуализации графов.

Граф и его SPQR-дерево. Пунктирные чёрные линии соединяют пары виртуальных рёбер, показанных чёрным. Остальные рёбра выкрашены согласно трёхсвязным компонентам, которым они принадлежат.

Базовую структуру, лежащую в основе SPQR-дерева — трёхсвязные компоненты графа, и связь между таким разложением и планарными вложениями первым изучал Маклейн^[3]. Эти структуры другие исследователи использовали в эффективных алгоритмах^[4] до их формализации как SPQR-дерево Ди Батистой и Тамассиа^[5]^[6]^[7].

СтруктураПравить

SPQR-дерево имеет вид некорневого дерева, в котором для каждого узла x имеется ассоциированный неориентированный граф или мультиграф G_x. Узел и граф, ассоциированный с ним, могут быть одного из четырёх типов, дающих аббревиатуру SPQR:

Узел типа S (series = последовательное соединение), ассоциированный граф является циклом с тремя и более вершинами и рёбрами. Этот случай аналогичен последовательному соединению в параллельно-последовательных графах^[5].
Узел типа P (parallel = параллельное соединение), ассоциированный граф является диполем (двойственным графом цикла), мультиграфом с двумя вершинами и тремя и более рёбрами. Этот случай аналогичен параллельному соединению в параллельно-последовательных графах^[5].
Узел типа Q, ассоциированный граф имеет единственное ребро. Этот тривиальный случай нужен, чтобы работать с графами, состоящими из единственного ребра. В некоторых работах по SPQR-деревьям этот тип узла не появляется в SPQR-деревьях графов, имеющих более одного ребра. В других работах все невиртуальные рёбра требуется представить с помощью узлов типа Q с одним настоящим и одним виртуальным ребром, а все рёбра узлов других типов должны быть виртуальными.
Узел типа R (rigid = жёсткий), ассоциированный граф является 3-связным графом, не являющимся ни циклом, ни диполем. «Rigid» здесь означает, что при применении SPQR-деревьев для планарного вложения графа ассоциированный с узлом R граф имеет единственное планарное вложение^[5].

Каждое ребро xy между двумя узлами SPQR-дерева ассоциировано с двумя ориентированными виртуальными рёбрами, одно из которых находится в G_x, а другое — в G_y. Каждое ребро в графе G_x может быть виртуальным ребром максимум для одного ребра SPQR-дерева.

SPQR-дерево T представляет 2-связный граф G_T, образованный следующим образом. Если ребро xy SPQR-дерева связывает виртуальное ребро ab графа G_x с виртуальным ребром cd графа G_y, образуется больший граф путём слияния a и c в одну супервершину, слияния b и d в другую супервершину и удаления двух виртуальных рёбер. То есть больший граф является суммой по 2-кликам G_x и G_y. Продолжение такого склеивания каждого ребра SPQR дерева даёт граф G_T, порядок склеивания не влияет на результат. Каждая вершина в одном из графов G_x может быть ассоциирована таким путём с единственной вершиной в G_T, то есть супервершиной, в которую она была влита.

Обычно не разрешается, чтобы внутри SPQR-дерева были смежны ни два узла типа S, ни два узла типа P, поскольку при такой смежности два узла могут быть слиты в один больший узел. При таком требовании SPQR дерево единственным образом определяется графом и графы G_x, ассоциированные с узлами SPQR-дерева, известны как трёхсвязные компоненты графа G.

ПостроениеПравить

SPQR-дерево заданного вершинно 2-связного графа можно построить за линейное время^[1]^[2].

Задачу построения трёхсвязных компонент графа за линейное время первым решили Хопкрофт и Тарьян^[1]. Основываясь на этом алгоритме, Ди Баттиста и Тамассиа^[7] высказали предположение, что вся структура SPQR-дерева, а те только его компоненты, можно построить за линейного время. После того как имплементация более медленного алгоритма для SPQR-деревьев была включена в библиотеку GDToolkit, Гутвенгер и Мутцель ^[2] дали первую имплементацию линейного времени. Как часть процесса имплементации они исправили некоторые ошибки в более ранней работе Хопкрофта и Тарьяна^[1].

Алгоритм Гутвенгера и Мутцеля^[2] включает следующие шаги.

Сортируем рёбра графа по парам индексов его конечных вершин с помощью варианта поразрядной сортировки, совершающей два прохода блочной сортировки (по одному проходу для каждого конца). После этого параллельные рёбра будут стоять рядом в сортированном списке и могут быть отделены в P-узел конечного SPQR-дерева, что делает оставшийся граф простым.
Разбиваем граф на компоненты. Эти компоненты можно образовать путём нахождения пар разделяющих вершин и разбиения графа по этим двум вершинам на меньшие графы (со связанными парами виртуальных рёбер, имеющих разделяющие вершины в качестве конечных вершин). Процесс разбиения повторяется, пока остаются пары, по которым можно осуществить разбиение. Разбиение, полученное таким образом, не обязательно уникально, поскольку части графа, которые должны стать S-узлами SPQR-дерева разбиваются на несколько треугольников.
Помечаем каждую компоненту разбиения буквой P (двухвершинная компонента с кратными рёбрами), буквой S (компонента в виде треугольника) или R (любая другая компонента). Пока имеются две компоненты, имеющие общую связанную пару виртуальных рёбер, и обе компоненты имеют тип S или обе компоненты имеют тип P, сливаем эти компоненты в одну бо́льшую компоненту того же типа.

Гутвенгер и Мутцель^[2] используют поиск в глубину для поиска структуру, которую они называют «пальмой». Пальма строится на основе дерева поиска в глубину и имеет дуги дерева поиска с ориентацией от корня дерева к листьям, остальные дуги (листья пальмы) ориентированы к корню. Гутвенгер и Мутцель затем ищут специальный предпорядок нумерации узлов пальмы и используют определённые шаблоны в этой нумерации для идентификации пар вершин, которые могут разделить граф на меньшие компоненты. Если компонента найдена таким образом, для идентификации рёбер, которые должны быть частью новой компоненты, используется стек.

ИспользованиеПравить

Нахождение 2-вершинных сеченийПравить

С SPQR-деревом графа G (без Q узлов) можно напрямую найти каждую пару вершин u и v в графе G, удаление которых делает граф G несвязным, но оставляет связными компоненты:

Две вершины u и v могут быть двумя концами виртуального ребра в графе, ассоциированном с R-узлом. В этом случае две компоненты представлены двумя поддеревьями SPQR-дерева, получающихся после удаления ребра SPQR-дерева.
Две вершины u и v могут быть двумя вершинами в графе, ассоциированном с P-узлом, который имеет два и более виртуальных рёбер. В этом случае компоненты, образованные путём удаления u и v, представлены поддеревьями SPQR-дерева, по одной для каждого виртуального ребра в узле.
Две вершины u и v могут быть двумя вершинами в графе, ассоциированном с S-узлом, не смежным либо u, либо v, или ребро uv является виртуальным. Если ребро виртуально, то пара (u,v) принадлежит узлу типа P или R и компоненты описаны выше. Если две вершины не смежны S, то компоненты представлены двумя путями цикла, ассоциированного с узлом S и узлами SPQR-дерева, присоединёнными к этим двум путям.

Представление всех вложений планарных графовПравить

Если планарный граф 3-связен, он имеет единственное планарное вложение с точностью до выбора внешней грани и ориентации вложения — гранями вложения являются в точности циклы графа. Однако для 2-связных планарных графов (с помеченными вершинами и рёбрами), не являющихся 3-связными, может существовать бо́льшая свобода поиска планарного вложения. Конкретнее, если два узла SPQR-дерева графа соединены парой виртуальных рёбер, можно изменить ориентацию одного из рёбер относительно другого. Кроме того, в узле типа P SPQR-дерева различные части графа, связанные с виртуальными рёбрами узла P, могут быть произвольным образом переставлены. Все планарные представления графа могут быть описаны таким образом^[8].

См. такжеПравить

Дерево двусвязных компонент, похожая древесная структура для вершинно 2-связных компонент
Дерево Гомори — Ху^[en], другая древесная структура, описывающая рёбра связности графа
Древесная декомпозиция, обобщение до больших сечений

ПримечанияПравить

↑ ¹ ² ³ ⁴ Hopcroft, Tarjan, 1973.
↑ ¹ ² ³ ⁴ ⁵ Gutwenger, Mutzel, 2001.
↑ Mac Lane, 1937.
↑ Например, Хоркрофт и Тарьян (Hopcroft, Tarjan 1973), Бинсток и Монма (Bienstock, Monma 1988). Обе статьи цитировались как предшественники Ди Батистой и Тамассиа.
↑ ¹ ² ³ ⁴ Di Battista, Tamassia, 1989.
↑ Di Battista, Tamassia, 1990.
↑ ¹ ² Di Battista, Tamassia, 1996.
↑ Mac Lane (1937).

ЛитератураПравить

Bienstock D., Monma C. On the complexity of covering vertices by faces in a planar graph // SIAM Journal on Computing. — 1988. — Т. 17, вып. 1. — С. 53–76. — doi:10.1137/0217004.
Di Battista G., Tamassia R. Incremental planarity testing // Proc. 30th Annual Symposium on Foundations of Computer Science. — 1989. — С. 436–441. — doi:10.1109/SFCS.1989.63515.
Di Battista G., Tamassia R. On-line graph algorithms with SPQR-trees // Proc. 17th International Colloquium on Automata, Languages and Programming. — Springer-Verlag, 1990. — Т. 443. — С. 598–611. — (Lecture Notes in Computer Science). — doi:10.1007/BFb0032061.
Di Battista G., Tamassia R. On-line planarity testing // SIAM Journal on Computing. — 1996. — Т. 25, вып. 5. — С. 956–997. — doi:10.1137/S0097539794280736.
Gutwenger C., Mutzel P. A linear time implementation of SPQR-trees // Proc. 8th International Symposium on Graph Drawing (GD 2000). — Springer-Verlag, 2001. — Т. 1984. — С. 77–90. — (Lecture Notes in Computer Science). — doi:10.1007/3-540-44541-2_8.
Hopcroft J., Tarjan R. Dividing a graph into triconnected components. — SIAM Journal on Computing. — 1973. — Т. 2. — С. 135–158. — doi:10.1137/0202012.
Mac Lane S. A structural characterization of planar combinatorial graphs // Duke Mathematical Journal. — 1937. — Т. 3, вып. 3. — С. 460–472. — doi:10.1215/S0012-7094-37-00336-3.

СсылкиПравить

имплементация SPQR tree в Open Graph Drawing Framework.
имплементация трёхсвязных компонент в Java в библиотеке jBPT library (см. TCTree class).

[_a65d53b0313aee70-1] ¹ ² ³ ⁴ Hopcroft, Tarjan, 1973.

[_a82774db95840ac5-2] ¹ ² ³ ⁴ ⁵ Gutwenger, Mutzel, 2001.

[_bc4588aaced7f886-3] Mac Lane, 1937.

[4] Например, Хоркрофт и Тарьян (Hopcroft, Tarjan 1973), Бинсток и Монма (Bienstock, Monma 1988). Обе статьи цитировались как предшественники Ди Батистой и Тамассиа.

[_4cbf68be70ca74a2-5] ¹ ² ³ ⁴ Di Battista, Tamassia, 1989.

[_57f625f9a44cef68-6] Di Battista, Tamassia, 1990.

[_56574b7c7fed0416-7] ¹ ² Di Battista, Tamassia, 1996.

[FOOTNOTEMac_Lane1937-8] Mac Lane (1937).

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]