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

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

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

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

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

Число неізоморфних напрямлених графів з 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-циклу між кожною парою вершин, які не є кінцями якоїсь дуги. Ця відповідність бієктивна. Тому та ж послідовність чисел розв'язує задачу перерахування графів для повних орграфів. Існує явна, але складна формула для чисел цієї послідовності[5].

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

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

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

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

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

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

Примітки

  1. ↑ Diestel, 2005.
  2. ↑ Слід зауважити, що в російському перекладі книги Дістеля «oriented» перекладається як «направленный» (спрямований), а «directed» — як «ориентированный» (орієнтований), тобто поняття переставлено місцями. Це може спричинити плутанину. В цій статті, як і в інших статтях Вікіпедії, прийнято визначення з російського перекладу.
  3. ↑ Rebane, Pearl, 1987, с. 222–228.
  4. ↑ Sumner's Universal Tournament Conjecture [Архівовано 27 лютого 2014 у Wayback Machine.], Douglas B. West, retrieved 2012-08-02.
  5. ↑ Harary, Palmer, 1973, с. 133.
  6. ↑ Robbins, 1939, с. 281–283.
  7. ↑ Nešetřil, Ossona de Mendez, 2012, с. 42.
  8. ↑ de Fraysseix, Ossona de Mendez, Rosenstiehl, 1995, с. 157–179.
  9. ↑ Ghouila-Houri, 1962, с. 1370–1371.
  10. ↑ McConnell, Spinrad, 1997, с. 19–25.
  11. ↑ Mihail, Winkler, 1992, с. 138–145.
  12. ↑ Thomas, 2006, с. 963–984.

Література

  • 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. Перевод:
  • Robbins H. E. A theorem on graphs, with an application to a problem of traffic control // The American Mathematical Monthly. — 1939. — Т. 46, вип. 5 (15 січня). — С. 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 (15 січня). — С. 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 (15 січня). — С. 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.

Посилання