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

Теоре́ма Ро́ббінса, названа на честь американського математика Герберта Роббінса, стверджує, що графи, які мають сильні орієнтації — це точно 2-реберно-зв'язні графи. Тобто тоді й лише тоді можна вибрати напрямок кожного ребра неорієнтованого графа G, перетворивши граф на орієнтований граф, у якому існує (орієнтований) шлях з будь-якої вершини в будь-яку іншу вершину, коли граф G зв'язний і не має мостів.

Орієнтовані графи

Вушна декомпозиція графа без мостів. Орієнтація кожного «вуха» в орієнтований шлях або орієнтований цикл робить весь граф сильно зв'язним.

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

Якщо в графі є міст, то його не можна сильно орієнтувати, оскільки, яку б орієнтацію не обрали, немає шляху з однієї вершини моста в іншу.

З іншого боку, потрібно показати, що будь-який зв'язний граф без мостів можна сильно орієнтувати. Як довів Роббінс, будь-який такий граф має розбиття на послідовність підграфів, званих «вухами», і в цій послідовності перший підграф є циклом, а кожен наступний підграф є шляхом, кінцеві вершини якого належать попереднім «вухам» послідовності. Якщо орієнтувати ребра в кожному «вусі» так, щоб вийшов орієнтований цикл або орієнтований шлях, отримаємо сильну орієнтацію всього графа.

Пов'язані результати

Узагальнення Беша і Тінделла теореми Роббінса на змішані графи показує, що якщо в графі G деякі ребра орієнтовані, а інші не орієнтовані, і граф G для будь-якої пари вершин містить (орієнтований) шлях, що з'єднує ці вершини і не порушує наявних напрямків ребер, то будь-якому неорієнтованому ребру графа G, що не є мостом, можна надати напрямок без зміни зв'язності графа G. Зокрема, неорієнтований граф без мостів можна зробити сильно зв'язним орієнтованим графом за допомогою жадібного алгоритму, який призначає напрямок ребра за крок, зберігаючи існування шляху між будь-якими двома парами вершин. Такий алгоритм не може застрягти в ситуації, коли неможливо вибрати наступний напрямок для дуги.

Алгоритми і складність

Сильну орієнтацію заданого неорієнтованого графа без мостів можна знайти за лінійний час пошуком у глибину за графом, орієнтуючи дорогою всі вершини при проході дерева в напрямку від кореня, а решту ребер від нащадка до предка Хоча цей алгоритм непридатний для паралельних обчислювальних систем внаслідок складності здійснення на цих комп'ютерах пошуку в глибину, існують альтернативні алгоритми, які ефективно розв'язують задачу в паралельній моделі обчислень. Відомі також паралельні алгоритми для пошуку сильно зв'язних орієнтацій для змішаних графів.

Література

• Mikhail J. Atallah. Parallel strong orientation of an undirected graph // Information Processing Letters. — 1984. — Т. 18, вип. 1. — С. 37–39. — DOI:10.1016/0020-0190(84)90072-3.
• V. K.Balakrishnan. Introductory Discrete Mathematics. — Mineola, NY : Dover Publications Inc, 1996. — С. 135. — ISBN 0-486-69115-2.
• Frank Boesch, Ralph Tindell. Robbins's theorem for mixed multigraphs // The American Mathematical Monthly. — 1980. — Т. 87, вип. 9. — С. 716–719. — DOI:10.2307/2321858.
• John Clark, Derek Allan Holton. A first look at graph theory. — Teaneck, NJ : World Scientific Publishing Co. Inc, 1991. — С. 254–260. — ISBN 981-02-0489-2.
• Jonathan L. Gross, Jay Yellen. Graph Theory and its Applications. — 2nd. — Boca Raton, FL : Chapman & Hall/CRC, 2006. — С. 498–499. — (Discrete Mathematics and its Applications) — ISBN 978-1-58488-505-4.
• John Hopcroft, Robert Tarjan. Algorithm 447: efficient algorithms for graph manipulation // Communications of the ACM. — 1973. — Т. 16, вип. 6. — С. 372–378. — DOI:10.1145/362248.362272.
• H. E. Robbins. A theorem on graphs, with an application to a problem on traffic control // The American Mathematical Monthly. — 1939. — Т. 46. — С. 281–283. — DOI:10.2307/2303897.
• Fred S. Roberts. Graph Theory and its Applications to Problems of Society. — Philadelphia, Pa. : Society for Industrial and Applied Mathematics (SIAM), 1978. — Т. 29. — С. 7–14. — (CBMS-NSF Regional Conference Series in Applied Mathematics)
• Danny Soroker. Fast parallel strong orientation of mixed graphs and related augmentation problems // Journal of Algorithms. — 1988. — Т. 9, вип. 2. — С. 205–223. — DOI:10.1016/0196-6774(88)90038-7.
• Uzi Vishkin. On efficient parallel strong orientation // Information Processing Letters. — 1985. — Т. 20, вип. 5. — С. 235–240. — DOI:10.1016/0020-0190(85)90025-0..