В теории графов , теорема Роббинс , названная в честь Герберта Robbins ( 1939 ), утверждает , что графики , которые имеют сильные ориентации в точности 2-реберно связные графы . То есть, можно выбрать направление для каждой кромки неориентированного графа G , превращая его в ориентированный граф , который имеет путь от каждой вершины к любой другой вершины, тогда и только тогда , когда G будет подключен и не имеет никакого моста .
Ориентируемые графы
Характеристика Роббинсом графов с сильной ориентацией может быть доказана с помощью разложения по уху , инструмента, введенного Роббинсом для этой задачи.
Если у графа есть мост, он не может быть строго ориентируемым, поскольку независимо от того, какая ориентация выбрана для моста, не будет пути от одной из двух конечных точек моста к другой.
В обратном направлении необходимо показать, что любой связный граф без мостов может быть сильно ориентирован. Как доказал Роббинс, каждый такой граф имеет разбиение на последовательность подграфов, называемых «ушами», в которых первый подграф в последовательности является циклом, а каждый последующий подграф - путем, причем обе конечные точки пути принадлежат более ранним ушам в последовательность. (Две конечные точки пути могут быть равны, и в этом случае подграф является циклом.) Ориентация ребер внутри каждого уха так, чтобы они образовывали направленный цикл или направленный путь, приводит к сильно связанной ориентации всего графа. [1]
Связанные результаты
Расширение теоремы Роббинс на смешанные графы по Бош & Tindell (1980) показывает , что, если G представляет собой график , в котором некоторые ребра могут быть направлены и другими неориентированным и G содержит путь соблюдая край ориентацию от каждой вершины к любому другим вершина, то любой неориентированный край G , который не мост может быть сделано без изменения направлены связности G . В частности, неориентированный граф без мостов может быть преобразован в сильно связанный ориентированный граф с помощью жадного алгоритма, который направляет ребра по одному, сохраняя при этом существование путей между каждой парой вершин; Такой алгоритм не может застрять в ситуации, в которой не могут быть приняты дополнительные решения по ориентации.
Алгоритмы и сложность
Сильная ориентация данного неориентированного графа без мостов может быть найдена за линейное время , выполняя поиск в глубину графа, ориентируя все ребра в дереве поиска сначала в глубину от корня дерева и ориентируя все оставшиеся ребра (которые обязательно должны соединить предка и потомка в дереве поиска первого глубины) от потомка к предку. [2] Хотя этот алгоритм не подходит для параллельных компьютеров , из-за сложности выполнения на них поиска в глубину доступны альтернативные алгоритмы, которые эффективно решают проблему в параллельной модели. [3] Известны также параллельные алгоритмы для поиска сильно связных ориентаций смешанных графов. [4]
Приложения
Роббинс изначально мотивировал свою работу приложением к проектированию улиц с односторонним движением в городах. Другое приложение возникает в области жесткости конструкции , в теории решетчатых связей . Эта теория касается проблемы создания квадратной сетки, состоящей из жестких стержней, прикрепленных к гибким соединениям, жесткой путем добавления дополнительных стержней или проволоки в качестве поперечных связей на диагоналях сетки. Набор добавленных стержней делает сетку жесткой, если связанный неориентированный граф связан, и имеет двойную связь (остается жесткой, если какое-либо ребро удалено), если, кроме того, она не имеет мостов. Аналогично, набор добавленных проводов (которые могут изгибаться для уменьшения расстояния между точками, которые они соединяют, но не могут расширяться) делает сетку жесткой, если связанный ориентированный граф сильно связан. [5] Таким образом, переосмысливая теорему Роббинса для этого приложения, конструкции с двойными связями - это в точности конструкции, стержни которых могут быть заменены проволокой, оставаясь при этом жесткими.
Заметки
- ^ Гросс и Йеллен (2006) .
- ^ Vishkin (1985) кредиты это наблюдение Аталла (1984) , и Балакришнана (1996) кредиты это Робертса (1978) . Но, какотмечают Кларк и Холтон (1991) , тот же алгоритм уже включен (с допущением о 2-вершинной связности, а не о 2-реберной связности) в основополагающую более раннюю работу Хопкрофта и Тарьяна (1973) по глубине. поиск.
- ^ Vishkin (1985) .
- ^ Сорокер (1988) .
- ^ Baglivo & Graver (1983) .
Рекомендации
- Аталлах, Михаил Дж. (1984), «Параллельная сильная ориентация неориентированного графа» , Письма об обработке информации , 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: эффективные алгоритмы для манипуляций графа", коммуникаций 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.
- Soroker, Дани (1988), "Быстрый параллельно сильную ориентацию смешанных графиков и связанных с ними проблем дополнения", журнал алгоритмов , 9 (2): 205-223, DOI : 10,1016 / 0196-6774 (88) 90038-7 , МР 0936106.
- Вишкин, Узи (1985), «Об эффективной параллельной сильной ориентации», Письма об обработке информации , 20 (5): 235–240, DOI : 10.1016 / 0020-0190 (85) 90025-0 , MR 0801988.