Ациклічна орієнтація
Ациклічна орієнтаціянеорієнтованого графа - це призначення напрямків кожному ребру (орієнтація), при якій не утворюється якогось орієнтованого циклу, а тому така орієнтація перетворює граф на спрямований ациклічний граф. Будь-який граф має ациклічну орієнтацію.
Хроматичне число будь-якого графа дорівнює мінімальній довжині максимального шляху серед усіх ациклічних орієнтацій. Ациклічні орієнтації пов'язані з розфарбуванням за допомогою хроматичного багаточлена, який підраховує як ациклічні орієнтації, так і забарвлення. Для планарних графів ациклічні орієнтації є подвійними графами цілком циклічних орієнтацій [en] і навпаки. Багато ациклічних орієнтацій заданого графа може бути надана структура часткового куба, в якому дві циклічні орієнтації суміжні, якщо вони відрізняються напрямом тільки одного ребра.
Орієнтації дерев завжди ациклічні і є полідеревами. Ациклічні орієнтації повних графів називають транзитивними турнірами. Біполярні орієнтації є окремими випадками ациклічних орієнтацій, в яких є точно одне джерело і один стік. Будь-який транзитивний турнір є біполярним.
Зміст
Будь-який граф має ациклічну орієнтацію. Одним із способів створення ациклічних орієнтацій є впорядкування вершин з подальшим орієнтуванням кожного ребра від більш ранньої вершини в списку до пізнішої. Послідовність вершин тоді стає топологічним упорядкуванням орієнтованого ациклічного графа (ОАГ), що вийшов, і будь-яка топологічна сортування цього ОАГ утворює одну і ту ж орієнтацію.
Оскільки будь-яка ОАГ має топологічне сортування, будь-яка ациклічна орієнтація може бути отриманавказаним чином. Однак різні послідовності вершин можуть призвести до однакових ациклічних орієнтацій, якщо ОАГ має кілька топологічних сортувань. Наприклад, у циклу з чотирма вершинами (показаний малюнку) існує 24 різних послідовності, але тільки 14 можливих ациклічних орієнтацій.
Теорема Галлаї – Хассе – Роя – Вітавера стверджує, що граф має ациклічну орієнтацію, у якій максимальний шлях [en] має трохи більше k вершин, тоді й лише тоді, коли граф то, можливо розфарбований лише у k кольорів [1] .
Багато ациклічних орієнтацій заданого графа може бути дана структура часткового куба, в якому дві циклічні орієнтації суміжні, якщо вони відрізняються напрямом тільки одного ребра [5] . З цього випливає, що якщо дві різні ациклічні орієнтації одного й того ж графа розрізняються напрямком k ребер, можна перетворити одну з орієнтацій на іншу послідовністю k змін орієнтації одного ребра, так що кожен проміжний стан є ациклічною орієнтацією.
Будь-яка орієнтація дерева ациклічна. Орієнтований ациклічний граф, отриманий такою орієнтацією називається полідеревом [6] .
Ациклічна орієнтація повного графа називається транзитивним турніром і вона еквівалентна повному упорядкуванню вершин графа. У такій орієнтації існує, зокрема, точно одне джерело і один стік.
Ациклічна орієнтація довільного графа, що має єдине джерело та єдиний стік, називається біполярною орієнтацією [7] .
Транзитивна орієнтація графа є ациклічною орієнтацією, яка його транзитивним замиканням. Не будь-який граф має транзитивну орієнтацію. Графи, що мають транзитивну орієнтацію, єграфами порівнянності [8]. Повні графи є окремим випадком графів порівнянності, а транзитивні турніри є окремим випадком транзитивних орієнтацій.