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

Эта статья о теореме Роббинса в теории графов. Чтобы узнать о теореме Робина в теории чисел, см. функцию делителя .

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

Управляемые графики

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

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

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

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

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

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

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

Сильная ориентация данного неориентированного графа без мостов может быть найдена за линейное время , выполняя поиск в глубину графа, ориентируя все ребра в дереве поиска в глубину от корня дерева и ориентируя все оставшиеся ребра (которые обязательно должны соединять предка и потомка в дереве поиска в глубину) от потомка к предку. Хотя этот алгоритм не подходит для параллельных компьютеров , из-за сложности выполнения на них поиска в глубину доступны альтернативные алгоритмы, которые эффективно решают задачу в параллельной модели. Известны также параллельные алгоритмы для поиска сильно связных ориентаций смешанных графов.

Приложения

Первоначально Роббинс мотивировал свою работу применением дизайна улиц с односторонним движением в городах. Другое применение возникает в области структурной жесткости , в теории крепления решеток . Эта теория касается проблемы создания квадратной сетки, состоящей из жестких стержней, прикрепленных к гибким соединениям, жесткой за счет добавления дополнительных стержней или проволок в качестве поперечных связей по диагоналям сетки. Набор добавленных стержней делает сетку жесткой, если связанный неориентированный граф связен, и дважды скреплен (остается жесткой, если какое-либо ребро удалено), если, кроме того, она не имеет мостов. Аналогично, набор добавленных проводов (которые могут изгибаться, чтобы уменьшить расстояние между точками, которые они соединяют, но не могут расширяться) делает сетку жесткой, если связанный ориентированный граф сильно связан. Следовательно, если переосмыслить теорему Роббинса для этого приложения, конструкции с двойными связями — это именно те конструкции, стержни которых можно заменить проволоками, оставаясь при этом жесткими.

Ссылки

• Аталлах, Михаил Дж. (1984), «Параллельная сильная ориентация неориентированного графа» , Information Processing Letters , 18 (1): 37–39, doi : 10.1016/0020-0190(84)90072-3 , MR   0742079 .
• Багливо, Дженни А .; Грейвер, Джек Э. (1983), «3.10 Несущие конструкции», Распространенность и симметрия в дизайне и архитектуре , Кембриджские городские и архитектурные исследования, Кембридж, Великобритания: Cambridge University Press, стр. 76–87, ISBN  9780521297844
• Балакришнан, В.К. (1996), «4.6 Сильная ориентация графов», Вводная дискретная математика , Минеола, Нью-Йорк: Dover Publications Inc., стр. 135, ISBN  978-0-486-69115-2 , МР   1402469 .
• Бош, Фрэнк; Тинделл, Ральф (1980), «Теорема Роббинса для смешанных мультиграфов», The American Mathematical Monthly , 87 (9): 716–719, doi : 10.2307/2321858 , JSTOR   2321858 , MR   0602828 .
• Кларк, Джон; Холтон, Дерек Аллан (1991), «7.4 Транспортный поток», Первый взгляд на теорию графов , Тинек, Нью-Джерси: World Scientific Publishing Co. Inc., стр. 254–260, ISBN.  978-981-02-0489-1 , МР   1119781 .
• Гросс, Джонатан Л.; Йеллен, Джей (2006), «Характеристика сильно ориентируемых графов», Теория графов и ее приложения , Дискретная математика и ее приложения (2-е изд.), Бока-Ратон, Флорида: Chapman & Hall/CRC, стр. 498–499, ISBN  978-1-58488-505-4 , МР   2181153 .
• Хопкрофт, Джон ; Тарьян, Роберт (1973), «Алгоритм 447: эффективные алгоритмы манипулирования графами», Communications of the ACM , 16 (6): 372–378, doi : 10.1145/362248.362272 , S2CID   14772567 .
• Роббинс, HE (1939), «Теорема о графах с применением к задаче управления дорожным движением», American Mathematical Monthly , 46 (5): 281–283, doi : 10.2307/2303897 , JSTOR   2303897 .
• Робертс, Фред С. (1978), «Глава 2. Проблема улицы с односторонним движением», Теория графов и ее приложения к проблемам общества , Серия региональных конференций CBMS-NSF по прикладной математике, том. 29, Филадельфия, Пенсильвания: Общество промышленной и прикладной математики (SIAM), стр. 7–14, ISBN.  9780898710267 , МР   0508050 .
• Сорокер, Дэнни (1988), «Быстрая параллельная сильная ориентация смешанных графов и связанные с ними проблемы расширения», Journal of Algorithms , 9 (2): 205–223, doi : 10.1016/0196-6774(88)90038-7 , MR   0936106 .
• Вишкин, Узи (1985), «Об эффективной параллельной сильной ориентации», Information Processing Letters , 20 (5): 235–240, doi : 10.1016/0020-0190(85)90025-0 , MR   0801988 .