Теорема Роббинса
Теорема Роббинса, названная по имени американского математика Герберта Роббинса[1], утверждает, что графы, имеющие сильные ориентации, — это в точности рёберно 2-связные графы. То есть тогда и только тогда можно выбрать направление каждого ребра неориентированного графа G, превратив граф в ориентированный граф, в котором существует (ориентированный) путь из любой вершины в любую другу вершину, когда граф G связен и не имеет мостов.
Ориентируемые графы
Характеризацию Роббинса графов сильными ориентациями можно доказать, используя ушную декомпозицию, инструмент, предложенный Роббинсом для этой цели.
Если в графе есть мост, то его нельзя сильно ориентировать, поскольку какая бы ориентация ни была выбрана, нет пути из одной вершины моста в другую.
В обратном направлении нужно показать, что любой связный граф без мостов можно сильно ориентировать. Как доказал Роббинс, любой такой граф имеет разбиение на последовательность подграфов, называемых «ушами», и в этой последовательности первый подграф является циклом, а каждый последующий подграф является путём, конечные вершины которого принадлежат предыдущим «ушам» последовательности. Если ориентировать рёбра в каждом «ухе» таким образом, что получится ориентированный цикл или ориентированный путь, получим сильную ориентацию всего графа[2].
Связанные результаты
Обобщение теоремы Роббинса на смешанные графы Бёшем и Тинделлом[3] показывает, что если в графе G некоторые рёбра ориентированы, а другие не ориентированы, и граф G для любой пары вершин содержит (ориентированный) путь, соединяющий эти вершины и не нарушающий существующие направления рёбер, то любому неориентированному ребру графа G, не являющемся мостом, может быть дано направление без изменения связности графа G. В частности, неориентированный граф без мостов может быть сделан сильно связным ориентированным графом с помощью жадного алгоритма, который назначает направление ребра за шаг, сохраняя существование пути между любыми двумя парами вершин. Такой алгоритм не может застрять в ситуации, когда нет возможности выбрать следующее направление дуге.
Алгоритмы и сложность
Сильную ориентацию заданного неориентированного графа без мостов можно найти за линейное время путём осуществления поиска в глубину по графу, ориентируя по пути все вершины при проходе дерева в направлении от корня, а все оставшиеся рёбра от потомка к предку[4] Хотя этот алгоритм непригоден для параллельных вычислительных систем вследствие сложности осуществления на этих компьютерах поиска в глубину, существуют альтернативные алгоритмы, решающие задачу эффективно в параллельной модели вычислений[5]. Известны также параллельные алгоритмы для поиска сильно связанных ориентаций для смешанных графов[6].
Примечания
- ↑ Robbins, 1939.
- ↑ Gross, Yellen, 2006.
- ↑ Boesch, Tindell, 1980.
- ↑ Вишкин (Vishkin 1985) приписывает это наблюдение Аталла (Atallah 1984), а Балакришнан (Balakrishnan 1996) приписывает его Робертсу (Roberts 1978). Но как указали Кларк и Холтон (Clark, Holton 1991), тот же алгоритм уже был включён (с предположением вершинной 2-связности вместо рёберной 2-связности) в основополагающую раннюю книгу Хопкрофта и Тарьяна (Hopcroft, Tarjan 1973) о поиске в глубину.
- ↑ Vishkin, 1985.
- ↑ 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. — .
- 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..