Меню Главная Случайная статья Настройки Ациклическая ориентация Материал из https://ru.wikipedia.org Ациклическая ориентация неориентированного графа — это назначение направлений каждому ребру (ориентация), при которой не образуется какого-либо ориентированного цикла, а потому такая ориентация превращает граф в направленный ациклический граф. Любой граф имеет ациклическую ориентацию. Хроматическое число любого графа равно минимальной длине максимальному пути[англ.] среди всех ациклических ориентаций. Ациклические ориентации связаны с раскраской посредством хроматического многочлена, который подсчитывает как ациклические ориентации, так и раскраски. Для планарных графов ациклические ориентации являются двойственными графами вполне циклических ориентаций[англ.], и наоборот. Множеству ациклических ориентаций заданного графа может быть придана структура частичного куба, в котором две циклические ориентации смежны, если они отличаются направлением только одного ребра. Ориентации деревьев всегда ацикличны и являются полидеревьями[англ.]. Ациклические ориентации полных графов называются транзитивными турнирами. Биполярные ориентации являются частными случаями ациклических ориентаций, в которых имеется в точности один источник и один сток. Любой транзитивный турнир является биполярным. Содержание 1 Построение 2 Связь с раскраской 3 Двойственность 4 Перевёртывание ребра 5 Частные случаи 6 Примечания 7 Литература Построение Любой граф имеет ациклическую ориентацию. Одним из способов создания ациклических ориентаций является упорядочение вершин с последующим ориентированием каждого ребра от более ранней вершины в списке к более поздней. Последовательность вершин тогда становится топологическим упорядочиванием получившегося ориентированного ациклического графа (ОАГ), и любая топологическая сортировка этого ОАГ образует одну и ту же ориентацию. Поскольку любой ОАГ имеет топологическую сортировку, любая ациклическая ориентация может быть получена указанным образом. Однако различные последовательности вершин могут привести к одинаковым ациклическим ориентациям, если получаемый ОАГ имеет несколько топологических сортировок. Например, у цикла с четырьмя вершинами (показан на рисунке) существует 24 различных последовательности, но только 14 возможных ациклических ориентаций. Связь с раскраской Теорема Галлаи – Хассе – Роя – Витавера утверждает, что граф имеет ациклическую ориентацию, в которой максимальный путь[англ.] имеет не более k вершин, тогда и только тогда, когда граф может быть раскрашен не более чем в Число ациклических ориентаций можно посчитать, используя хроматический многочлен ${\displaystyle \chi _{G}}$, значение которого для положительного целого числа Двойственность Для планарных графов ациклические ориентации являются двойственными вполне циклическим ориентациям[англ.], ориентациям, в которых каждое ребро принадлежит ориентированному циклу — если ${\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]. Из этого следует, что если две различные ациклические ориентации одного и того же графа различаются направлением Частные случаи Любая ориентация дерева ациклична. Ориентированный ациклический граф, полученный такой ориентацией называется полидеревом[англ.][6]. Ациклическая ориентация полного графа называется транзитивным турниром и она эквивалентна полному упорядочению вершин графа. В такой ориентации существует, в частности, в точности один источник и один сток. Ациклическая ориентация произвольного графа, имеющая единственный источник и единственный сток, называется биполярной ориентацией [7]. Транзитивная ориентация графа является ациклической ориентацией, которая является его транзитивным замыканием. Не любой граф обладает транзитивной ориентацией. Графы, имеющие транзитивную ориентацию, являются графами сравнимости[8]. Полные графы являются частным случаем графов сравнимости, а транзитивные турниры являются частным случаем транзитивных ориентаций. Примечания Neetil, Ossona de Mendez, 2012, с. 42. Stanley, 1973, с. 171–178. Welsh, 1997, с. 287–323. Las Vergnas, 1980, с. 231–243. Fukuda, Prodon, Sakuma, 2001, с. 9–16. Dasgupta, 1999, с. 134–141. de Fraysseix, Ossona de Mendez, Rosenstiehl, 1995, с. 157–179. 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 Neetil, 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. 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. 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. Caractrisation des graphes non orients dont on peut orienter les arrtes de manire obtenir le graphe d'une relation d'ordre // Les Comptes rendus de l'Acadmie des sciences. — 1962. — Т. 254. — С. 1370–1371.