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

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

Турнір — це орієнтація повного графа. Полідерево^[en] — це орієнтація неорієнтованого дерева^[3]. Гіпотеза Самнера стверджує, що будь-який турнір із ${\displaystyle 2n-2}$ вершинами містить будь-яке полідерево з 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].

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