Ациклическая ориентация
Ациклическая ориентация неориентированного графа — это назначение направлений каждому ребру (ориентация), при которой не образуется какого-либо ориентированного цикла, а потому такая ориентация превращает граф в направленный ациклический граф. Любой граф имеет ациклическую ориентацию.
Хроматическое число любого графа равно минимальной длине Шаблон:Не переведено 5 среди всех ациклических ориентаций. Ациклические ориентации связаны с раскраской посредством хроматического многочлена, который подсчитывает как ациклические ориентации, так и раскраски. Для планарных графов ациклические ориентации являются двойственными графами Шаблон:Не переведено 5, и наоборот. Множеству ациклических ориентаций заданного графа может быть придана структура частичного куба, в котором две циклические ориентации смежны, если они отличаются направлением только одного ребра.
Ориентации деревьев всегда ацикличны и являются Шаблон:Не переведено 5. Ациклические ориентации полных графов называются транзитивными турнирами. Биполярные ориентации являются частными случаями ациклических ориентаций, в которых имеется в точности один источник и один сток. Любой транзитивный турнир является биполярным.
Построение
Любой граф имеет ациклическую ориентацию. Одним из способов создания ациклических ориентаций является упорядочение вершин с последующим ориентированием каждого ребра от более ранней вершины в списке к более поздней. Последовательность вершин тогда становится топологическим упорядочиванием получившегося ориентированного ациклического графа (ОАГ) и любая топологическая сортировка этого ОАГ образует одну и ту же ориентацию.
Поскольку любой ОАГ имеет топологическую сортировку, любая ациклическая ориентация может быть получена указанным образом. Однако различные последовательности вершин могут привести к одинаковым ациклическим ориентациям, если получаемый ОАГ имеет несколько топологических сортировок. Например, у цикла с четырьмя вершинами (показан на рисунке) существует 24 различных последовательности, но только 14 возможных ациклических ориентаций.
Связь с раскраской
Теорема Галлаи – Хассе – Роя – Витавера утверждает, что граф имеет ациклическую ориентацию, в которой Шаблон:Не переведено 5 имеет не более Шаблон:Mvar вершин, тогда и только тогда, когда граф может быть раскрашен не более чем в Шаблон:Mvar цветов Шаблон:Sfn.
Число ациклических ориентаций можно посчитать, используя хроматический многочлен , значение которого для положительного целого числа Шаблон:Mvar равно числу Шаблон:Mvar-раскрасок графа. Любой граф Шаблон:Mvar имеет в точности различных ациклических ориентаций Шаблон:Sfn, так что в этом смысле ациклические ориентации можно понимать как раскраску с Шаблон:Math цветом.
Двойственность
Для планарных графов ациклические ориентации являются двойственными Шаблон:Не переведено 5, ориентациям, в которых каждое ребро принадлежит ориентированному циклу — если является планарным графом, и ориентации переводятся в ориентации двойственного графа путём поворота каждого ребра на 90 градусов по часовой стрелке, то вполне циклическая ориентация графа соответствует полученной таким образом ациклической ориентации двойственного графа, и наоборот Шаблон:Sfn.
Подобно хроматическому многочлену, многочлен Татта графа можно использовать для подсчёта числа ациклических ориентаций как . Двойственность между ациклическими и вполне циклическими ориентациями планарных графов можно распространить тем же образом на непланарные графы — многочлен Татта двойственного графа планарного графа получается обменом аргументов многочлена и число вполне циклических ориентаций графа равно , что получается обменом аргументов в формуле для числа ациклических ориентацийШаблон:Sfn.
Перевёртывание ребра
Множеству ациклических ориентаций заданного графа может быть дана структура частичного куба, в котором две циклические ориентации смежны, если они отличаются направлением только одного ребраШаблон:Sfn. Из этого следует, что если две различные ациклические ориентации одного и того же графа различаются направлением Шаблон:Mvar рёбер, можно преобразовать одну из ориентаций в другую последовательностью Шаблон:Mvar изменений ориентации одного ребра, так что каждое промежуточное состояние является ациклической ориентацией.
Частные случаи
Любая ориентация дерева ациклична. Ориентированный ациклический граф, полученный такой ориентацией называется Шаблон:Не переведено 5Шаблон:Sfn.
Ациклическая ориентация полного графа называется транзитивным турниром и она эквивалентна полному упорядочению вершин графа. В такой ориентации существует, в частности, в точности один источник и один сток.
Ациклическая ориентация произвольного графа, имеющая единственный источник и единственный сток, называется биполярной ориентацией Шаблон:Sfn.
Транзитивная ориентация графа является ациклической ориентацией, которая является его транзитивным замыканием. Не любой граф обладает транзитивной ориентацией. Графы, имеющие транзитивную ориентацию, являются графами сравнимостиШаблон:Sfn. Полные графы являются частным случаем графов сравнимости, а транзитивные турниры являются частным случаем транзитивных ориентаций.