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

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

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

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

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

• все вершины получают различные номера,
• вершине s назначается номер 1,
• вершине t назначается номер n,
• если вершине v назначается номер i ($1<i<n$), то по меньшей мере одному соседу вершины v назначается меньший, чем i номер, а одному соседу — большийШаблон:RШаблон:RШаблон:R.

Граф имеет биполярную ориентацию тогда и только тогда, когда он имеет st-нумерацию. Если граф имеет биполярную ориентацию, то st-нумерация может быть построена путём нахождения топологической сортировки ориентированного ациклического графа, заданного ориентацией, и нумерации каждой вершины согласно её позиции в этом порядке. В обратном направлении, любая st-нумерация порождает топологический порядок, в котором каждое ребро графа G ориентировано от конечной точки с меньшим номером в конечную точку с большим номеромШаблон:RШаблон:R. В графе, содержащем ребро st, ориентация является биполярной тогда и только тогда, когда она ациклична и ориентация, образованная обращением ребра st, вполне цикличнаШаблон:R.

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

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

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

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

Алгоритмы

Можно найти st-нумерацию и биполярную ориентацию заданного графа с выделенными вершинами s и t за линейное время, используя поиск в глубинуШаблон:RШаблон:RШаблон:R. Алгоритм ТарьянаШаблон:R использует поиск в глубину, который начинается с вершины s. Как в основанном на поиске в глубину алгоритме для проверки, является ли граф двусвязным, этот алгоритм первым проходом определяет величину pre(v) для вершины v, которая является числом предпорядока вершины v при проходе в глубину, и число low(v), которое является наименьшим числом предпорядка, которое может быть достигнуто следованием по одному ребру от v в дереве поиска в глубину. Оба эти числа могут быть вычислены за линейное время как часть поиска в глубину. Данный граф будет двусвязным (и будет иметь биполярную ориентацию) тогда и только тогда, когда t является единственным потомком вершины s в дереве поиска в глубину и $\mathrm{l}\mathrm{o}\mathrm{w}(v)<\mathrm{p}\mathrm{r}\mathrm{e}(v)$ для всех вершин v, отличных от s. Когда эти числа вычислены, алгоритм Тарьяна осуществляет второй проход дерева поиска в глубину, поддерживая число sign(v) для каждой вершины v и связный список вершин, который создаёт в конечном счёте список всех вершин графа в порядке, заданном st-нумерацией. Начально, список содержит s и t и $\mathrm{s}\mathrm{i}\mathrm{g}\mathrm{n}(s)=-1$. Когда вершина v обнаружена при первом проходе, v вставляется в список либо до, либо после его родителя p(v) в дереве поиска в глубину согласно знаку sign(low(v)). Затем sign(p(v)) устанавливается в -sign(low(v)). Как показал Тарьян, полученный порядок вершин из этой процедуры даёт st-нумерацию заданного графаШаблон:R.

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

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

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

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