Перегляд вихідного коду сторінки Сильна орієнтація (теорія графів)

'''Сильна орієнтація''' [[Граф (математика)|неорієнтованого графа]]&nbsp;— це призначення напрямків кожному ребру ([[Орієнтація (теорія графів)|орієнтація графа]]), за якого граф перетворюється на [[Компонента сильної зв'язності графа|сильно зв'язний граф]].

Сильні орієнтації можна використати для планування односторонньої мережі доріг. Згідно з [[Теорема Роббінса|теоремою Роббінса]], графи з сильними орієнтаціями&nbsp;— це точно [[Міст (теорія графів)|графи без мостів]]. Ейлерова орієнтація і добре збалансована орієнтація є важливими частковими випадками сильних орієнтацій. У свою чергу, сильні орієнтації можна узагальнити до цілком циклічних орієнтацій незв'язних графів. Множина сильних орієнтацій графа утворює [[частковий куб]], у якому суміжні орієнтації відрізняються лише орієнтацією однієї дуги. Окрему сильну орієнтацію можна знайти за лінійний час, але порахувати число сильних орієнтацій даного графа є #P-повною задачею.

== Застосування в регулюванні руху ==
Роббінс{{Sfn|Robbins|1939}} запропонував задачу сильної орієнтації з розповіддю про місто, вулиці якого та їх перетини подано графом ''G''. При цьому, жителі міста хочуть мати можливість полагодити будь-який сегмент дороги в будні дні, зберігаючи можливість дістатися до будь-якої частини міста з будь-якої іншої частини по дорогах, що залишилися (з двостороннім рухом). На вихідних усі дороги відкриваються, але через високу щільність трафіку жителі хочуть перетворювати всі дороги на односторонні, зберігаючи при цьому властивість досяжності будь-якої частини міста з будь-якої іншої. [[Теорема Роббінса]] стверджує, що систему доріг можна ремонтувати в робочі дні [[тоді й лише тоді]], коли їх можна перетворити на односторонні у вихідні. З цієї причини теорему іноді називають '''теоремою односторонніх вулиць'''{{Sfn|Koh, Tay|2002}}.

Після роботи Роббінса, в серії статей Робертс і Су (Xu) докладніше промоделювали задачу переведення [[Решітка (теорія графів)|решітки]] двосторонніх вулиць міста в односторонні вулиці і досліджували вплив цих переведень на відстані між парами точок у решітці. Як вони показали, традиційний розподіл односторонніх вулиць, за якого напрямок руху паралельними вулицями чергується, не є оптимальним для попарних відстаней. Однак покращена орієнтація, яку вони знайшли, містить точки, де напрямки стикаються (на перехрестя приходить рух з двох протилежних напрямків), що можна розглядати як недолік їхніх розв'язків.

== Пов'язані типи орієнтацій ==
Якщо неорієнтований граф має [[Ейлерів ланцюг|ейлерів цикл]], ейлерову орієнтація графа (орієнтація, за якої кожна вершина має однакове число вхідних та вихідних дуг) можна знайти зорієнтувавши ребра за ейлеровим циклом {{Sfn|Schrijver|1983}}. Ці орієнтації будуть автоматично сильними орієнтаціями.

'''Теорема Неша&nbsp;— Вільямса'''{{Sfn|Nash-Williams|1960}}{{Sfn|Nash-Williams|1969}} стверджує, що будь-який неорієнтований граф ''G'' має ''добре збалансовану орієнтацію''. Це орієнтація, в якій для будь-яких двох вершин ''u'' і ''v'' графа ''G'' число попарно неперетинних (по дугах) орієнтованих шляхів з ''u'' до ''v'' в отриманому орієнтованому графі дорівнює, щонайменше, <math>\lfloor\frac{k}{2}\rfloor</math>, де ''k''&nbsp;— найбільша кількість шляхів у множині неперетинних (по ребрах) неорієнтованих шляхів з ''u'' до ''v''. Орієнтації Неша&nbsp;— Вільямса мають також властивість, що вони дуже близькі до ейлерових орієнтацій&nbsp;— у кожній вершині число вхідних та вихідних дуг відрізняється на одиницю. Із існування добре збалансованих орієнтацій разом з [[Теорема Менгера|теоремою Менгера]] негайно випливає теорема Роббінса&nbsp;— за теоремою Менгера [[K-реберно-зв'язний граф|реберно двозв'язний]] граф має щонайменше два неперетинних по ребрах шляхи між будь-якими двома вершинами, звідки випливає, що будь-яка добре збалансована орієнтація має бути сильно зв'язною. З цього результату випливає, що будь-який ''2k''-реберно-зв'язний неорієнтований граф можна зорієнтувати з утворенням ''k''-реберно-зв'язного орієнтованого графа.

