Сильная ориентация (теория графов)

Сильная ориентация неориентированного графа — это назначение направлений каждому ребру (ориентация графа), при котором граф превращается в сильно связный граф.

Сильные ориентации можно использовать для планирования односторонней сети дорог. Согласно теореме Роббинса графы с сильными ориентациями — это в точности графы без мостов. Эйлерова ориентация и хорошо сбалансированная ориентация являются важными частными случаями сильных ориентаций. В свою очередь, сильные ориентации можно обобщить до вполне цикличных ориентаций несвязных графов. Множество сильных ориентаций графа образует частичный куб, в котором смежные ориентации отличаются лишь ориентацией одной дуги. Можно найти отдельную сильную ориентацию за линейное время, но посчитать число сильных ориентаций заданного графа является #P-полной задачей.

Приложение в регулировании трафика

Роббинс предложил задачу сильной ориентации с рассказом о городе, улицы которого и их пересечения представляются графом G. Согласно рассказу Роббинса, жители города хотят починить любой сегмент дороги за рабочие дни, сохраняя возможность достичь любую часть города из любой другой части по оставшимся дорогам (с двусторонним движением). На выходных все дороги открываются, но ввиду высокой плотности трафика жители хотят превратить все дороги в односторонние, но свойство достижимости любой части города из любой другой части должно остаться. Теорема Роббинса утверждает, что систему дорог можно ремонтировать в рабочие дни тогда и только тогда, когда их можно превратить в односторонние в выходные. По этой причине теорему иногда называют теоремой односторонних улиц.

После работы Роббинса в серии статей Робертс и Су (Xu) промоделировали более аккуратно задачу перевода решётки двусторонних улиц города в односторонние улицы и исследовали эффект этих переводов на расстояния между парами точек в решётке. Как они показали, традиционное распределение односторонних улиц, в котором направление движения по параллельным улицам чередуется, не является оптимальным для попарных расстояний. Однако улучшенная ориентация, которую они нашли, содержит точки, где направления сталкиваются (на перекрёсток приходит трафик с двух противоположных направлений), что можно рассматривать как недостаток их решений.

Связанные типы ориентаций

Если неориентированный граф имеет эйлеров цикл, эйлерова ориентация графа (ориентация, для которой каждая вершина имеет одинаковое число входящих и исходящих дуг) может быть найдена путём ориентации рёбер согласно эйлерову циклу. Эти ориентации автоматически будут сильными ориентациями.

Теорема Нэша — Уильямса утверждает, что любой неориентированный граф G имеет хорошо сбалансированную ориентацию. Это ориентация, в которой для любых двух вершин u и v графа G число попарно непересекающихся (по дугам) ориентированных путей из u в v в получившемся ориентированном графе равно, по меньшей мере, $\lfloor {\frac {k}{2}}\rfloor$, где k — максимальное число путей в множестве непересекающихся (по рёбрам) неориентированных путей из u в v. Ориентации Нэша — Уильямса имеют также свойство, что они очень близки к эйлеровым ориентациям — в каждой вершине число входящих и исходящих отличается на единицу. Из существования хорошо сбалансированных ориентаций вместе с теоремой Менгера немедленно вытекает теорема Роббинса — по теореме Менгера рёберно двусвязный граф имеет по меньшей мере два непересекающихся по рёбрам пути между любыми двумя вершинами, откуда следует, что любая хорошо сбалансированная ориентация должна быть сильно связной. Из этого же результата вытекает, что любой рёберно 2k-связный неориентированный граф может быть ориентирован с образованием рёберно k-связного ориентированного графа.

Вполне циклическая ориентация графа G — это ориентация, в которой каждое ребро принадлежит ориентированному циклу. Для связных графов это то же самое, что и сильная ориентация, но вполне циклическую ориентацию можно определить для несвязных графов и это ориентация, в которой каждая компонента связности графа G становится сильно связной. Теорему Роббинса можно переформулировать, что граф имеет вполне циклическую ориентацию тогда и только тогда, когда в нём нет мостов. Вполне циклические ориентации двойственны ацикличным ориентациям (ориентации, которые превращают граф G в ориентированный ациклический граф) в том смысле, что если G является планарным, а ориентации графа G переносятся на ориентации двойственного планарного графа для G путём поворота рёбер на 90 градусов по часовой стрелке, то вполне циклическая ориентация графа G соответствует построенной таким образом ацикличной ориентации двойственного графа, и наоборот. Число различных вполне циклических ориентаций любого графа G равна $T_{G}(0,2)$, где $T_{G}$ — многочлен Татта графа, а (двойственное) число ацикличных ориентаций равно $T_{G}(2,0)$. Как следствие, из теоремы Роббинса вытекает, что многочлен Татта имеет корень в точке (0,2) тогда и только тогда, когда в графе G имеется мост.

Если сильная ориентация имеет свойство, что все ориентированные циклы проходят через одно ребро st (эквивалентно, если смена ориентации ребра приводит к ациклической ориентации), то ациклическая ориентация, полученная сменой направления дуги st, является биполярной ориентацией. Любая двуполюсная ориентация связана с сильной ориентацией этим образом.

Граф смены направлений дуг

Если граф G рёберно 3-связен, а X и Y являются двумя различными сильными ориентациями графа G, то можно преобразовать X в Y путём изменения ориентации одной дуги за шаг таким образом, что на каждом шаге ориентация остаётся сильной. Таким образом, граф перевёртываний (граф смены направлений дуг), вершины которого соответствуют сильным ориентациям графа G, а рёбра соответствуют парам сильных ориентаций, отличающихся направлением одного ребра, образует частичный куб.

Алгоритмы и сложность

Сильная ориентация данного неориентированного графа без мостов может быть найдена за линейное время путём осуществления поиска в глубину графа, ориентации всех рёбер при поиске от корня и ориентации остальных рёбер (которые необходимо должны соединять предка и потомка в дереве поиска в глубину) от потомка к предку. Если задан неориентированный граф G с мостами вместе со списком ориентированных пар вершин, которые должны быть соединены ориентированными путями, можно за полиномиальное время найти ориентацию графа G, соединяющую все заданные пары, если такая ориентация существует. Однако та же самая задача является NP-полной, если вход может быть смешанным графом.

Подсчёт числа сильных ориентаций заданного графа G является #P-полной задачей, даже когда G планарен и является двудольным. Однако для плотных графов (точнее, для графов, в которых каждая вершина имеет линейное число соседей), число сильных ориентаций можно оценить с помощью стохастической аппроксимирующей схемы полиномиального времени. Задача подсчёта сильных ориентаций может быть решена точно за полиномиальное время для графов с ограниченной древесной шириной.