Сильная ориентация - Strong orientation

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

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

Приложение для контроля дорожного движения

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

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

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

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

Теорема Нэша-Вильямса (1960, 1969 ) утверждает, что каждый неориентированный граф грамм имеет уравновешенная ориентация. Это ориентация со свойством, что для каждой пары вершин ты и v в грамм, количество попарно непересекающихся направленных путей из ты к v в получившемся ориентированном графе не менее ${displaystyle lfloor {frac {k} {2}} floor}$, куда k - максимальное количество путей в наборе непересекающихся по ребрам неориентированных путей из ты к v. Ориентации Нэша-Вильямса также обладают тем свойством, что они максимально приближены к эйлеровым ориентациям: в каждой вершине степень и исходная степень находятся внутри друг друга. Наличие сбалансированных ориентаций вместе с Теорема Менгера, немедленно следует теорема Роббинса: по теореме Менгера 2-реберный граф имеет по крайней мере два рёберно-непересекающихся пути между каждой парой вершин, из чего следует, что любая хорошо сбалансированная ориентация должна быть сильно связной. В более общем плане этот результат означает, что каждый 2k-реберный неориентированный граф можно сориентировать, образуя k-реберный ориентированный граф.

А полностью циклическая ориентация графа грамм - ориентация, в которой каждое ребро принадлежит ориентированному циклу. Для связных графов это то же самое, что и сильная ориентация, но полностью циклические ориентации также могут быть определены для несвязных графов, и это ориентации, в которых каждая связная компонента грамм становится сильно связанным. Теорема Роббинса может быть переформулирована как утверждение, что граф имеет полностью циклическую ориентацию тогда и только тогда, когда у него нет моста. Полностью циклические ориентации двойственны ациклическим ориентациям (ориентации, грамм в ориентированный ациклический граф ) в том смысле, что если грамм это планарный граф, и ориентации грамм переносятся на ориентации плоский двойной график грамм поворотом каждого края на 90 градусов по часовой стрелке, затем полностью циклическая ориентация грамм таким образом соответствует ациклической ориентации дуального графа и наоборот.^[3][4] Количество различных вполне циклических ориентаций любого графа грамм является Т_грамм(0,2) куда Т_грамм это Полином Тутте графа, и вдвойне количество ациклических ориентаций равно Т_грамм(2,0).^[5] Как следствие, из теоремы Роббинса следует, что многочлен Тутте имеет корень в точке (0,2) тогда и только тогда, когда граф грамм есть мост.

Если сильная ориентация имеет свойство, что все направленные циклы проходят через одно ребро ул (эквивалентно, если при изменении ориентации края получается ациклическая ориентация ), то ациклическая ориентация, образованная обращением ул это биполярная ориентация. Таким образом, каждая биполярная ориентация связана с сильной ориентацией.^[6]

Перевернуть графики

Если грамм является 3-реберно-связным графом и Икс и Y любые две разные сильные ориентации грамм, то можно преобразовать Икс в Y изменяя ориентацию одного края за раз, на каждом этапе сохраняя свойство сильной ориентации.^[7] Следовательно перевернуть график вершины которого соответствуют сильным ориентациям грамм, и ребра которого соответствуют парам сильных ориентаций, которые отличаются направлением единственного ребра, образует частичный куб.

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

Сильную ориентацию данного неориентированного графа без мостов можно найти в линейное время путем выполнения поиск в глубину графа, ориентируя все ребра в дереве поиска первого в глубину от корня дерева и ориентируя все оставшиеся ребра (которые обязательно должны соединять предка и потомка в дереве поиска первого в глубину) от потомка к предку.^[8] Если неориентированный граф грамм с мостами вместе со списком упорядоченных пар вершин, которые должны быть соединены ориентированными путями, это возможно в полиномиальное время найти ориентацию грамм соединяющий все заданные пары, если такая ориентация существует. Однако та же проблема НП-полный когда входом может быть смешанный график.^[9]

это # P-complete для подсчета количества сильных ориентаций данного графа грамм, даже когда грамм плоский и двудольный.^[3][10] Однако для плотные графы (более конкретно, графы, в которых каждая вершина имеет линейное число соседей), количество сильных ориентаций может быть оценено как полностью полиномиальная схема рандомизированной аппроксимации.^[3][11] Проблема подсчета сильных ориентаций также может быть решена точно, в полиномиальное время, для графов ограниченного ширина дерева.^[3]

Примечания

Рекомендации