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

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

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

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

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

Строительство

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

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

Отношение к окраске

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

Количество ациклических ориентаций можно подсчитать с помощью хроматического полинома $\chi _{G}$, значение которого в положительном целом k является количеством k -раскрасок графа.Каждый граф G имеет ровно $|\chi _{G}(-1)|$ различные ациклические ориентации, поэтому в этом смысле ациклическую ориентацию можно интерпретировать как раскраску с -1 цветом.

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

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

Подобно хроматическому многочлену, Тутте полином $T_{G}$ графика $G$, можно использовать для подсчета количества ациклических ориентаций $G$ как $T_{G}(2,0)$.Двойственность между ациклической и полностью циклической ориентацией планарных графов в этой форме распространяется и на непланарные графы: полином Тутте двойственного графа планарного графа получается путем замены аргументов $T_{G}$и количество полностью циклических ориентаций графа $G$ является $T_{G}(0,2)$, также полученный заменой аргументов формулы на число ациклических ориентаций.

Переворот края

Совокупности всех ациклических ориентаций данного графа можно придать структуру частичного куба , в котором две ациклические ориентации являются смежными всякий раз, когда они различаются направлением одного ребра. Это означает, что когда две разные ациклические ориентации одного и того же графа различаются направлениями k ребер, можно преобразовать одну из ориентаций в другую с помощью последовательности k изменений ориентации одного ребра, так что каждое из промежуточные состояния этой последовательности преобразований также ацикличны.

Особые случаи

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

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

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

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

Транзитивная ориентация графа — это ациклическая ориентация, равная его собственному транзитивному замыканию . Не каждый граф имеет транзитивную ориентацию; графики, которые это делают, являются графиками сравнимости . Полные графы — это частные случаи графов сравнимости, а транзитивные турниры — это частные случаи транзитивных ориентаций.