Граф и его дерево SPQR. Пунктирные черные линии соединяют пары виртуальных ребер, показанных черным цветом; остальные ребра окрашены в соответствии с трехсвязным компонентом, к которому они принадлежат.
В теории графов , разделе математики, трисвязные компоненты двусвязного графа представляют собой систему меньших графов, которые описывают все 2-вершинные разрезы в графе. Дерево SPQR представляет собой древовидную структуру данных, используемую в информатике , а точнее в алгоритмах графов , для представления трисвязных компонентов графа. Дерево SPQR графа может быть построено за линейное время [1] и имеет несколько применений в динамических алгоритмах графов и рисовании графов .
Базовые структуры, лежащие в основе дерева SPQR, трехсвязные компоненты графа и связь между этим разложением и планарными вложениями планарного графа , были впервые исследованы Сондерсом Маклейном (1937); эти структуры использовались в эффективных алгоритмах несколькими другими исследователями [2] до их формализации в качестве дерева SPQR Ди Баттистой и Тамассией (1989, 1990, 1996).
Структура
Дерево SPQR принимает форму некорневого дерева , в котором для каждого узла x связан неориентированный граф или мультиграф G x . Узел и связанный с ним граф могут иметь один из четырех типов, учитывая инициалы SPQR:
В узле S ассоциированный граф является графом цикла с тремя или более вершинами и ребрами. Этот случай аналогичен композиции серий в последовательно-параллельных графах ; S означает «серия». [3]
В узле Q связанный граф имеет одно реальное ребро. Этот тривиальный случай необходим для обработки графа, имеющего только одно ребро. В некоторых работах по деревьям SPQR этот тип узла не появляется в деревьях SPQR графов с более чем одним ребром; в других работах все невиртуальные ребра должны быть представлены узлами Q с одним реальным и одним виртуальным ребром, а ребра в других типах узлов должны быть все виртуальными.
В узле R ассоциированный граф — это 3-связный граф, который не является циклом или диполем. R означает «жесткий»: при применении деревьев SPQR в планарном графовом вложении ассоциированный граф узла R имеет уникальное планарное вложение. [3]
Каждое ребро 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-вершинно-связного графа может быть построено за линейное время . [1]
Задача построения трехсвязных компонентов графа была впервые решена за линейное время Хопкрофтом и Тарьяном (1973). Основываясь на этом алгоритме, Ди Баттиста и Тамассиа (1996) предположили, что полная структура дерева SPQR, а не только список компонентов, должна быть построена за линейное время. После того, как реализация более медленного алгоритма для деревьев SPQR была предоставлена как часть библиотеки GDToolkit, Гутвенгер и Мутцель (2001) предоставили первую реализацию за линейное время. В рамках этого процесса реализации этого алгоритма они также исправили некоторые ошибки в более ранней работе Хопкрофта и Тарьяна (1973).
Алгоритм Гутвенгера и Мутцеля (2001) включает следующие общие шаги.
Отсортируйте ребра графа по парам числовых индексов их конечных точек, используя вариант сортировки по радиусу , который делает два прохода сортировки ведром , по одному для каждой конечной точки. После этого шага сортировки параллельные ребра между теми же двумя вершинами будут соседствовать друг с другом в отсортированном списке и могут быть разделены на P-узел конечного дерева SPQR, оставляя оставшийся граф простым.
Разделить граф на разделенные компоненты; это графы, которые можно сформировать, найдя пару разделяющих вершин, разделив граф в этих двух вершинах на два меньших графа (со связанной парой виртуальных ребер, имеющих разделяющие вершины в качестве конечных точек), и повторяя этот процесс разделения до тех пор, пока не останется больше разделяющих пар. Разделение, найденное таким образом, не является однозначно определенным, поскольку части графа, которые должны стать S-узлами дерева SPQR, будут подразделены на несколько треугольников.
Пометьте каждый разделенный компонент буквой P (разделенный компонент с двумя вершинами и несколькими ребрами), S (разделенный компонент в форме треугольника) или R (любой другой разделенный компонент). Пока существуют два разделенных компонента, которые разделяют связанную пару виртуальных ребер, и оба компонента имеют тип S или оба имеют тип P, объедините их в один более крупный компонент того же типа.
Чтобы найти разделенные компоненты, Гутвенгер и Мутцель (2001) используют поиск в глубину , чтобы найти структуру, которую они называют пальмовым деревом; это дерево поиска в глубину, ребра которого ориентированы от корня дерева, для ребер, принадлежащих дереву, и по направлению к корню для всех остальных ребер. Затем они находят специальную предпорядковую нумерацию узлов в дереве и используют определенные шаблоны в этой нумерации для определения пар вершин, которые могут разделить граф на более мелкие компоненты. Когда компонент находится таким образом, структура данных стека используется для определения ребер, которые должны быть частью нового компонента.
Использование
Нахождение разрезов по 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, могут быть произвольно переставлены . Все планарные представления могут быть описаны таким образом. [4]
Дерево Гомори–Ху , другая древовидная структура, характеризующая связность ребер графа.
Разложение дерева , обобщение (больше не уникальное) для более крупных разрезов
Примечания
^ аб Хопкрофт и Тарьян (1973); Гутвенгер и Мутцель (2001).
^ Например, Hopcroft & Tarjan (1973) и Bienstock & Monma (1988), оба из которых упоминаются Ди Баттистой и Тамассией как прецеденты.
^ abc Ди Баттиста и Тамассия (1989).
↑ Мак Лейн (1937).
Ссылки
Бьенсток, Дэниел; Монма, Клайд Л. (1988), «О сложности покрытия вершин гранями в плоском графе», SIAM Journal on Computing , 17 (1): 53–76, CiteSeerX 10.1.1.542.2314 , doi : 10.1137/0217004.
Хопкрофт, Джон ; Тарьян, Роберт (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).
