Дерево SPQR

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

В теории графов, разделе математики, трехсвязные компоненты двусвязного графа представляют собой систему меньших графов, которые описывают все 2-вершинные разрезы в графе. Дерево SPQR - это древовидная структура данных, используемая в информатике, а точнее в алгоритмах графа, для представления трехсвязных компонентов график. Дерево SPQR графа может быть построено за линейное время и имеет несколько применений в рисовании графа.

Базовые структуры, лежащие в основе дерева SPQR, трехсвязные компоненты графа и соединение между этим разложением и планарными вложениями плоского графа были впервые исследованы Сондерсом Мак Лейном (1937); эти структуры использовались в эффективных алгоритмах несколькими другими исследователями до их формализации в виде дерева SPQR Ди Баттиста и Тамассия (1989, 1990, 1996).

• 1 Структура
• 2 Конструкция
• 3 Использование
  • 3.1 Поиск 2-вершинных разрезов
  • 3.2 Представление всех вложений плоских графов
• 4 См. Также
• 5 Примечания
• 6 Ссылки
• 7 Внешние ссылки

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

• В узле S связанный граф представляет собой циклический граф с тремя или более вершинами и ребрами.. Этот случай аналогичен составлению серий в последовательно-параллельных графах ; S означает "серия".
• В узле P связанный граф представляет собой дипольный граф, мультиграф с двумя вершинами и тремя или более ребрами, плоский двойственный в график цикла. Этот случай аналогичен параллельной композиции в последовательно-параллельных графах ; P означает «параллельный».
• В узле Q связанный граф имеет единственное действительное ребро. Этот тривиальный случай необходим для работы с графом, имеющим только одно ребро. В некоторых работах по деревьям SPQR этот тип узла не появляется в деревьях SPQR графов с более чем одним ребром; в других работах все невиртуальные ребра должны быть представлены узлами Q с одним реальным и одним виртуальным ребром, а ребра в других типах узлов должны быть виртуальными.
• В узле R связанный граф - это 3-связный граф, который не является циклом или диполем. R означает «жесткий»: в применении деревьев SPQR при встраивании планарного графа связанный граф узла R имеет уникальное плоское вложение.

Каждое ребро 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 представлен деревом SPQR без смежных узлов P и без смежных узлов S, тогда графы G x, связанные с узлами дерева SPQR, известны как трехсвязные компоненты G.

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

Задача построения трехсвязных компонентов графа была впервые решена в линейное время Хопкрофт и Тарджан (1973). Основываясь на этом алгоритме, Ди Баттиста и Тамассия (1996) предположили, что полная древовидная структура SPQR, а не только список компонентов, должна быть построена за линейное время. После того, как реализация более медленного алгоритма для деревьев SPQR была предоставлена ​​как часть библиотеки GDToolkit, Gutwenger Mutzel (2001) предоставили первую реализацию линейного времени. В рамках этого процесса реализации этого алгоритма они также исправили некоторые ошибки в более ранней работе Hopcroft Tarjan (1973).

. Алгоритм Gutwenger Mutzel (2001) включает следующее общие шаги.

1. Сортировка ребер графа по парам числовых индексов их конечных точек, используя вариант radix sort, который выполняет два прохода bucket sort, по одному для каждой конечной точки. После этого шага сортировки параллельные ребра между теми же двумя вершинами будут смежными друг с другом в отсортированном списке и могут быть разделены на P-узел в конечном дереве SPQR, оставив оставшийся граф простым.
2. Разбить граф на отдельные компоненты; это графы, которые могут быть сформированы путем нахождения пары разделяющих вершин, разделения графа в этих двух вершинах на два меньших графа (со связанной парой виртуальных ребер, имеющих разделяющие вершины в качестве конечных точек), и повторения этого процесса разделения до тех пор, пока разделяющие пары существуют. Найденное таким образом разделение не определено однозначно, потому что части графа, которые должны стать S-узлами дерева SPQR, будут подразделены на несколько треугольников.
3. Пометьте каждый разделенный компонент буквой P (два -вершинный разделенный компонент с несколькими ребрами), S (разделенный компонент в форме треугольника) или R (любой другой разделенный компонент). Хотя существуют два разделенных компонента, которые имеют общую пару связанных виртуальных ребер, и оба компонента имеют тип S или оба имеют тип P, объедините их в один более крупный компонент того же типа.

Чтобы найти разделенные компоненты, Gutwenger Mutzel (2001) используют поиск в глубину, чтобы найти структуру, которую они называют пальмой; это дерево поиска в глубину с его ребрами , ориентированными от корня дерева для ребер, принадлежащих дереву, и к корню для всех остальных ребер. Затем они находят специальную нумерацию узлов в дереве preorder и используют определенные шаблоны в этой нумерации для определения пар вершин, которые могут разделить граф на более мелкие компоненты. Когда компонент найден таким образом, структура данных стека используется для идентификации ребер, которые должны быть частью нового компонента.

Поиск 2-вершинных разрезов

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

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

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

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

• Дерево сечений блоков, аналогичная древовидная структура для компонентов, связанных с двумя вершинами
• дерево Гомори – Ху, другая древовидная структура, которая характеризует связность ребер графа
• Древовидная декомпозиция, обобщение (больше не уникальное) на более крупные разрезы

• Bienstock, Daniel ; Монма, Клайд Л. (1988), «О сложности покрытия вершин гранями в плоском графе», SIAM Journal on Computing, 17 (1): 53–76, CiteSeerX 10.1.1.542.2314, doi : 10.1137 / 0217004.
• Ди Баттиста, Джузеппе; Тамассия, Роберто (1989), «Тестирование инкрементной планарности», Proc. 30-й ежегодный симпозиум по основам информатики, стр. 436–441, doi : 10.1109 / SFCS.1989.63515.
• Ди Баттиста, Джузеппе; Тамассия, Роберто (1990), «Алгоритмы онлайн-графов с SPQR-деревьями», Proc. 17-й Международный коллоквиум по автоматам, языкам и программированию, Lecture Notes in Computer Science, 443, Springer-Verlag, pp. 598–611, doi : 10.1007 / BFb0032061.
• Ди Баттиста, Джузеппе; Тамассия, Роберто (1996), «Онлайн-тестирование планарности» (PDF), SIAM Journal on Computing, 25 (5): 956–997, doi : 10.1137 / S0097539794280736.
• Гутвенгер, Карстен; Mutzel, Petra (2001), «Линейная временная реализация SPQR-деревьев», Proc. 8-й Международный симпозиум по рисованию графиков (GD 2000), Lecture Notes in Computer Science, 1984, Springer-Verlag, pp. 77–90, doi : 10.1007 / 3-540-44541-2_8.
• Хопкрофт, Джон ; Тарджан, Роберт (1973), «Разделение графа на трехсвязные компоненты», SIAM Journal on Computing, 2 (3): 135–158, doi : 10.1137 / 0202012, hdl : 1813/6037.
• Mac Lane, Saunders (1937), «Структурная характеристика плоских комбинаторных графов», Duke Mathematical Журнал, 3 (3): 460–472, doi : 10.1215 / S0012-7094-37-00336-3.

• Реализация дерева SPQR в Open Graph Drawing Framework.
• Дерево трехкомпонентной реализации Java компонентов в библиотеке jBPT (см. Класс TCTree).