Биполярная ориентация
В теории графов биполярная ориентация или st -ориентация неориентированного графа — это присвоение направления каждому ребру ( ориентация ), которое приводит к тому, что граф становится ориентированным ациклическим графом с одним источником s и одним стоком t , и st топологическое -нумерация графа представляет собой упорядочение полученного ориентированного ациклического графа. [1] [2]
Определения и существование
[ редактировать ]Пусть G = ( V , E ) — неориентированный граф с n = | В | вершины. Ориентация ориентированный G — это присвоение направления каждому ребру G , превращающее его в граф . Это ациклическая ориентация , если полученный ориентированный граф не имеет ориентированных циклов . Каждый ациклически ориентированный граф имеет хотя бы один источник (вершину без входящих ребер) и хотя бы один сток (вершину без исходящих ребер); это биполярная ориентация, если она имеет ровно один источник и ровно один сток. В некоторых ситуациях G может быть задан вместе с двумя обозначенными вершинами s и t ; в этом случае биполярная ориентация s и t должна иметь s в качестве единственного источника и t в качестве уникального стока. [1] [2]
St G -нумерация графа ( опять же с двумя обозначенными вершинами s и t ) — это присвоение целых чисел от 1 до n вершинам 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] В одном направлении, если этот граф 2-связен, то биполярную ориентацию можно получить, последовательно ориентируя каждое ухо при ушном разложении графа. [4] В другом направлении, если граф не является 2-вершинно связным, то он имеет вершину сочленения v, отделяющую некоторый двусвязный компонент G от s и t . Если этот компонент содержит вершину с меньшим номером, чем v , то вершина с наименьшим номером в компоненте не может иметь соседа с меньшим номером, и симметрично, если он содержит вершину с более высоким номером, чем v , тогда вершина с наибольшим номером в компонент не может иметь соседа с более высоким номером.
Приложения к планарности
[ редактировать ]Лемпель, Эвен и Седербаум (1967) сформулировали st -нумерацию как часть проверки планарности алгоритма : [3] и Розенштиль и Тарьян (1986) сформулировали биполярные ориентации как часть алгоритма построения мозаичных представлений плоских графов . [1]
Биполярная ориентация планарного графа приводит к созданию st -планарного графа , ориентированного ациклического планарного графа с одним источником и одним стоком. Эти графы имеют определенное значение в теории решеток, также в рисовании графов : диаграмма Хассе двумерной а решетки обязательно является st -планарной, и каждый транзитивно редуцированный st -планарный граф таким образом представляет собой двумерную решетку. [5] Ориентированный ациклический граф G имеет планарный рисунок вверх тогда и только тогда, когда G является подграфом st -планарного графа. [6]
Алгоритмы
[ редактировать ]Можно найти st -нумерацию и биполярную ориентацию данного графа с обозначенными вершинами s и t за линейное время , используя поиск в глубину . [7] [8] [9] Алгоритм Тарьяна (1986) использует поиск в глубину, который начинается с вершины s и сначала пересекает ребро st . Как и в алгоритме поиска в глубину для проверки двусвязности графа, этот алгоритм определяет pre( v ) для вершины v как предварительный номер v при обходе в глубину и low( v ) быть наименьшим номером предварительного порядка, которого можно достичь, следуя по одному ребру от потомка v в дереве поиска в глубину. Оба этих числа могут быть вычислены за линейное время как часть поиска в глубину. Данный граф будет двусвязным (и будет иметь биполярную ориентацию) тогда и только тогда, когда t является единственным дочерним элементом s в дереве поиска в глубину и low( v ) < pre( v ) для всех вершин v, отличных от s . После того, как эти числа вычислены, алгоритм Тарьяна выполняет второй обход дерева поиска в глубину, сохраняя числовой знак ( v ) для каждой вершины v и связанный список вершин, который в конечном итоге будет перечислять все вершины графа в порядке предоставленный ст - нумерация. Первоначально список содержит s и t и знак( s ) = −1. Когда каждая вершина v впервые встречается при этом втором обходе, v вставляется в список либо до, либо после ее родительского элемента p( v ) в дереве поиска в глубину в зависимости от того, является ли знак(low( v )) отрицательным или положительным. соответственно; тогда знак(p( v )) устанавливается в -sign(low( v )). Как показывает Тарьян, порядок вершин, полученный в результате этой процедуры, дает st -нумерацию данного графа. [9]
Альтернативно, эффективные последовательные и параллельные алгоритмы могут быть основаны на ушной декомпозиции . [4] [10] [11] Хотя приведенные выше алгоритмы на основе DFS по своей сути зависят от специальной декомпозиции с открытым ухом, вызванной базовым деревом DFS, декомпозиция с открытым ухом здесь может быть произвольной. Этот более общий подход фактически используется в нескольких приложениях, например, для вычисления независимых (от ребер) остовных деревьев. Разложение открытого уха существует тогда и только тогда, когда граф, образованный из данного графа добавлением ребра st, является двусвязным (то же условие, что и существование биполярной ориентации) и может быть найден за линейное время. St - ориентацию (и, следовательно, также st -нумерацию) можно легко получить, направляя каждое ухо в одном и том же направлении, следя за тем, чтобы, если уже существует направленный путь, соединяющий одни и те же две конечные точки между краями предыдущих ушей, тогда новый ухо должно быть ориентировано в одном направлении. Однако, несмотря на простоту этого фольклорного подхода, получение линейного времени работы является более сложным. Всякий раз, когда добавляется ухо, конечные точки этого уха должны проверяться на достижимость или, что то же самое, на предмет st -нумерация, какая вершина стоит первой в предварительной st -нумерации перед. Это препятствие можно решить в худшем случае с постоянным временем, используя (несколько сложную) структуру данных порядка , [11] или более прямыми методами. Маон, Шибер и Вишкин (1986) предлагают сложную, но локализованную процедуру поиска для определения подходящей ориентации для каждого уха, которая (в отличие от подхода, использующего поиск в глубину) подходит для параллельных вычислений. [4]
Современный и простой алгоритм, вычисляющий st -нумерации и -ориентации за линейное время, приведен в . [11] Идея этого алгоритма состоит в том, чтобы заменить структуру данных порядка простой схемой нумерации, в которой вершины содержат интервалы вместо st -номеров.
Папаманту и Толлис (2006) сообщают об алгоритмах управления длинами направленных путей в биполярной ориентации данного графа, что, в свою очередь, приводит к некоторому контролю над шириной и высотой некоторых типов отрисовки графа . [12]
Пространство всех ориентаций
[ редактировать ]Для 3-связных графов с обозначенными вершинами s и t любые две биполярные ориентации могут быть соединены друг с другом с помощью последовательности операций, которые меняют местами одно ребро за раз, на каждом этапе сохраняя биполярную ориентацию. [2] Более строго, для плоских 3-связных графов множеству биполярных ориентаций можно придать структуру конечной дистрибутивной решетки с операцией обращения ребер, соответствующей накрывающему отношению решетки. [2] Для любого графа с обозначенным источником и приемником набор всех биполярных ориентаций может быть указан в полиномиальном времени для каждой ориентации. [2]
st -нумерация и -ориентация ребер
[ редактировать ]Можно построить порядок, аналогичный st -нумерации, нумеруя ребра вместо вершин. Это эквивалентно st -нумерации линейного графика входного графа. Хотя явное построение линейного графа займет квадратичное время, известны алгоритмы с линейным временем для вычисления нумерации st -ребер и ориентации st -ребер графа. [11]
См. также
[ редактировать ]- Выпуклое вложение , многомерное обобщение биполярных ориентаций.
Ссылки
[ редактировать ]- ^ Jump up to: а б с д и Розенштиль, Пьер ; Тарьян, Роберт Э. (1986), «Прямолинейные плоские макеты и биполярные ориентации плоских графов», Дискретная и вычислительная геометрия , 1 (4): 343–353, doi : 10.1007/BF02187706 , MR 0866369 .
- ^ Jump up to: а б с д и ж г час де Фрессе, Юбер; Оссона де Мендес, Патрис ; Розенштиль, Пьер (1995), «Возвращение к биполярным ориентациям», Discrete Applied Mathematics , 56 (2–3): 157–179, doi : 10.1016/0166-218X(94)00085-R , MR 1318743 .
- ^ Jump up to: а б с Лемпель, А. ; Эвен, С .; Седербаум, И. (1967), «Алгоритм проверки планарности графов», Теория графов (Международный симпозиум, Рим, 1966) , Нью-Йорк: Гордон и Брич, стр. 215–232, MR 0220617 .
- ^ Jump up to: а б с Маон, Ю.; Шибер, Б.; Вишкин, У. (1986), «Поиск с разложением параллельного уха (EDS) и нумерация ST в графиках», Theoretical Computer Science , 47 (3): 277–298, doi : 10.1016/0304-3975(86)90153-2 , МР 0882357 .
- ^ Платт, CR (1976), «Плоские решетки и плоские графы», Журнал комбинаторной теории , сер. Б, 21 (1): 30–39, doi : 10.1016/0095-8956(76)90024-1 .
- ^ Ди Баттиста, Джузеппе; Тамассиа, Роберто (1988), «Алгоритмы для плоских представлений ациклических орграфов», Theoretical Computer Science , 61 (2–3): 175–198, doi : 10.1016/0304-3975(88)90123-5 .
- ^ Эберт, Дж. (1983), « st -упорядочение вершин двусвязных графов», Computing , 30 (1): 19–33, doi : 10.1007/BF02253293 , MR 0691948 , S2CID 6570953 .
- ^ Даже Шимон ; Тарьян, Роберт Эндре (1976), «Вычисление нумерации st », Theoretical Computer Science , 2 (3): 339–344, doi : 10.1016/0304-3975(76)90086-4 , MR 0414406 .
- ^ Jump up to: а б Тарьян, Роберт Эндре (1986), «Два оптимизированных алгоритма поиска в глубину» (PDF) , Fundamenta Informaticae , 9 (1): 85–94, doi : 10.3233/FI-1986-9105 , MR 0848212 .
- ^ Газит, Гилель (1991), "Оптимальные параллельные алгоритмы EREW для связности, ушной декомпозиции и нумерации st плоских графов", Proc. 5-й Международный симпозиум по параллельной обработке , стр. 84–91, doi : 10.1109/IPPS.1991.153761 , S2CID 34959564 .
- ^ Jump up to: а б с д Шлипф, Лена; Шмидт, Йенс М. (2019), «Простое вычисление нумерации st-ребер и st на основе разложения уха», Information Processing Letters , 145 : 58–63, doi : 10.1016/j.ipl.2019.01.008 , S2CID 71714734 .
- ^ Папаманту, Харалампос; Толлис, Иоаннис Г. (2006), «Применение параметризованных st -ориентаций в алгоритмах рисования графов» (PDF) , Рисование графиков: 13-й Международный симпозиум, GD 2005, Лимерик, Ирландия, 12–14 сентября 2005 г., Пересмотренные статьи , Лекция Заметки по информатике, том. 3843, Берлин: Springer, стр. 355–367, номер документа : 10.1007/11618058_32 , MR 2244524 .