Биполярная ориентация
Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

В теории графов , A биполярная ориентацией или й -ориентация из неориентированного графа является присвоением каждого направления к краю (AN ориентации ) , что приводит к тому , графику стать ориентированным ациклическим графом с одним источником ы и один умывальником т , и й -numbering графы является топологическим упорядочением результирующего направленного ациклического графа. [1] [2]

Определения и существование

Пусть G  = ( V , E ) - неориентированный граф с n  = | V | вершины. Ориентации из G является присвоение направлению к каждому краю G , что делает его в ориентированный граф . Это ациклическая ориентация, если полученный ориентированный граф не имеет ориентированных циклов . Каждый ациклически ориентированный граф имеет хотя бы один источник (вершину без входящих ребер) и хотя бы один сток (вершину без исходящих ребер); это биполярная ориентация, если она имеет ровно один источник и ровно один сток. В некоторых ситуацияхG может быть задана вместе с двумя обозначенными вершинами s и t ; в этом случае биполярная ориентация для s и t должна иметь s в качестве уникального источника и t в качестве уникального стока. [1] [2]

Й -numbering из G (опять же , с двумя вершинами , назначенные ей и т ) является присвоение целых чисел от 1 до п к вершинам G , таким образом, что

  • каждой вершине присваивается отдельный номер,
  • s присваивается номер 1,
  • t присваивается номер n , а
  • если вершине v присваивается номер i с 1 <  i  <  n , то по крайней мере одному соседу v назначается меньшее число, чем i, и по крайней мере одному соседу v назначается большее число, чем i . [1] [2] [3]

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

Связный граф G с обозначенными вершинами s и t имеет биполярную ориентацию и st -нумерацию тогда и только тогда, когда граф, образованный из G путем добавления ребра из s в t, является 2-вершинно-связным . [3] В одном направлении, если этот граф связан с двумя вершинами, то биполярная ориентация может быть получена путем согласованного ориентирования каждого уха в разложении уха графа. [4] В противном случае, если граф не является 2-вершинно-связным, то он имеет вершину сочленения v, разделяющую некоторую двусвязную компоненту Gот с и т . Если этот компонент содержит вершину с меньшим номером, чем v , тогда вершина с наименьшим номером в компоненте не может иметь соседа с меньшим номером, и симметрично, если она содержит вершину с более высоким номером, чем v, то вершина с наибольшим номером в компонент не может иметь соседа с более высоким номером.

Приложения к планарности

Лемпели, даже и Цедербаум (1967) сформулирована ул -numberings как часть планарности тестирования алгоритма , [3] и Rosenstiehl & Тарьян (1986) сформулирована биполярных ориентация в качестве части алгоритма для построения тесселяции представлений о плоских графах . [1]

Биполярная ориентация плоского графа приводит к st -планарному графу , ориентированному ациклическому планарному графу с одним источником и одним стоком. Эти графики имеют определенное значение в решетчатой теории , а также в графике рисунка : Диаграмма Хассе из двумерной решетки обязательно й -planar, и каждый транзитивно уменьшенный улица -planar график представляет собой двумерную решетку таким образом. [5] Ориентированный ациклический граф G имеет планарный рисунок вверх тогда и только тогда, когда G является подграфом st -планарного графа.[6]

Алгоритмы

Можно найти st- нумерацию и биполярную ориентацию данного графа с обозначенными вершинами s и t за линейное время, используя поиск в глубину . [7] [8] [9] Алгоритм Tarjan (1986) использует поиск в глубину, который начинается в вершине s и сначала проходит по ребру st . Как и в алгоритме на основе поиска в глубину для проверки двусвязности графа, этот алгоритм определяет pre ( v ) для вершины v как номер предварительного порядка v при обходе в глубину и low (v ) быть наименьшим номером предварительного заказа, которого можно достичь, следуя единственному ребру от потомка v в дереве поиска в глубину. Оба эти числа могут быть вычислены за линейное время как часть поиска в глубину. Данный граф будет двусвязным (и будет иметь биполярную ориентацию) тогда и только тогда, когда t будет единственным потомком s в дереве поиска в глубину и low ( v ) <pre ( v ) для всех вершин v, кроме  s . После того, как эти числа были вычислены, алгоритм Тарьяна выполняет второй обход дерева поиска в глубину, сохраняя знак числа ( v ) для каждой вершины.v и связанный список вершин, который в конечном итоге перечислит все вершины графа в порядке, заданном st -нумерацией. Изначально список содержит s и t , а sign ( s ) = −1. Когда каждая вершина v впервые встречается при этом втором обходе, v вставляется в список либо до, либо после ее родительского p ( v ) в дереве поиска в глубину в зависимости от того, является ли знак (low ( v )) отрицательным или положительным. соответственно; тогда sign (p ( v )) устанавливается в -sign (low ( v )). Как показывает Тарьян, порядок вершин, полученный в результате этой процедуры, дает st-нумерация данного графа. [9]

