Теорема Роббинса - Robbins theorem - Wikipedia
В теория графов, Теорема Роббинса, названный в честь Герберт Роббинс (1939 ), утверждает, что графы, имеющие сильные ориентации точно 2-реберные графы. То есть можно выбрать направление для каждого края неориентированный граф граммпревратив его в ориентированный граф у которого есть путь из каждой вершины в любую другую вершину, если и только если грамм является связаны и не имеет мост.
Ориентируемые графы
Характеристика Роббинса графов с сильной ориентацией может быть доказана с помощью разложение уха, инструмент, представленный Роббинсом для этой задачи.
Если у графа есть мост, то он не может быть строго ориентируемым, поскольку независимо от того, какая ориентация выбрана для моста, не будет пути от одной из двух конечных точек моста к другой.
В обратном направлении необходимо показать, что любой связный граф без мостов может быть сильно ориентирован. Как доказал Роббинс, каждый такой граф имеет разбиение на последовательность подграфов, называемых «ушами», в которых первый подграф в последовательности является циклом, а каждый последующий подграф - путем, причем обе конечные точки пути принадлежат более ранним ушам в последовательность. (Две конечные точки пути могут быть равны, и в этом случае подграф является циклом.) Ориентация ребер внутри каждого уха так, чтобы они образовывали направленный цикл или направленный путь, приводит к сильно связанной ориентации всего графа.[1]
Связанные результаты
Распространение теоремы Роббинса на смешанные графики к Бош и Тинделл (1980) показывает, что если грамм - граф, в котором одни ребра могут быть направленными, а другие - неориентированными, и грамм содержит путь, соблюдающий ориентацию ребер от каждой вершины до каждой другой вершины, то любое неориентированное ребро грамм который не является мостом, может быть направлен без изменения подключения грамм. В частности, неориентированный граф без мостов может быть преобразован в сильно связный ориентированный граф с помощью жадный алгоритм который направляет ребра по одному, сохраняя существование путей между каждой парой вершин; Такой алгоритм не может застрять в ситуации, в которой не могут быть приняты дополнительные решения по ориентации.
Алгоритмы и сложность
Сильную ориентацию данного неориентированного графа без мостов можно найти в линейное время путем выполнения поиск в глубину графа, ориентируя все ребра в дереве поиска первого в глубину от корня дерева и ориентируя все оставшиеся ребра (которые обязательно должны соединять предка и потомка в дереве поиска первого в глубину) от потомка к предку.[2] Хотя этот алгоритм не подходит для параллельные компьютеры, из-за сложности выполнения поиска в глубину для них доступны альтернативные алгоритмы, которые эффективно решают проблему в параллельной модели.[3] Известны также параллельные алгоритмы для поиска сильно связных ориентаций смешанных графов.[4]
Примечания
- ^ Гросс и Йеллен (2006).
- ^ Вишкин (1985) приписывает это наблюдение Аталлах (1984), и Балакришнан (1996) приписывает это Робертс (1978). Но, как Кларк и Холтон (1991) укажите, тот же алгоритм уже включен (с предположением 2-вершинная связность а не 2-краевое соединение) в основополагающей более ранней работе Хопкрофт и Тарьян (1973) по глубине первого поиска.
- ^ Вишкин (1985).
- ^ Сорокер (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.