Loading AI tools
Из Википедии, свободной энциклопедии
Теорема Роббинса, названная по имени американского математика Герберта Роббинса[1], утверждает, что графы, имеющие сильные ориентации, — это в точности рёберно 2-связные графы. То есть тогда и только тогда можно выбрать направление каждого ребра неориентированного графа G, превратив граф в ориентированный граф, в котором существует (ориентированный) путь из любой вершины в любую другу вершину, когда граф G связен и не имеет мостов.
Характеризацию Роббинса графов сильными ориентациями можно доказать, используя ушную декомпозицию, инструмент, предложенный Роббинсом для этой цели.
Если в графе есть мост, то его нельзя сильно ориентировать, поскольку какая бы ориентация ни была выбрана, нет пути из одной вершины моста в другую.
В обратном направлении нужно показать, что любой связный граф без мостов можно сильно ориентировать. Как доказал Роббинс, любой такой граф имеет разбиение на последовательность подграфов, называемых «ушами», и в этой последовательности первый подграф является циклом, а каждый последующий подграф является путём, конечные вершины которого принадлежат предыдущим «ушам» последовательности. Если ориентировать рёбра в каждом «ухе» таким образом, что получится ориентированный цикл или ориентированный путь, получим сильную ориентацию всего графа[2].
Обобщение теоремы Роббинса на смешанные графы Бёшем и Тинделлом[3] показывает, что если в графе G некоторые рёбра ориентированы, а другие не ориентированы, и граф G для любой пары вершин содержит (ориентированный) путь, соединяющий эти вершины и не нарушающий существующие направления рёбер, то любому неориентированному ребру графа G, не являющемся мостом, может быть дано направление без изменения связности графа G. В частности, неориентированный граф без мостов может быть сделан сильно связным ориентированным графом с помощью жадного алгоритма, который назначает направление ребра за шаг, сохраняя существование пути между любыми двумя парами вершин. Такой алгоритм не может застрять в ситуации, когда нет возможности выбрать следующее направление дуге.
Сильную ориентацию заданного неориентированного графа без мостов можно найти за линейное время путём осуществления поиска в глубину по графу, ориентируя по пути все вершины при проходе дерева в направлении от корня, а все оставшиеся рёбра от потомка к предку[4] Хотя этот алгоритм непригоден для параллельных вычислительных систем вследствие сложности осуществления на этих компьютерах поиска в глубину, существуют альтернативные алгоритмы, решающие задачу эффективно в параллельной модели вычислений[5]. Известны также параллельные алгоритмы для поиска сильно связанных ориентаций для смешанных графов[6].
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.