В теории графов биполярная ориентация или 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 так, что
Граф имеет биполярную ориентацию тогда и только тогда, когда он имеет 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 и связанный список вершин, который в конечном итоге будет перечислять все вершины графа в порядке заданной st -нумерацией. Первоначально список содержит 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 -ребер графа. [11]