Орієнта́ція неорієнтованого графа — це призначення напрямків кожному ребру, що перетворює початковий граф на орієнтований граф.
Орієнтовані графи
Орієнтований граф називають напрямленим, якщо жодна з його пар вершин не з'єднана двома симетричними (різноспрямованими) ребрами. Серед орієнтованих графів ці графи вирізняються відсутністю 2-циклів (тобто граф може містити тільки одну з дуг (x, y) і (y, x)).
Турнір — це орієнтація повного графа. [en] — це орієнтація неорієнтованого дерева. стверджує, що будь-який турнір із вершинами містить будь-яке полідерево з 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 кольорів. Ациклічні орієнтації і циклічні орієнтації пов'язані між собою планарною двоїстістю. Ациклічну орієнтацію з єдиним джерелом та єдиним стоком називають .
(Транзитивна орієнтація) — це орієнтація, за якої одержуваний орієнтований граф є своїм транзитивним замиканням. Графи з транзитивними орієнтаціями називають (графами порівнянності). Їх можна визначити з частково впорядкованої множини, якщо зробити два елементи суміжними у всіх випадках, коли вони порівнянні в частковому порядку. Транзитивну орієнтацію, якщо вона існує, можна знайти за лінійний час. Однак перевірка, чи отримана орієнтація (або будь-яка задана орієнтація) дійсно транзитивна, вимагає більше часу, оскільки вона за складністю еквівалентна множенню матриць.
Ейлерова орієнтація неорієнтованого графа — це орієнтація, в якій кожна вершина має однаковий напівстепінь входу і напівстепінь виходу. Ейлерова орієнтація решітки з'являється в статистичній механіці в теорії [en].
має властивість, що певні цикли парної довжини в графі мають непарне число дуг у двох різних напрямках. Такі орієнтації завжди існують для планарних графів, але не завжди для інших типів графів. Ця орієнтація використовується в підрахунку досконалих парувань.
Примітки
- Diestel, 2005.
- Слід зауважити, що в російському перекладі книги Дістеля «oriented» перекладається як «направленный» (спрямований), а «directed» — як «ориентированный» (орієнтований), тобто поняття переставлено місцями. Це може спричинити плутанину. В цій статті, як і в інших статтях Вікіпедії, прийнято визначення з російського перекладу.
- Rebane, Pearl, 1987, с. 222–228.
- Sumner's Universal Tournament Conjecture [ 27 лютого 2014 у Wayback Machine.], Douglas B. West, retrieved 2012-08-02.
- Harary, Palmer, 1973, с. 133.
- Robbins, 1939, с. 281–283.
- Nešetřil, Ossona de Mendez, 2012, с. 42.
- de Fraysseix, Ossona de Mendez, Rosenstiehl, 1995, с. 157–179.
- Ghouila-Houri, 1962, с. 1370–1371.
- McConnell, Spinrad, 1997, с. 19–25.
- Mihail, Winkler, 1992, с. 138–145.
- Thomas, 2006, с. 963–984.
Література
- Reinhard Diestel. 1.10 Other notions of graphs // [1] — 3rd. — , 2005. — . з джерела 20 листопада 2021 Перевод:
- Рейнгард Дистель. 1.10 Другие виды графов // Теория графов. — Новосибирск : Издательство Института математики, 2002. — УДК 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 (16 червня). — С. 281–283. — DOI: .
- Jaroslav Nešetřil, Patrice Ossona de Mendez. Theorem 3.13 // Sparsity: Graphs, Structures, and Algorithms. — Heidelberg : Springer, 2012. — Т. 28. — С. 42. — (Algorithms and Combinatorics) — . — DOI:
- Hubert de Fraysseix, Patrice Ossona de Mendez, Pierre Rosenstiehl. Bipolar orientations revisited // Discrete Applied Mathematics. — 1995. — Т. 56, вип. 2–3 (16 червня). — С. 157–179. — DOI: .
- 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 // . — 1962. — Т. 254 (16 червня). — С. 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) — .
- 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:
Посилання
- Weisstein, Eric W. Орієнтація графа(англ.) на сайті Wolfram MathWorld.
- Weisstein, Eric W. Орієнтований граф(англ.) на сайті Wolfram MathWorld.
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет