Биполярная ориентация

Биполярная ориентация или st-ориентация неориентированного графа — это назначение ориентации каждому ребру (ориентации), что превращает граф в направленный ациклический граф с единственным источником s и единственном стоком t, а st-нумерация графа — это топологическая сортировка полученного ориентированного ациклического графа[1][2].

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

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

st-Нумерация графа G (снова, с выделенными двумя вершинами s и t) — это назначение целых чисел от 1 до n вершинам графа G, таких что

• все вершины получают различные номера,
• вершине s назначается номер 1,
• вершине t назначается номер n,
• если вершине v назначается номер i (${\displaystyle 1<i<n}$), то по меньшей мере одному соседу вершины 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, то вершина с наибольшим номером в компоненте не может иметь соседа с большим номером.

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

Лемпель, Эвен и Цедербаум[3] сформулировали st-нумерации как часть алгоритма проверки планарности[3], а Розенштиль[5] и Тарьян[1] сформулировали биполярную ориентацию как часть алгоритма построения мозаичного представления планарных графов[1].

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

Алгоритмы

Можно найти st-нумерацию и биполярную ориентацию заданного графа с выделенными вершинами s и t за линейное время, используя поиск в глубину[8][9][10]. Алгоритм Тарьяна[10] использует поиск в глубину, который начинается с вершины s. Как в основанном на поиске в глубину алгоритме для проверки, является ли граф двусвязным, этот алгоритм первым проходом определяет величину pre(v) для вершины v, которая является числом предпорядока вершины v при проходе в глубину, и число low(v), которое является наименьшим числом предпорядка, которое может быть достигнуто следованием по одному ребру от v в дереве поиска в глубину. Оба эти числа могут быть вычислены за линейное время как часть поиска в глубину. Данный граф будет двусвязным (и будет иметь биполярную ориентацию) тогда и только тогда, когда t является единственным потомком вершины s в дереве поиска в глубину и ${\displaystyle \mathrm {low} (v)<\mathrm {pre} (v)}$ для всех вершин v, отличных от s. Когда эти числа вычислены, алгоритм Тарьяна осуществляет второй проход дерева поиска в глубину, поддерживая число sign(v) для каждой вершины v и связный список вершин, который создаёт в конечном счёте список всех вершин графа в порядке, заданном st-нумерацией. Начально, список содержит s и t и ${\displaystyle \mathrm {sign} (s)=-1}$. Когда вершина v обнаружена при первом проходе, v вставляется в список либо до, либо после его родителя p(v) в дереве поиска в глубину согласно знаку sign(low(v)). Затем sign(p(v)) устанавливается в -sign(low(v)). Как показал Тарьян, полученный порядок вершин из этой процедуры даёт st-нумерацию заданного графа[10].

Альтернативно, эффективные последовательные и параллельные алгоритмы могут основываться на ушной декомпозиции[4][11]. Открытая ушная декомпозиция заданного графа с выделенными вершинами s и t может быть определена как разбиение рёбер графа на последовательность путей, называемых «ушами», в которых конечными точками первого уха являются s и t, конечные точки каждого следующего уха принадлежат предыдущим ушам в последовательности, а каждая внутренняя вершина каждого уха первый раз появляется именно в этом ухе. Открытая ушная декомпозиция существует тогда и только тогда, когда граф, полученный добавлением ребра st, двусвязен (то же самое условие, что и для существования биполярной ориентации) и может быть найден за линейное время. st-Ориентация может быть получена путём задания подходящего направления для каждого уха, принимая меры предосторожности, что если уже существует ориентированный путь, соединяющий те же две конечные точки в предыдущих ушах, то новое ухо должно иметь то же направление. Однако, проверка этого непосредственно с помощью вычисления достижимости будет медленной. Маон, Шибер и Вышкин[4] дали сложную, но локализованную процедуру поиска для определения подходящей ориентации для каждого уха, которая (в отличие от подхода, использующего поиск в глубину) пригодна для параллельных вычислений[4].

Папаментоу и Толлис[12] сообщают об алгоритмах для контроля длин ориентированных путей в биполярной ориентации заданного графа, которые, в свою очередь, приводят к контролю длины и высоты некоторых видов визуализации графов[12].

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

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

Примечания

1. Pierre Rosenstiehl, Robert Tarjan. Rectilinear planar layouts and bipolar orientations of planar graphs // Discrete and Computational Geometry. — 1986. — Т. 1, вып. 4. — С. 343–353. — doi:10.1007/BF02187706..
2. Hubert de Fraysseix, Patrice Ossona de Mendez, Pierre. Bipolar orientations revisited // Discrete Applied Mathematics. — 1995. — Т. 56, вып. 2—3. — С. 157–179. — doi:10.1016/0166-218X(94)00085-R.
3. Abraham Lempel, Shimon Even, Cederbaum I. An algorithm for planarity testing of graphs // Theory of Graphs (Internat. Sympos., Rome, 1966). — New York: Gordon and Breach, 1967. — С. 215–232.
4. Maon Y., Schieber B., Vishkin U. Parallel ear decomposition search (EDS) and ST-numbering in graphs // Theoretical Computer Science. — 1986. — Т. 47, вып. 3. — doi:10.1016/0304-3975(86)90153-2.
5. Фамилия Rosenstiehl немецкого происхождения и на немецком она читается как Розенштиль. В английской варианте она может звучать как Розенстиль
6. Platt C. R. Planar lattices and planar graphs // Journal of Combinatorial Theory. — 1976. — Т. 21, вып. 1. — С. 30–39. — doi:10.1016/0095-8956(76)90024-1.
7. Giuseppe Di Battista, Roberto Tamassia. Algorithms for plane representations of acyclic digraphs // Theoretical Computer Science. — 1988. — Т. 61, вып. 2—3. — С. 175–198. — doi:10.1016/0304-3975(88)90123-5.
8. Ebert J. st-ordering the vertices of biconnected graphs // Computing. — 1983. — Т. 30, вып. 1. — С. 19–33. — doi:10.1007/BF02253293.
9. Shimon Even, Robert Tarjan. Computing an st-numbering // Theoretical Computer Science. — 1976. — Т. 2, вып. 3. — С. 339–344. — doi:10.1016/0304-3975(76)90086-4.
10. Robert Tarjan. Two streamlined depth-first search algorithms // Fundamenta Informaticae. — 1986. — Т. 9, вып. 1. — С. 85–94.
11. Hillel Gazit. Optimal EREW parallel algorithms for connectivity, ear decomposition and st-numbering of planar graphs // Proc. 5th International Parallel Processing Symposium. — 1991. — С. 84–91. — doi:10.1109/IPPS.1991.153761.
12. Charalampos Papamanthou, Ioannis G. Tollis. Applications of parameterized st-orientations in graph drawing algorithms // Graph Drawing: 13th International Symposium, GD 2005, Limerick, Ireland, September 12–14, 2005, Revised Papers. — Berlin: Springer, 2006. — Т. 3843. — С. 355–367. — (Lecture Notes in Computer Science). — doi:10.1007/11618058_32.