Сильная ориентация - 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]

Примечания

1. Ко и Тай (2002).
2. Шрайвер (1983).
3. Валлийский (1997).
4. Ной (2001).
5. Лас Вергнас (1980).
6. де Фрейссе, Оссона де Мендес и Розенштиль (1995).
7. Фукуда, Продон и Сакума (2001).
8. См. Например Аталлах (1984) и Робертс (1978).
9. Аркин и Хассин (2002).
10. Вертиган и валлийский (1992).
11. Алон, Frieze & Welsh (1995).

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

• Алон, Нога; Фриз, Алан; Уэлш, Доминик (1995), "Полиномиальные схемы рандомизированной аппроксимации для инвариантов Тутте-Гретендика: плотный случай", Случайные структуры и алгоритмы, 6 (4): 459–478, Дои:10.1002 / RSA.3240060409, МИСТЕР  1368847
• Аркин, Эстер М.; Хассин, Рафаэль (2002), "Заметка об ориентации смешанных графов", Дискретная прикладная математика, 116 (3): 271–278, Дои:10.1016 / S0166-218X (01) 00228-1, МИСТЕР  1878572.
• Аталлах, Михаил Дж. (1984), «Параллельная сильная ориентация неориентированного графа», Письма об обработке информации, 18 (1): 37–39, Дои:10.1016/0020-0190(84)90072-3, МИСТЕР  0742079.
• де Фрейссе, Юбер; Оссона де Мендес, Патрис; Розенштиль, Пьер (1995), "Биполярные ориентации снова и снова", Дискретная прикладная математика, 56 (2–3): 157–179, Дои:10.1016 / 0166-218X (94) 00085-R, МИСТЕР  1318743.
• Фукуда, Комей; Продон, Ален; Сакума, Тадаши (2001), «Заметки об ациклических ориентациях и лемме об обстреле», Теоретическая информатика, 263 (1–2): 9–16, Дои:10.1016 / S0304-3975 (00) 00226-7, МИСТЕР  1846912^{[постоянная мертвая ссылка ]}.
• Koh, K. M .; Тай, Э. Г. (2002), "Оптимальные ориентации графов и орграфов: обзор", Графы и комбинаторика, 18 (4): 745–756, Дои:10.1007 / s003730200060, МИСТЕР  1964792, S2CID  34821155.
• Лас Вергнас, Мишель (1980), «Выпуклость в ориентированных матроидах», Журнал комбинаторной теории, Серия B, 29 (2): 231–243, Дои:10.1016/0095-8956(80)90082-9, МИСТЕР  0586435.
• Нэш-Уильямс, К. Сент-Дж. А. (1960), "Об ориентации, связности и нечетных вершинах-спариваниях в конечных графах.", Канадский математический журнал, 12: 555–567, Дои:10.4153 / cjm-1960-049-6, МИСТЕР  0118684.
• Нэш-Уильямс, К. Сент-Дж. А. (1969), "Хорошо сбалансированные ориентации конечных графов и ненавязчивые пары нечетных вершин", Недавний прогресс в комбинаторике (Proc. Third Waterloo Conf. On Combinatorics, 1968), Нью-Йорк: Academic Press, стр. 133–149, МИСТЕР  0253933.
• Ной, Марк (2001), "Ациклические и полностью циклические ориентации в плоских графах", Американский математический ежемесячник, 108 (1): 66–68, Дои:10.2307/2695680, JSTOR  2695680, МИСТЕР  1857074.
• Роббинс, Х. (1939), «Теорема о графах в приложении к проблеме управления движением», Американский математический ежемесячный журнал, 46 (5): 281–283, Дои:10.2307/2303897, HDL:10338.dmlcz / 101517, JSTOR  2303897.
• Робертс, Фред С. (1978), "Глава 2. Проблема улицы с односторонним движением", Теория графов и ее приложения к проблемам общества, Серия региональных конференций CBMS-NSF по прикладной математике, 29, Филадельфия, Пенсильвания: Общество промышленной и прикладной математики (SIAM), стр. 7–14, ISBN  9780898710267, МИСТЕР  0508050.
• Робертс, Фред С .; Сюй, Юнхуа (1988), "Об оптимальных сильно связных ориентациях графов городских улиц. I. Большие сетки", Журнал SIAM по дискретной математике, 1 (2): 199–222, Дои:10.1137/0401022, МИСТЕР  0941351.
• Робертс, Фред С .; Сюй, Юнхуа (1989), "Об оптимальных сильно связанных ориентациях графиков городских улиц. II. Два проспекта восток-запад или улицы север-юг", Сети, 19 (2): 221–233, Дои:10.1002 / нетто.3230190204, МИСТЕР  0984567.
• Робертс, Фред С .; Сюй, Юнхуа (1992), "Об оптимальных сильно связанных ориентациях графиков городских улиц. III. Три проспекта восток-запад или улицы север-юг", Сети, 22 (2): 109–143, Дои:10.1002 / нетто.3230220202, МИСТЕР  1148018.
• Робертс, Фред С .; Сюй, Юн Хуа (1994), "Об оптимальных сильно связанных ориентациях графиков городских улиц. IV. Четыре проспекта восток-запад или улицы север-юг", Дискретная прикладная математика, 49 (1–3): 331–356, Дои:10.1016 / 0166-218X (94) 90217-8, МИСТЕР  1272496.
• Шрайвер, А. (1983), «Границы числа эйлеровых ориентаций» (PDF), Комбинаторика, 3 (3–4): 375–380, Дои:10.1007 / BF02579193, МИСТЕР  0729790, S2CID  13708977.
• Vertigan, D. L .; Уэлш, Д. Дж. А. (1992), "Вычислительная сложность плоскости Тутте: двудольный случай", Комбинаторика, теория вероятностей и вычисления, 1 (2): 181–187, Дои:10.1017 / S0963548300000195, МИСТЕР  1179248.
• Валлийский, Доминик (1997), «Приблизительный подсчет», Обзоры по комбинаторике, 1997 г. (Лондон), Лондонская математика. Soc. Lecture Note Ser., 241, Кембридж: Cambridge Univ. Press, стр. 287–323, Дои:10.1017 / CBO9780511662119.010, МИСТЕР  1477750.