Ациклическая ориентация

Ациклическая ориентация неориентированного графа — это назначение направлений каждому ребру (ориентация), при которой не образуется какого-либо ориентированного цикла, а потому такая ориентация превращает граф в направленный ациклический граф. Любой граф имеет ациклическую ориентацию.

14 различных ациклических ориентаций цикла с 4 вершинами, назначение направлений каждого ребра цикла, при котором полученный ориентированный граф ацикличен. Две ориентации на рисунке смежны, если отличаются лишь одним ребром.

Хроматическое число любого графа равно минимальной длине максимальному пути^[англ.] среди всех ациклических ориентаций. Ациклические ориентации связаны с раскраской посредством хроматического многочлена, который подсчитывает как ациклические ориентации, так и раскраски. Для планарных графов ациклические ориентации являются двойственными графами вполне циклических ориентаций^[англ.], и наоборот. Множеству ациклических ориентаций заданного графа может быть придана структура частичного куба, в котором две циклические ориентации смежны, если они отличаются направлением только одного ребра.

Ориентации деревьев всегда ацикличны и являются полидеревьями^[англ.]. Ациклические ориентации полных графов называются транзитивными турнирами. Биполярные ориентации являются частными случаями ациклических ориентаций, в которых имеется в точности один источник и один сток. Любой транзитивный турнир является биполярным.

Построение

Любой граф имеет ациклическую ориентацию. Одним из способов создания ациклических ориентаций является упорядочение вершин с последующим ориентированием каждого ребра от более ранней вершины в списке к более поздней. Последовательность вершин тогда становится топологическим упорядочиванием получившегося ориентированного ациклического графа (ОАГ), и любая топологическая сортировка этого ОАГ образует одну и ту же ориентацию.

Поскольку любой ОАГ имеет топологическую сортировку, любая ациклическая ориентация может быть получена указанным образом. Однако различные последовательности вершин могут привести к одинаковым ациклическим ориентациям, если получаемый ОАГ имеет несколько топологических сортировок. Например, у цикла с четырьмя вершинами (показан на рисунке) существует 24 различных последовательности, но только 14 возможных ациклических ориентаций.

Связь с раскраской

Теорема Галлаи – Хассе – Роя – Витавера утверждает, что граф имеет ациклическую ориентацию, в которой максимальный путь^[англ.] имеет не более k вершин, тогда и только тогда, когда граф может быть раскрашен не более чем в k цветов ^[1].

Число ациклических ориентаций можно посчитать, используя хроматический многочлен ${\displaystyle \chi _{G}}$, значение которого для положительного целого числа k равно числу k-раскрасок графа. Любой граф G имеет в точности ${\displaystyle |\chi _{G}(-1)|}$ различных ациклических ориентаций ^[2], так что в этом смысле ациклические ориентации можно понимать как раскраску с −1 цветом.

Двойственность

Для планарных графов ациклические ориентации являются двойственными вполне циклическим ориентациям^[англ.], ориентациям, в которых каждое ребро принадлежит ориентированному циклу — если ${\displaystyle G}$ является планарным графом, и ориентации ${\displaystyle G}$ переводятся в ориентации двойственного графа ${\displaystyle G}$ путём поворота каждого ребра на 90 градусов по часовой стрелке, то вполне циклическая ориентация графа ${\displaystyle G}$ соответствует полученной таким образом ациклической ориентации двойственного графа, и наоборот ^[3].

Подобно хроматическому многочлену, многочлен Татта ${\displaystyle T_{G}}$ графа ${\displaystyle G}$ можно использовать для подсчёта числа ациклических ориентаций ${\displaystyle G}$ как ${\displaystyle T_{G}(2,0)}$. Двойственность между ациклическими и вполне циклическими ориентациями планарных графов можно распространить тем же образом на непланарные графы — многочлен Татта двойственного графа планарного графа получается обменом аргументов многочлена ${\displaystyle T_{G}}$ и число вполне циклических ориентаций графа ${\displaystyle G}$ равно ${\displaystyle T_{G}(0,2)}$, что получается обменом аргументов в формуле для числа ациклических ориентаций^[4].

Перевёртывание ребра

Множеству ациклических ориентаций заданного графа может быть дана структура частичного куба, в котором две циклические ориентации смежны, если они отличаются направлением только одного ребра^[5]. Из этого следует, что если две различные ациклические ориентации одного и того же графа различаются направлением k рёбер, можно преобразовать одну из ориентаций в другую последовательностью k изменений ориентации одного ребра, так что каждое промежуточное состояние является ациклической ориентацией.

Частные случаи

Полидерево, результат ациклической ориентации дерева

Любая ориентация дерева ациклична. Ориентированный ациклический граф, полученный такой ориентацией называется полидеревом^{[англ.][6]}.

Ациклическая ориентация полного графа называется транзитивным турниром и она эквивалентна полному упорядочению вершин графа. В такой ориентации существует, в частности, в точности один источник и один сток.

Ациклическая ориентация произвольного графа, имеющая единственный источник и единственный сток, называется биполярной ориентацией ^[7].

Транзитивная ориентация графа является ациклической ориентацией, которая является его транзитивным замыканием. Не любой граф обладает транзитивной ориентацией. Графы, имеющие транзитивную ориентацию, являются графами сравнимости^[8]. Полные графы являются частным случаем графов сравнимости, а транзитивные турниры являются частным случаем транзитивных ориентаций.