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

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

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]. Полные графы являются частным случаем графов сравнимости, а транзитивные турниры являются частным случаем транзитивных ориентаций.

Примечания

1. Nešetřil, Ossona de Mendez, 2012, с. 42.
2. Stanley, 1973, с. 171–178.
3. Welsh, 1997, с. 287–323.
4. Las Vergnas, 1980, с. 231–243.
5. Fukuda, Prodon, Sakuma, 2001, с. 9–16.
6. Dasgupta, 1999, с. 134–141.
7. de Fraysseix, Ossona de Mendez, Rosenstiehl, 1995, с. 157–179.
8. Ghouila-Houri, 1962, с. 1370–1371.

Литература

• Richard P. Stanley. Acyclic orientations of graphs // Discrete Mathematics. — 1973. — Т. 5, вып. 2. — doi:10.1016/0012-365X(73)90108-8.
• Jaroslav Nešetřil, Patrice Ossona de Mendez. Sparsity: Graphs, Structures, and Algorithms. — Heidelberg: Springer, 2012. — Т. 28. — С. 42. — (Algorithms and Combinatorics). — ISBN 978-3-642-27874-7. — doi:10.1007/978-3-642-27875-4.
• Dominic Welsh. Surveys in combinatorics, 1997 (London). — Cambridge: Cambridge Univ. Press, 1997. — Т. 241. — С. 287–323. — (London Math. Soc. Lecture Note Ser.). — doi:10.1017/CBO9780511662119.010.
• Michel Las Vergnas. Convexity in oriented matroids // Journal of Combinatorial Theory. — 1980. — Т. 29, вып. 2. — С. 231–243. — doi:10.1016/0095-8956(80)90082-9.
• Komei Fukuda, Alain Prodon, Tadashi Sakuma. Notes on acyclic orientations and the shelling lemma // Theoretical Computer Science. — 2001. — Т. 263, вып. 1-2. — С. 9–16. — doi:10.1016/S0304-3975(00)00226-7. (недоступная ссылка)
• Sanjoy Dasgupta. in Proc. 15th Conference on Uncertainty in Artificial Intelligence (UAI 1999), Stockholm, Sweden, July-August 1999. — 1999. — С. 134–141.
• Hubert de Fraysseix, Patrice Ossona de Mendez, Pierre Rosenstiehl. Bipolar orientations revisited // Discrete Applied Mathematics. — 1995. — Т. 56, вып. 2-3. — С. 157–179. — doi:10.1016/0166-218X(94)00085-R.
• Alain Ghouila-Houri. Caractérisation des graphes non orientés dont on peut orienter les arrêtes de manière à obtenir le graphe d'une relation d'ordre // Les Comptes rendus de l'Académie des sciences. — 1962. — Т. 254. — С. 1370–1371.