Теорема Роббинса

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

Ориентируемые графы

Ушная декомпозиция графа без мостов. Ориентация каждого «уха» в ориентированный путь или ориентированный цикл делает весь граф сильно связным.

Характеризацию Роббинса графов сильными ориентациями можно доказать, используя ушную декомпозицию, инструмент, предложенный Роббинсом для этой цели.

Если в графе есть мост, то его нельзя сильно ориентировать, поскольку какая бы ориентация ни была выбрана, нет пути из одной вершины моста в другую.

В обратном направлении нужно показать, что любой связный граф без мостов можно сильно ориентировать. Как доказал Роббинс, любой такой граф имеет разбиение на последовательность подграфов, называемых «ушами», и в этой последовательности первый подграф является циклом, а каждый последующий подграф является путём, конечные вершины которого принадлежат предыдущим «ушам» последовательности. Если ориентировать рёбра в каждом «ухе» таким образом, что получится ориентированный цикл или ориентированный путь, получим сильную ориентацию всего графа[2].

Связанные результаты

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

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

Сильную ориентацию заданного неориентированного графа без мостов можно найти за линейное время путём осуществления поиска в глубину по графу, ориентируя по пути все вершины при проходе дерева в направлении от корня, а все оставшиеся рёбра от потомка к предку[4] Хотя этот алгоритм непригоден для параллельных вычислительных систем вследствие сложности осуществления на этих компьютерах поиска в глубину, существуют альтернативные алгоритмы, решающие задачу эффективно в параллельной модели вычислений[5]. Известны также параллельные алгоритмы для поиска сильно связанных ориентаций для смешанных графов[6].

Примечания

  1. ↑ Robbins, 1939.
  2. ↑ Gross, Yellen, 2006.
  3. ↑ Boesch, Tindell, 1980.
  4. ↑ Вишкин (Vishkin 1985) приписывает это наблюдение Аталла (Atallah 1984), а Балакришнан (Balakrishnan 1996) приписывает его Робертсу (Roberts 1978). Но как указали Кларк и Холтон (Clark, Holton 1991), тот же алгоритм уже был включён (с предположением вершинной 2-связности вместо рёберной 2-связности) в основополагающую раннюю книгу Хопкрофта и Тарьяна (Hopcroft, Tarjan 1973) о поиске в глубину.
  5. ↑ Vishkin, 1985.
  6. ↑ Soroker, 1988.

Литература

  • Mikhail J. Atallah. Parallel strong orientation of an undirected graph // Information Processing Letters. — 1984. — Т. 18, вып. 1. — С. 37–39. — doi:10.1016/0020-0190(84)90072-3.
  • V. K.Balakrishnan. Introductory Discrete Mathematics. — Mineola, NY: Dover Publications Inc., 1996. — С. 135. — ISBN 0-486-69115-2.
  • Frank Boesch, Ralph Tindell. Robbins's theorem for mixed multigraphs // The American Mathematical Monthly. — 1980. — Т. 87, вып. 9. — С. 716–719. — doi:10.2307/2321858.
  • John Clark, Derek Allan Holton. A first look at graph theory. — Teaneck, NJ: World Scientific Publishing Co. Inc., 1991. — С. 254–260. — ISBN 981-02-0489-2.
  • Jonathan L. Gross, Jay Yellen. Graph Theory and its Applications. — 2nd. — Boca Raton, FL: Chapman & Hall/CRC, 2006. — С. 498–499. — (Discrete Mathematics and its Applications). — ISBN 978-1-58488-505-4.
  • John Hopcroft, Robert Tarjan. Algorithm 447: efficient algorithms for graph manipulation // Communications of the ACM. — 1973. — Т. 16, вып. 6. — С. 372–378. — doi:10.1145/362248.362272.
  • 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).
  • Danny Soroker. Fast parallel strong orientation of mixed graphs and related augmentation problems // Journal of Algorithms. — 1988. — Т. 9, вып. 2. — С. 205–223. — doi:10.1016/0196-6774(88)90038-7.
  • Uzi Vishkin. On efficient parallel strong orientation // Information Processing Letters. — 1985. — Т. 20, вып. 5. — С. 235–240. — doi:10.1016/0020-0190(85)90025-0..

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