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

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

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

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

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

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

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

Дерево SPQR T представляет собой 2-связный граф G T , сформированный следующим образом. Всякий раз , когда SPQR дерево края ху связывает виртуальный ребро AB из G х с виртуальным краем кд из G у , образуют одну большую граф путем слияния и гр в одну supervertex, слияние б и д в другой одной supervertex, и удаление двух виртуальные края. То есть, чем больше графа является 2-клика суммы из G х и О у. Выполнение этого шага склейки на каждом ребре SPQR-дерева дает граф G T ; порядок выполнения этапов склейки не влияет на результат. Каждая вершина в одном из графов G x может быть связана таким образом с уникальной вершиной в G T , супервершине, с которой она была объединена.

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

Строительство [ править ]

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

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

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

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

Чтобы найти разделенные компоненты, Gutwenger & Mutzel (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]

См. Также [ править ]

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

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

  1. ^ а б Хопкрофт и Тарджан (1973) ; Гутвенгер и Мутцель (2001) .
  2. ↑ Например, Hopcroft & Tarjan (1973) и Bienstock & Monma (1988) , оба из которых цитируются как прецеденты Ди Баттиста и Тамассия.
  3. ^ a b c Ди Баттиста и Тамассия (1989) .
  4. Перейти ↑ Mac Lane (1937) .

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

  • Бинсток, Дэниел; Monma, Клайд Л. (1988), "О сложности покрытия вершины гранями в плоском графе", SIAM журнал по вычислениям , 17 (1): 53-76, CiteSeerX  10.1.1.542.2314 , DOI : 10,1137 / 0217004.
  • Ди Баттиста, Джузеппе; Tamassia, Роберто (1989), "Тестирование возрастающей планарности", Proc. Тридцатый ежегодный симпозиум по Основы информатики ., Стр 436-441, DOI : 10,1109 / SFCS.1989.63515.
  • Ди Баттиста, Джузеппе; Тамассия, Роберто (1990), "Алгоритмы онлайн-графов с SPQR-деревьями", Proc. 17-й Международный коллоквиум по автоматам, языкам и программированию , конспект лекций по информатике , 443 , Springer-Verlag, стр. 598–611, doi : 10.1007 / BFb0032061.
  • Ди Баттиста, Джузеппе; Tamassia, Роберто (1996), "Онлайн плоскостность тестирование" (PDF) , SIAM журнал по вычислениям , 25 (5): 956-997, DOI : 10,1137 / S0097539794280736.
  • Гутвенгер, Карстен; Mutzel, Petra (2001), "Линейная временная реализация SPQR-деревьев", Proc. 8-й Международный симпозиум по рисованию графиков (GD 2000) , конспект лекций по информатике, 1984 , Springer-Verlag, стр. 77–90, doi : 10.1007 / 3-540-44541-2_8.
  • Хопкрофт, Джон ; Тарьян, Роберт (1973), "Разделение графа на трехсвязные компоненты", SIAM журнал по вычислениям , 2 (3): 135-158, DOI : 10,1137 / 0202012 , ЛВП : 1813/6037.
  • Mac Lane, Saunders (1937), "Структурная характеристика плоских комбинаторных графов", Дюк математический журнал , 3 (3): 460-472, DOI : 10,1215 / S0012-7094-37-00336-3.

Внешние ссылки [ править ]

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