SPQR-дерево

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

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

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

Структура

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

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

Каждому ребру xy между двумя узлами дерева SPQR сопоставлены два направленных виртуальных ребра , одно из которых является ребром в G _x , а другое - ребро в G _y . Каждое ребро в графе G _x может быть виртуальным ребром не более чем для одного ребра дерева SPQR.

дерево T представляет собой 2-связный граф GT _{SPQR -} , сформированный следующим образом. Всякий раз, когда ребро дерева SPQR xy связывает виртуальное ребро ab графа G _x с виртуальным ребром cd графа G _y , сформируйте один больший граф, объединив a и c в одну супервершину, объединив b и d в другую одну супервершину и удалив две виртуальные края. То есть больший граф представляет собой 2-кликовую сумму G _x и G _y . Выполнение этого шага склеивания на каждом ребре дерева SPQR дает граф G _T ; порядок выполнения этапов приклеивания не влияет на результат. из графов Gx _. может быть связана таким образом с уникальной вершиной в GT _{Каждая вершина в одном} , супервершиной, с которой она была объединена

Как правило, в дереве SPQR не допускается соседство двух узлов S или соседство двух узлов P, поскольку в случае возникновения такой смежности два узла могут быть объединены в один более крупный узел. При таком предположении дерево SPQR однозначно определяется по его графику. Когда граф G представлен деревом SPQR без соседних узлов P и без соседних узлов S, тогда графы G _x, связанные с узлами дерева SPQR, известны как трехсвязные компоненты G .

Строительство

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

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

Алгоритм Гутвенгера и Мутцеля (2001) включает следующие общие этапы.

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

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

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

Нахождение двухвершинных разрезов

С помощью 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, могут быть произвольно переставлены . Таким образом можно описать все плоские представления.

См. также

• Блочное дерево , аналогичная древовидная структура для 2-связных компонентов.
• Дерево Гомори – Ху , другая древовидная структура, которая характеризует связность ребер графа.
• Разложение дерева , обобщение (уже не уникальное) на более крупные разрезы

Ссылки

• Биншток, Дэниел; Монма, Клайд Л. (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 , ISBN  0-8186-1982-1 .
• Ди Баттиста, Джузеппе; Тамассиа, Роберто (1990), «Алгоритмы на онлайн-графах с SPQR-деревьями», Proc. 17-й международный коллоквиум по автоматам, языкам и программированию , Конспекты лекций по информатике , том. 443, Springer-Verlag, стр. 598–611, номер документа : 10.1007/BFb0032061 , ISBN.  978-3-540-52826-5 .
• Ди Баттиста, Джузеппе; Тамассиа, Роберто (1996), «Онлайн-тестирование планарности» (PDF) , SIAM Journal on Computing , 25 (5): 956–997, doi : 10.1137/S0097539794280736 .
• Гутвенгер, Карстен; Мутцель, Петра (2001), «Реализация SPQR-деревьев с линейным временем», Proc. 8-й Международный симпозиум по рисованию графов (GD 2000) , Конспекты лекций по информатике, том. 1984, Springer-Verlag, стр. 77–90, номер документа : 10.1007/3-540-44541-2_8 , ISBN.  978-3-540-41554-1 .
• Хопкрофт, Джон ; Тарьян, Роберт (1973), «Разделение графа на трехсвязные компоненты», SIAM Journal on Computing , 2 (3): 135–158, doi : 10.1137/0202012 , hdl : 1813/6037 .
• Мак Лейн, Сондерс (1937), «Структурная характеристика плоских комбинаторных графов», Duke Mathematical Journal , 3 (3): 460–472, doi : 10.1215/S0012-7094-37-00336-3 .

Внешние ссылки

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