Теорема Роббинса - Robbins theorem

Эта статья посвящена теореме Роббинса в теории графов. По теореме Робина в теории чисел см. делительная функция.

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

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

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

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

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

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

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

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

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

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

Примечания

1. Гросс и Йеллен (2006).
2. Вишкин (1985) приписывает это наблюдение Аталлах (1984), и Балакришнан (1996) приписывает это Робертс (1978). Но, как Кларк и Холтон (1991) укажите, тот же алгоритм уже включен (с предположением 2-вершинная связность а не 2-краевое соединение) в основополагающей более ранней работе Хопкрофт и Тарьян (1973) по глубине первого поиска.
3. Вишкин (1985).
4. Сорокер (1988).

Рекомендации

• Аталлах, Михаил Дж. (1984), «Параллельная сильная ориентация неориентированного графа», Письма об обработке информации, 18 (1): 37–39, Дои:10.1016/0020-0190(84)90072-3, МИСТЕР  0742079.
• Балакришнан В. К. (1996), "4.6 Сильная ориентация графов", Вводная дискретная математика, Минеола, Нью-Йорк: Dover Publications Inc., стр. 135, ISBN  978-0-486-69115-2, МИСТЕР  1402469.
• Бош, Франк; Тинделл, Ральф (1980), "Теорема Роббинса для смешанных мультиграфов", Американский математический ежемесячник, 87 (9): 716–719, Дои:10.2307/2321858, JSTOR  2321858, МИСТЕР  0602828.
• Кларк, Джон; Холтон, Дерек Аллан (1991), «7.4 Traffic Flow», Первый взгляд на теорию графов, Тинек, штат Нью-Джерси: 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: эффективные алгоритмы манипулирования графами», Коммуникации ACM, 16 (6): 372–378, Дои:10.1145/362248.362272, S2CID  14772567.
• Роббинс, Х. (1939), «Теорема о графах в приложении к проблеме управления движением», Американский математический ежемесячный журнал, 46 (5): 281–283, Дои:10.2307/2303897, HDL:10338.dmlcz / 101517, JSTOR  2303897.
• Робертс, Фред С. (1978), "Глава 2. Проблема улицы с односторонним движением", Теория графов и ее приложения к проблемам общества, Серия региональных конференций CBMS-NSF по прикладной математике, 29, Филадельфия, Пенсильвания: Общество промышленной и прикладной математики (SIAM), стр. 7–14, ISBN  9780898710267, МИСТЕР  0508050.
• Сорокер, Дэнни (1988), "Быстрая параллельная сильная ориентация смешанных графов и связанные проблемы дополнения", Журнал алгоритмов, 9 (2): 205–223, Дои:10.1016/0196-6774(88)90038-7, МИСТЕР  0936106.
• Вишкин, Узи (1985), "Об эффективной параллельной сильной ориентации", Письма об обработке информации, 20 (5): 235–240, Дои:10.1016/0020-0190(85)90025-0, МИСТЕР  0801988.