Орієнтація (теорія графів)
Орієнта́ція неорієнтованого графа — це призначення напрямків кожному ребру, що перетворює початковий граф на орієнтований граф.
Орієнтовані графи
Орієнтований граф називають напрямленим, якщо жодна з його пар вершин не з'єднана двома симетричними (різноспрямованими) ребрами. Серед орієнтованих графів ці графи вирізняються відсутністю 2-циклів (тобто граф може містити тільки одну з дуг Шаблон:Nobr і Шаблон:Nobr)Шаблон:Sfn[1].
Турнір — це орієнтація повного графа. Шаблон:Не перекладено — це орієнтація неорієнтованого дереваШаблон:Sfn. Гіпотеза Самнера стверджує, що будь-який турнір із вершинами містить будь-яке полідерево з n вершинамиШаблон:R.
Число неізоморфних напрямлених графів з n вершинами (для n=1, 2, 3, …) дорівнює
- 1; 2; 7; 42; 582; 21,480; 2,142,288; 575,016,219; 415,939,243,032; … (Шаблон:OEIS).
Напрямлені графи перебувають в один-до-одного відповідності з повними орієнтованими графами (графами, в яких є орієнтована дуга між будь-якою парою різних вершин). Повний орієнтований граф можна перетворити в напрямлений граф видаленням усіх 2-циклів, і навпаки, напрямлений граф можна перетворити на повний орієнтований граф додаванням 2-циклу між кожною парою вершин, які не є кінцями якоїсь дуги. Ця відповідність бієктивна. Тому та ж послідовність чисел розв'язує задачу перерахування графів для повних орграфів. Існує явна, але складна формула для чисел цієї послідовностіШаблон:Sfn.
Обмежені орієнтації
Сильна орієнтація — це орієнтація, внаслідок якої отримуємо сильно зв'язний орграф. Тісно зв'язані цілком циклічні орієнтації — це орієнтації, в яких кожна дуга належить принаймні одному простому циклу. Орієнтація неорієнтованого графа G цілком циклічна тоді й лише тоді, коли вона є сильною орієнтацією будь-якої компоненти зв'язності графа G. Теорема Роббінса каже, що граф має сильну орієнтацію тоді й лише тоді, коли він реберно 2-зв'язний. Незв'язні графи можуть мати цілком циклічні орієнтації, але тільки в разі, коли в них немає мостаШаблон:Sfn.
Ациклічна орієнтація — це орієнтація, що приводить до орієнтованого ациклічного графа. Будь-який граф має ациклічну орієнтацію. Всі ациклічні орієнтації можна отримати, розташувавши вершини в ряд, а потім спрямовуючи дугу з ранішої вершини в пізнішу в цьому ряду. Теорема Галлаї — Гассе — Роя — Вітавера стверджує, що граф має ациклічну орієнтацію, в якій найдовший шлях має максимум k вершин, тоді й лише тоді, коли його можна розфарбувати максимум у k кольорівШаблон:Sfn. Ациклічні орієнтації і циклічні орієнтації пов'язані між собою планарною двоїстістю. Ациклічну орієнтацію з єдиним джерелом та єдиним стоком називають біполярною орієнтацієюШаблон:Sfn.
Транзитивна орієнтація — це орієнтація, за якої одержуваний орієнтований граф є своїм транзитивним замиканням. Графи з транзитивними орієнтаціями називають графами порівнянності. Їх можна визначити з частково впорядкованої множини, якщо зробити два елементи суміжними у всіх випадках, коли вони порівнянні в частковому порядкуШаблон:Sfn. Транзитивну орієнтацію, якщо вона існує, можна знайти за лінійний часШаблон:Sfn. Однак перевірка, чи отримана орієнтація (або будь-яка задана орієнтація) дійсно транзитивна, вимагає більше часу, оскільки вона за складністю еквівалентна множенню матриць.
Ейлерова орієнтація неорієнтованого графа — це орієнтація, в якій кожна вершина має однаковий напівстепінь входу і напівстепінь виходу. Ейлерова орієнтація решітки з'являється в статистичній механіці в теорії Шаблон:Не перекладеноШаблон:Sfn.
Пфаффова орієнтація має властивість, що певні цикли парної довжини в графі мають непарне число дуг у двох різних напрямках. Такі орієнтації завжди існують для планарних графів, але не завжди для інших типів графів. Ця орієнтація використовується в алгоритмі FKT підрахунку досконалих паруваньШаблон:Sfn.
Примітки
Література
- Шаблон:Книга Перевод:
- Шаблон:КнигаШаблон:Недоступне посилання
- Шаблон:Книга Перевод:
- Шаблон:Стаття
- Шаблон:Книга
- Шаблон:Стаття
- Шаблон:Стаття
- Шаблон:Книга
- Шаблон:Книга
- Шаблон:Книга
Посилання
- ↑ Слід зауважити, що в російському перекладі книги Дістеля «oriented» перекладається як «направленный» (спрямований), а «directed» — як «ориентированный» (орієнтований), тобто поняття переставлено місцями. Це може спричинити плутанину. В цій статті, як і в інших статтях Вікіпедії, прийнято визначення з російського перекладу.