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

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

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

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

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

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

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

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

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

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

Примечания

Литература