SPQR-дерево

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

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

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

Структура[править | править код]

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

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

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

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

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

Построение[править | править код]

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

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

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

  1. Сортируем рёбра графа по парам индексов его конечных вершин с помощью варианта поразрядной сортировки, совершающей два прохода блочной сортировки (по одному проходу для каждого конца). После этого параллельные рёбра будут стоять рядом в сортированном списке и могут быть отделены в P-узел конечного SPQR-дерева, что делает оставшийся граф простым.
  2. Разбиваем граф на компоненты. Эти компоненты можно образовать путём нахождения пар разделяющих вершин и разбиения графа по этим двум вершинам на меньшие графы (со связанными парами виртуальных рёбер, имеющих разделяющие вершины в качестве конечных вершин). Процесс разбиения повторяется, пока остаются пары, по которым можно осуществить разбиение. Разбиение, полученное таким образом, не обязательно уникально, поскольку части графа, которые должны стать S-узлами SPQR-дерева разбиваются на несколько треугольников.
  3. Помечаем каждую компоненту разбиения буквой 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, могут быть произвольным образом переставлены. Все планарные представления графа могут быть описаны таким образом[3].

См. также[править | править код]

Примечания[править | править код]

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

Литература[править | править код]

  • 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.

Ссылки[править | править код]

Источник — https://ru.wikipedia.org/w/index.php?title=SPQR-дерево&oldid=119266935