В качестве альтернативы, эффективные последовательные и параллельные алгоритмы могут быть основаны на разложении ушей . [4] [10] [11] Хотя описанные выше алгоритмы на основе DFS по своей сути зависят от специальной декомпозиции открытого уха, вызванной лежащим в основе DFS-деревом, разложение открытого уха здесь может быть произвольным. Этот более общий подход фактически используется несколькими приложениями, например, для вычисления (не зависящих от ребер) покрывающих деревьев. Разложение открытого уха существует тогда и только тогда, когда граф, сформированный из данного графа добавлением ребра st, является двусвязным (то же условие, что и существование биполярной ориентации), и его можно найти за линейное время. Й -ориентация (и , таким образом , также ул-нумерация) может быть легко получена путем направления каждого уха в постоянном направлении, заботясь о том, что если уже существует направленный путь, соединяющий те же две конечные точки между краями предыдущих ушей, то новое ухо должно быть ориентировано в том же направлении. Однако, несмотря на простоту этого фольклорного подхода, получение линейного времени выполнения более сложно. Каждый раз, когда добавляется ухо, необходимо проверять его конечные точки на достижимость или, что эквивалентно, для st- нумерации, какая вершина идет первой в предварительной st- нумерации ранее. Это препятствие может быть решено в худшем случае постоянная времени с помощи (несколько вовлеченных) структурой данных для того , [11] , или более прямыми методами.Маон, Шибер и Вишкин (1986) предоставляют сложную, но локализованную процедуру поиска для определения подходящей ориентации для каждого уха, которая (в отличие от подхода с использованием поиска в глубину) подходит для параллельных вычислений. [4]

Современный и простой алгоритм, вычисляющий st -нумерацию и -ориентацию за линейное время, приведен в [11] . Идея этого алгоритма состоит в замене упорядоченной структуры данных простой схемой нумерации, в которой вершины несут интервалы вместо st - числа.

Papamanthou & Tollis (2006) сообщают об алгоритмах управления длиной направленных путей в биполярной ориентации данного графа, что, в свою очередь, приводит к некоторому контролю над шириной и высотой определенных типов рисования графа . [12]

Пространство всех ориентаций

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

й -Станки-нумерации и -orientations

Можно построить порядок, аналогичный st -нумерации, путем нумерации ребер вместо вершин. Это эквивалентно st -нумерации линейного графика входного графа. Несмотря на то, построение линии-граф явно бы квадратичное время, алгоритмы линейного времени для вычисления й -Станок-нумерации и й -Станок-ориентации графа известны. [11]

Смотрите также

  • Выпуклое вложение , многомерное обобщение биполярных ориентаций

использованная литература

  1. ^ a b c d e Rosenstiehl, Пьер ; Тарьян, Роберт Е. (1986), "плоские макеты Прямолинейных и биполярные ориентации плоских графов", Дискретные и вычислительная геометрия , 1 (4): 343-353, DOI : 10.1007 / BF02187706 , МР  0866369.
  2. ^ a b c d e f g h де Фрейссе, Юбер; Оссона де Мендес, Патрис ; Rosenstiehl, Пьер (1995), "Bipolar ориентация вновь", Дискретная прикладная математика , 56 (2-3): 157-179, DOI : 10.1016 / 0166-218X (94) 00085-Р , МР 1318743 .
  3. ^ а б в Лемпель, А .; Даже, С .; Седербаум, I. (1967), "Алгоритм для проверки планарности графов", Теория графов (Internat. Sympos., Рим, 1966) , Нью-Йорк: Гордон и Бреч, стр. 215–232, MR 0220617 .
  4. ^ a b c Maon, Y .; Schieber, B .; Vishkin, У. (1986), "Параллельный поиск разложения уха (EDS) и ST-нумерация в графах", Теоретическая информатика , 47 (3): 277-298, DOI : 10,1016 / 0304-3975 (86) 90153-2 , MR 0882357 .
  5. ^ Платт, CR (1976), "Плоские решетки и плоские графы", Журнал комбинаторной теории , сер. В, 21 (1): 30–39, DOI : 10.1016 / 0095-8956 (76) 90024-1.
  6. ^ Ди Баттиста, Джузеппе; Tamassia, Роберто (1988), "Алгоритмы для плоских представлений ациклических орграфов", Теоретическая информатика , 61 (2-3): 175-198, DOI : 10,1016 / 0304-3975 (88) 90123-5.
  7. ^ Эберт, J. (1983), " й -ordering вершины двусвязных графов", Вычислительный , 30 (1): 19-33, DOI : 10.1007 / BF02253293 , МР 0691948 .
  8. ^ Даже, Шимон ; Тарьян, Роберт Эндре (1976), "вычисления ул -numbering", Теоретическая информатика , 2 (3): 339-344, DOI : 10,1016 / 0304-3975 (76) 90086-4 , MR 0414406 .
  9. ^ Б Тарьян Роберт Эндре (1986), "Два упорядочена по глубине первых алгоритмов поиска" (PDF) , Fundamenta Informaticae , 9 (1): 85-94, DOI : 10,3233 / FI-1986-9105 , MR 0848212  .
  10. ^ Газит, Хиллель (1991), "Оптимальные параллельные алгоритмы EREW для связности, разложения уха и нумерации плоских графов", Proc. 5 - й Международный симпозиум по параллельной обработке , С. 84-91,. DOI : 10,1109 / IPPS.1991.153761.
  11. ^ a b c d Шлипф, Лена; Шмидт, Йенс М. (2019), «Простое вычисление st-рёбер- и st-нумерации из разложений уха», Information Processing Letters , 145 : 58–63, doi : 10.1016 / j.ipl.2019.01.008.
  12. ^ Папаманту, Харалампос; Толлис, Иоаннис Г. (2006), «Приложения параметризованных st- ориентаций в алгоритмах рисования графов» (PDF) , Отрисовка графов: 13-й Международный симпозиум, GD 2005, Лимерик, Ирландия, 12–14 сентября 2005 г., Revised Papers , Lecture Примечания по информатике, 3843 , Берлин: Springer., С. 355-367, DOI : 10.1007 / 11618058_32 , MR 2244524  .
Источник « https://en.wikipedia.org/w/index.php?title=Bipolar_orientation&oldid=1032099113 »
Contribute a better translation