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

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

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

Заявление на регулирование дорожного движения

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

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

Сопутствующие виды ориентации

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

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

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

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

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

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

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

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

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

Ссылки

• Алон, Нога ; Фриз, Алан ; Уэлш, Доминик (1995), «Схемы рандомизированной аппроксимации с полиномиальным временем для инвариантов Тутте-Гретендика: плотный случай», Случайные структуры и алгоритмы , 6 (4): 459–478, doi : 10.1002/rsa.3240060409 , MR   1368847
• Аркин, Эстер М .; Хассин, Рафаэль (2002), «Заметки об ориентациях смешанных графов» (PDF) , Discrete Applied Mathematics , 116 (3): 271–278, doi : 10.1016/S0166-218X(01)00228-1 , MR   1878572 .
• Аталлах, Михаил Дж. (1984), «Параллельная сильная ориентация неориентированного графа» , Information Processing Letters , 18 (1): 37–39, doi : 10.1016/0020-0190(84)90072-3 , MR   0742079 .
• де Фрессе, Юбер; Оссона де Мендес, Патрис ; Розенштиль, Пьер (1995), «Возвращение к биполярным ориентациям», Discrete Applied Mathematics , 56 (2–3): 157–179, doi : 10.1016/0166-218X(94)00085-R , MR   1318743 .
• Фукуда, Комей ; Продон, Ален; Сакума, Тадаши (2001), «Заметки об ациклических ориентациях и лемме об обстреле» , Theoretical Computer Science , 263 (1–2): 9–16, doi : 10.1016/S0304-3975(00)00226-7 , MR   1846912
• Кох, КМ; Тэй, Э.Г. (2002), «Оптимальные ориентации графов и орграфов: обзор», Graphs and Combinatorics , 18 (4): 745–756, doi : 10.1007/s003730200060 , MR   1964792 , S2CID   34821155 .
• Лас Верньяс, Мишель (1980), «Выпуклость в ориентированных матроидах», Журнал комбинаторной теории , серия B, 29 (2): 231–243, doi : 10.1016/0095-8956(80)90082-9 , MR   0586435 .
• Нэш-Уильямс, К. Ст. Дж. А. (1960), «Об ориентациях, связности и парах нечетных вершин в конечных графах», Canadian Journal of Mathematics , 12 : 555–567, doi : 10.4153/cjm-1960-049 -6 , МР   0118684 .
• Нэш-Уильямс, К. Ст. Дж. А. (1969), «Хорошо сбалансированные ориентации конечных графов и ненавязчивые пары нечетных вершин», Недавний прогресс в комбинаторике (Труды Третьей конференции Ватерлоо по комбинаторике, 1968) , Нью-Йорк: Академик Пресс, стр. 133–149, MR   0253933 .
• Ной, Марк (2001), «Ациклические и полностью циклические ориентации в плоских графах», The American Mathematical Monthly , 108 (1): 66–68, doi : 10.2307/2695680 , JSTOR   2695680 , MR   1857074 .
• Роббинс, HE (1939), «Теорема о графах с применением к задаче управления дорожным движением», American Mathematical Monthly , 46 (5): 281–283, doi : 10.2307/2303897 , JSTOR   2303897 .
• Робертс, Фред С. (1978), «Глава 2. Проблема улицы с односторонним движением», Теория графов и ее приложения к проблемам общества , Серия региональных конференций CBMS-NSF по прикладной математике, том. 29, Филадельфия, Пенсильвания: Общество промышленной и прикладной математики (SIAM), стр. 7–14, ISBN.  9780898710267 , МР   0508050 .
• Робертс, Фред С.; Сюй, Юнхуа (1988), «Об оптимальных сильно связных ориентациях графов городских улиц. I. Большие сетки», SIAM Journal on Discrete Mathematics , 1 (2): 199–222, doi : 10.1137/0401022 , MR   0941351 .
• Робертс, Фред С.; Сюй, Юнхуа (1989), «Об оптимальных сильно связанных ориентациях графов городских улиц. II. Два проспекта с востока на запад или улицы с севера на юг», Networks , 19 (2): 221–233, doi : 10.1002/net. 3230190204 , МР   0984567 .
• Робертс, Фред С.; Сюй, Юнхуа (1992), «Об оптимальных сильно связанных ориентациях графов городских улиц. III. Три проспекта с востока на запад или улицы с севера на юг», Networks , 22 (2): 109–143, doi : 10.1002/net. 3230220202 , МР   1148018 .
• Робертс, Фред С.; Сюй, Юн Хуа (1994), «Об оптимальных сильно связанных ориентациях графов городских улиц. IV. Четыре проспекта с востока на запад или улицы с севера на юг», Discrete Applied Mathematics , 49 (1–3): 331–356, doi : 10.1016/0166-218X(94)90217-8 , МР   1272496 .
• Шрийвер, А. (1983), «Границы числа эйлеровых ориентаций» (PDF) , Combinatorica , 3 (3–4): 375–380, doi : 10.1007/BF02579193 , MR   0729790 , S2CID   13708977 .
• Вертиган, ДЛ; Уэлш, DJA (1992), «Вычислительная сложность плоскости Тутте: двудольный случай», Combinatorics, Probability and Computing , 1 (2): 181–187, doi : 10.1017/S0963548300000195 , MR   1179248 .
• Уэлш, Доминик (1997), «Приблизительный подсчет», Обзоры по комбинаторике, 1997 (Лондон) , London Math. Соц. Лекционная конспект. Сер., т. 1, с. 241, Кембридж: Кембриджский университет. Press, стр. 287–323, doi : 10.1017/CBO9780511662119.010 , ISBN.  978-0-521-59840-8 , МР   1477750 .