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

Сильна орієнтація неорієнтованого графа — це призначення напрямків кожному ребру (орієнтація графа), за якого граф перетворюється на сильно зв'язний граф.

Сильні орієнтації можна використати для планування односторонньої мережі доріг. Згідно з теоремою Роббінса, графи з сильними орієнтаціями — це точно графи без мостів. Ейлерова орієнтація і добре збалансована орієнтація є важливими частковими випадками сильних орієнтацій. У свою чергу, сильні орієнтації можна узагальнити до цілком циклічних орієнтацій незв'язних графів. Множина сильних орієнтацій графа утворює частковий куб, у якому суміжні орієнтації відрізняються лише орієнтацією однієї дуги. Окрему сильну орієнтацію можна знайти за лінійний час, але порахувати число сильних орієнтацій даного графа є #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 планарний і є двочастковим. Однак для щільних графів (точніше, для графів, у яких кожна вершина має лінійне число сусідів), число сильних орієнтацій можна оцінити за допомогою стохастичної схеми наближення до поліноміального часу. Для графів з обмеженою деревною шириною задачу підрахунку сильних орієнтацій можна розв'язати точно за поліноміальний час.

Література

• Noga Alon, Alan Frieze, Dominic Welsh. Polynomial time randomized approximation schemes for Tutte-Gröthendieck invariants: the dense case // Random Structures & Algorithms. — 1995. — Т. 6, вип. 4. — С. 459–478. — DOI:10.1002/rsa.3240060409.
• Esther M. Arkin, Refael Hassin. A note on orientations of mixed graphs // Discrete Applied Mathematics. — 2002. — Т. 116, вип. 3. — С. 271–278. — DOI:10.1016/S0166-218X(01)00228-1.
• Mikhail Atallah. Parallel strong orientation of an undirected graph // Information Processing Letters. — 1984. — Т. 18, вип. 1. — С. 37–39. — DOI:10.1016/0020-0190(84)90072-3.
• Hubert de Fraysseix, Patrice Ossona de Mendez, Pierre Rosenstiehl. Bipolar orientations revisited // Discrete Applied Mathematics. — 1995. — Т. 56, вип. 2-3. — С. 157–179. — DOI:10.1016/0166-218X(94)00085-R.
• Komei Fukuda, Alain Prodon, Tadashi Sakuma. Notes on acyclic orientations and the shelling lemma // Theoretical Computer Science. — 2001. — Т. 263, вип. 1-2. — С. 9–16. — DOI:10.1016/S0304-3975(00)00226-7.^{[недоступне посилання з Декабрь 2017]}
• K. M. Koh, E. G. Tay. Optimal orientations of graphs and digraphs: a survey // Graphs and Combinatorics. — 2002. — Т. 18, вип. 4. — С. 745–756. — DOI:10.1007/s003730200060.
• Michel Las Vergnas. Convexity in oriented matroids // Journal of Combinatorial Theory. — 1980. — Т. 29, вип. 2. — С. 231–243. — (Series B). — DOI:10.1016/0095-8956(80)90082-9.
• C. St. J. A. Nash-Williams. On orientations, connectivity and odd-vertex-pairings in finite graphs. // Canadian Journal of Mathematics. — 1960. — Т. 12. — С. 555–567. — DOI:10.4153/cjm-1960-049-6.
• C. St. J. A. Nash-Williams. Recent Progress in Combinatorics (Proc. Third Waterloo Conf. on Combinatorics, 1968). — New York : Academic Press, 1969. — С. 133–149.
• Marc Noy. Acyclic and totally cyclic orientations in planar graphs // The American Mathematical Monthly. — 2001. — Т. 108, вип. 1. — С. 66–68. — DOI:10.2307/2695680.
• H. E. Robbins. A theorem on graphs, with an application to a problem on traffic control // American Mathematical Monthly. — 1939. — Т. 46. — С. 281–283. — DOI:10.2307/2303897.
• Fred S. Roberts. Graph Theory and its Applications to Problems of Society. — Philadelphia, Pa. : Society for Industrial and Applied Mathematics (SIAM), 1978. — Т. 29. — С. 7–14. — (CBMS-NSF Regional Conference Series in Applied Mathematics)
• Fred S. Roberts, Yonghua Xu. On the optimal strongly connected orientations of city street graphs. I. Large grids // SIAM Journal on Discrete Mathematics. — 1988. — Т. 1, вип. 2. — С. 199–222. — DOI:10.1137/0401022.
• Fred S. Roberts, Yonghua Xu. On the optimal strongly connected orientations of city street graphs. II. Two east-west avenues or north-south streets // Networks. — 1989. — Т. 19, вип. 2. — С. 221–233. — DOI:10.1002/net.3230190204.
• Fred S. Roberts, Yonghua Xu. On the optimal strongly connected orientations of city street graphs. III. Three east-west avenues or north-south streets // Networks. — 1992. — Т. 22, вип. 2. — С. 109–143. — DOI:10.1002/net.3230220202.
• Fred S. Roberts, Yonghua Xu. On the optimal strongly connected orientations of city street graphs. IV. Four east-west avenues or north-south streets // Discrete Applied Mathematics. — 1994. — Т. 49, вип. 1-3. — С. 331–356. — DOI:10.1016/0166-218X(94)90217-8.
• A. Schrijver. Bounds on the number of Eulerian orientations // Combinatorica. — 1983. — Т. 3, вип. 3-4. — С. 375–380. — DOI:10.1007/BF02579193.
• D. L. Vertigan, D. J. A. Welsh. The computational complexity of the Tutte plane: the bipartite case // Combinatorics, Probability and Computing. — 1992. — Т. 1, вип. 2. — С. 181–187. — DOI:10.1017/S0963548300000195.
• Dominic Welsh. Surveys in combinatorics, 1997 (London). — Cambridge : Cambridge Univ. Press, 1997. — Т. 241. — С. 287–323. — (London Math. Soc. Lecture Note Ser.) — DOI:10.1017/CBO9780511662119.010.