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

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

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

Приложение в регулировании трафика

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

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

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

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

Теорема Нэша — Уильямса[4][5] утверждает, что любой неориентированный граф G имеет хорошо сбалансированную ориентацию. Это ориентация, в которой для любых двух вершин u и v графа G число попарно непересекающихся (по дугам) ориентированных путей из u в v в получившемся ориентированном графе равно, по меньшей мере, , где k — максимальное число путей в множестве непересекающихся (по рёбрам) неориентированных путей из u в v. Ориентации Нэша — Уильямса имеют также свойство, что они очень близки к эйлеровым ориентациям — в каждой вершине число входящих и исходящих отличается на единицу. Из существования хорошо сбалансированных ориентаций вместе с теоремой Менгера немедленно вытекает теорема Роббинса — по теореме Менгера рёберно двусвязный граф имеет по меньшей мере два непересекающихся по рёбрам пути между любыми двумя вершинами, откуда следует, что любая хорошо сбалансированная ориентация должна быть сильно связной. Из этого же результата вытекает, что любой рёберно 2k-связный неориентированный граф может быть ориентирован с образованием рёберно k-связного ориентированного графа.

Вполне циклическая ориентация графа G — это ориентация, в которой каждое ребро принадлежит ориентированному циклу. Для связных графов это то же самое, что и сильная ориентация, но вполне циклическую ориентацию можно определить для несвязных графов и это ориентация, в которой каждая компонента связности графа G становится сильно связной. Теорему Роббинса можно переформулировать, что граф имеет вполне циклическую ориентацию тогда и только тогда, когда в нём нет мостов. Вполне циклические ориентации двойственны ацикличным ориентациям (ориентации, которые превращают граф G в ориентированный ациклический граф) в том смысле, что если G является планарным, а ориентации графа G переносятся на ориентации двойственного планарного графа для G путём поворота рёбер на 90 градусов по часовой стрелке, то вполне циклическая ориентация графа G соответствует построенной таким образом ацикличной ориентации двойственного графа, и наоборот[6][7]. Число различных вполне циклических ориентаций любого графа G равна , где  — многочлен Татта графа, а (двойственное) число ацикличных ориентаций равно [8]. Как следствие, из теоремы Роббинса вытекает, что многочлен Татта имеет корень в точке (0,2) тогда и только тогда, когда в графе G имеется мост.

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

Граф смены направлений дуг

Если граф G рёберно 3-связен, а X и Y являются двумя различными сильными ориентациями графа G, то можно преобразовать X в Y путём изменения ориентации одной дуги за шаг таким образом, что на каждом шаге ориентация остаётся сильной[10]. Таким образом, граф перевёртываний (граф смены направлений дуг), вершины которого соответствуют сильным ориентациям графа G, а рёбра соответствуют парам сильных ориентаций, отличающихся направлением одного ребра, образует частичный куб.

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

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

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

Примечания

  1. ↑ Robbins, 1939.
  2. ↑ Koh, Tay, 2002.
  3. ↑ Schrijver, 1983.
  4. ↑ Nash-Williams, 1960.
  5. ↑ Nash-Williams, 1969.
  6. ↑ 1 2 3 4 Welsh, 1997.
  7. ↑ Noy, 2001.
  8. ↑ Las Vergnas, 1980.
  9. ↑ de Fraysseix, Ossona de Mendez, Rosenstiehl, 1995.
  10. ↑ Fukuda, Prodon, Sakuma, 2001.
  11. ↑ См., например, (Atallah 1984) и (Roberts 1978).
  12. ↑ Arkin, Hassin, 2002.
  13. ↑ Vertigan, Welsh, 1992.
  14. ↑ Alon, Frieze, Welsh, 1995.

Литература

  • 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. (недоступная ссылка)
  • 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. — 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. — JSTOR 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.

Strategi Solo vs Squad di Free Fire: Cara Menang Mudah!