Орієнтація (теорія графів)

Орієнта́ція неорієнтованого графа — це призначення напрямків кожному ребру, що перетворює початковий граф на орієнтований граф.

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

Орієнтований граф називають напрямленим, якщо жодна з його пар вершин не з'єднана двома симетричними (різноспрямованими) ребрами. Серед орієнтованих графів ці графи вирізняються відсутністю 2-циклів (тобто граф може містити тільки одну з дуг (x, y) і (y, x)).

Турнір — це орієнтація повного графа. Полідерево — це орієнтація неорієнтованого дерева. Гіпотеза Самнера стверджує, що будь-який турнір із $2n-2$ вершинами містить будь-яке полідерево з n вершинами.

Число неізоморфних напрямлених графів з n вершинами (для n=1, 2, 3, …) дорівнює

1; 2; 7; 42; 582; 21,480; 2,142,288; 575,016,219; 415,939,243,032; … (послідовність A001174 з Онлайн енциклопедії послідовностей цілих чисел, OEIS).

Напрямлені графи перебувають в один-до-одного відповідності з повними орієнтованими графами (графами, в яких є орієнтована дуга між будь-якою парою різних вершин). Повний орієнтований граф можна перетворити в напрямлений граф видаленням усіх 2-циклів, і навпаки, напрямлений граф можна перетворити на повний орієнтований граф додаванням 2-циклу між кожною парою вершин, які не є кінцями якоїсь дуги. Ця відповідність бієктивна. Тому та ж послідовність чисел розв'язує задачу перерахування графів для повних орграфів. Існує явна, але складна формула для чисел цієї послідовності.

Обмежені орієнтації

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

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

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

Ейлерова орієнтація неорієнтованого графа — це орієнтація, в якій кожна вершина має однаковий напівстепінь входу і напівстепінь виходу. Ейлерова орієнтація решітки з'являється в статистичній механіці в теорії моделей крижаного типу.

Пфаффова орієнтація має властивість, що певні цикли парної довжини в графі мають непарне число дуг у двох різних напрямках. Такі орієнтації завжди існують для планарних графів, але не завжди для інших типів графів. Ця орієнтація використовується в алгоритмі FKT підрахунку досконалих парувань.

Література

• Reinhard Diestel. 1.10 Other notions of graphs // [1] — 3rd. — Springer, 2005. — ISBN 3-540-26182-6. Архівовано з джерела 20 листопада 2021 Перевод:
  • Рейнгард Дистель. 1.10 Другие виды графов // Теория графов. — Новосибирск : Издательство Института математики, 2002. — ISBN 5-86134-101-X УДК 519.17 ББЛ 22.17.
• George Rebane, Judea Pearl. The recovery of causal poly-trees from statistical data // Proc. 3rd Annual Conference on Uncertainty in Artificial Intelligence (UAI 1987), Seattle, WA, USA, July 1987. — 1987. — С. 222–228.^{[недоступне посилання з Май 2019]}
• Frank Harary, Edgar M. Palmer. Formula 5.4.13 // Graphical Enumeration. — New York : Academic Press, 1973. — С. 133. Перевод:
  • Ф. Харари, Э. Палмер. Формула 5.4.13 // Перечисление графов. — М. : Мир, 1977. — С. 163.
• Robbins H. E. A theorem on graphs, with an application to a problem of traffic control // The American Mathematical Monthly. — 1939. — Т. 46, вип. 5 (5 листопада). — С. 281–283. — DOI:10.2307/2303897.
• Jaroslav Nešetřil, Patrice Ossona de Mendez. Theorem 3.13 // Sparsity: Graphs, Structures, and Algorithms. — Heidelberg : Springer, 2012. — Т. 28. — С. 42. — (Algorithms and Combinatorics) — ISBN 978-3-642-27874-7. — DOI:10.1007/978-3-642-27875-4.
• Hubert de Fraysseix, Patrice Ossona de Mendez, Pierre Rosenstiehl. Bipolar orientations revisited // Discrete Applied Mathematics. — 1995. — Т. 56, вип. 2–3 (5 листопада). — С. 157–179. — DOI:10.1016/0166-218X(94)00085-R.
• Alain Ghouila-Houri. Caractérisation des graphes non orientés dont on peut orienter les arrêtes de manière à obtenir le graphe d'une relation d'ordre // Les Comptes rendus de l'Académie des sciences. — 1962. — Т. 254 (5 листопада). — С. 1370–1371.
• McConnell R. M., Spinrad J. Linear-time transitive orientation // 8th ACM-SIAM Symposium on Discrete Algorithms. — 1997. — С. 19–25.
• Milena Mihail, Peter Winkler. On the Number of Eularian Orientations of a Graph // Proceedings of the Third Annual ACM-SIAM Symposium on Discrete Algorithms. — Philadelphia, PA, USA : Society for Industrial and Applied Mathematics, 1992. — С. 138–145. — (SODA '92) — ISBN 0-89791-466-X.
• Robin Thomas (mathematician). A survey of Pfaffian orientations of graphs // International Congress of Mathematicians. Vol. III. — Eur. Math. Soc., Zürich, 2006. — С. 963–984. — DOI:10.4171/022-3/47.

Посилання

• Weisstein, Eric W. Орієнтація графа(англ.) на сайті Wolfram MathWorld.
• Weisstein, Eric W. Орієнтований граф(англ.) на сайті Wolfram MathWorld.