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

твердження в теорії графів

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

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

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

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

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

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

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

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

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

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

Примітки ред.

  1. Robbins, 1939.
  2. Gross, Yellen, 2006.
  3. Boesch, Tindell, 1980.
  4. Вішкін (Vishkin, 1985) приписує це спостереження Аталлі (Atallah, 1984), а Балакрішнан (Balakrishnan, 1996) приписує його Робертсу (Roberts, 1978). Але, як зазначили Кларк і Голтон (Clark, Holton, 1991), той самий алгоритм вже з'являвся (з припущенням вершиннї 2-зв'язності замість реберної 2-зв'язності) в основоположній ранній книзі Гопкрофта і Тарджана (Hopcroft, Tarjan, 1973) про пошук у глибину.
  5. Vishkin, 1985.
  6. Soroker, 1988.

Література ред.