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

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

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

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

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

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

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