'''Цілком циклічна орієнтація''' графа ''G''&nbsp;— це орієнтація, у якій кожне ребро належить орієнтованому циклу. Для зв'язних графів це те саме, що й сильна орієнтація, але цілком циклічну орієнтацію можна визначити для незв'язних графів і це орієнтація, в якій кожна компонента зв'язності графа ''G'' стає сильно зв'язною. Теорему Роббінса можна переформулювати, що граф має цілком циклічну орієнтацію [[тоді й лише тоді]], коли в ньому немає мостів. Цілком циклічні орієнтації двоїсті ациклічним орієнтаціям (орієнтації, які перетворюють граф ''G'' на [[Спрямований ациклічний граф|орієнтований ациклічний граф]]) в тому сенсі, що якщо ''G'' є [[Планарний граф|планарним]], а орієнтації графа ''G'' переносяться на орієнтації [[Двоїстий граф|двоїстого до ''G'' планарного]] графа поворотом ребер на 90°, то цілком циклічна орієнтація графа ''G'' відповідає побудованій у такий спосіб ациклічній орієнтації двоїстого графа, і навпаки{{Sfn|Welsh|1997}}{{Sfn|Noy|2001}}. Число різних цілком циклічних орієнтацій будь-якого графа ''G'' дорівнює <math>T_G(0,2) </math>, де <math>T_G</math>&nbsp;— [[многочлен Татта]] графа, а (двоїсте) число ациклічних орієнтацій дорівнює <math>T_G(2,0) </math>{{Sfn|Las Vergnas|1980}}. Як наслідок, з теореми Роббінса випливає, що многочлен Татта має корінь у точці {{Math|(0,2)}} тоді й лише тоді, коли в графі ''G'' є міст.

Якщо сильна орієнтація має властивість, що всі орієнтовані цикли проходять через одне ребро ''st'' (еквівалентно, якщо зміна орієнтації ребра приводить до [[Ациклічна орієнтація|ациклічної орієнтації]]), то ациклічна орієнтація, отримана зміною напряму дуги ''st'', є [[Біполярна орієнтація|біполярною орієнтацією]]. В такий спосіб будь-яка біполярна орієнтація пов'язана з сильною орієнтацією{{Sfnp|de Fraysseix, Ossona de Mendez, Rosenstiehl|1995}}.

== Граф зміни напрямків дуг ==
Якщо граф ''G'' 3-реберно-зв'язний, а ''X'' і ''Y''&nbsp;— дві різні сильні орієнтації графа ''G'', то можна перетворити ''X'' на ''Y'', покроково змінюючи орієнтацію однієї дуги, таким чином, що на кожному кроці орієнтація залишається сильною{{Sfn|Fukuda, Prodon, Sakuma|2001}}. Таким чином, ''граф перевертань'' (граф зміни напрямів дуг), вершини якого відповідають сильним орієнтаціям графа ''G'', а ребра відповідають парам сильних орієнтацій, що відрізняються напрямком одного ребра, утворює [[частковий куб]].

== Алгоритми та складність ==
Сильну орієнтацію даного неорієнтованого графа без мостів можна знайти за [[Часова складність|лінійний час]] здійсненням [[Пошук у глибину|пошуку в глибину]] графа, орієнтуванням усіх ребер під час пошуку від кореня та орієнтування інших ребер (які мають з'єднувати предка та нащадка в дереві пошуку в глибину) від нащадка до предка<ref>Див., наприклад, {{Harvard citation|Atallah|1984}} і {{Harvard citation|Roberts|1978}}.</ref>. Якщо дано неорієнтований граф ''G'' з мостами разом зі списком орієнтованих пар вершин, які мають бути з'єднані орієнтованими шляхами, можна за [[Часова складність|поліноміальний час]] знайти орієнтацію графа ''G'', що з'єднує всі задані пари, якщо вона існує. Однак та сама задача є [[NP-повна задача|NP-повною]], якщо вхід може бути [[Змішаний граф|змішаним графом]]{{Sfn|Arkin, Hassin|2002}}.

Підрахунок числа сильних орієнтацій даного графа ''G'' є #P-повною задачею, навіть коли ''G'' планарний і є [[Двочастковий граф|двочастковим]]{{Sfn|Welsh|1997}}{{Sfn|Vertigan, Welsh|1992}}. Однак для [[Щільний граф|щільних графів]] (точніше, для графів, у яких кожна вершина має лінійне число сусідів), число сильних орієнтацій можна оцінити за допомогою [[схема наближення до поліноміального часу|стохастичної схеми наближення до поліноміального часу]]{{Sfn|Welsh|1997}}{{Sfn|Alon, Frieze, Welsh|1995}}. Для графів з обмеженою [[Деревна ширина (теорія графів)|деревною шириною]] задачу підрахунку сильних орієнтацій можна розв'язати точно за [[Часова складність|поліноміальний час]]{{Sfn|Welsh|1997}}.

== Примітки ==
{{примітки|2}}

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