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

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

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

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

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

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

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

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

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

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

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

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

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

Переворачивание края

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

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

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

Каждая ориентация дерева ациклична . Направленный ацикличный граф, полученный в результате такой ориентации, называется полидеревом . [ 6]

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

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

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

Ссылки

  1. ^ Нешетржил, Ярослав ; Оссона де Мендес, Патрис (2012), "Теорема 3.13", Разреженность: графы, структуры и алгоритмы , Алгоритмы и комбинаторика, т. 28, Гейдельберг: Springer, стр. 42, doi :10.1007/978-3-642-27875-4, ISBN 978-3-642-27874-7, МР  2920058.
  2. ^ Стэнли, Ричард П. (1973), «Ациклические ориентации графов», Дискретная математика , 5 (2): 171–178, doi :10.1016/0012-365X(73)90108-8.
  3. ^ Welsh, Dominic (1997), "Approximate counting", Surveys in combinatorics, 1997 (Лондон) , London Math. Soc. Lecture Note Ser., т. 241, Кембридж: Cambridge Univ. Press, стр. 287–323, doi :10.1017/CBO9780511662119.010, ISBN 978-0-521-59840-8, МР  1477750.
  4. ^ Лас Верньяс, Мишель (1980), «Выпуклость в ориентированных матроидах», Журнал комбинаторной теории , Серия B, 29 (2): 231–243, doi :10.1016/0095-8956(80)90082-9, MR  0586435.
  5. ^ Фукуда, Комей ; Продон, Ален; Сакума, Тадаши (2001), «Заметки об ациклических ориентациях и лемме шеллинга», Теоретическая информатика , 263 (1–2): 9–16, doi : 10.1016/S0304-3975(00)00226-7 , MR  1846912
  6. ^ Дасгупта, Санджой (1999), «Изучение политдеревьев», Труды 15-й конференции по неопределенности в искусственном интеллекте (UAI 1999), Стокгольм, Швеция, июль-август 1999 г. (PDF) , стр. 134–141 .
  7. ^ de Fraysseix, Hubert; de Mendez, Patrice Ossona; Rosenstiehl, Pierre (1995), «Повторный взгляд на биполярные ориентации», Discrete Applied Mathematics , 56 (2–3): 157–179, doi : 10.1016/0166-218X(94)00085-R , MR  1318743.
  8. ^ Гуила-Ури, Ален (1962), «Caractérisation desgraphes not orientés dont on peut orienter les arrêtes de manière à obtenir le Grape d'une Relations d'ordre», Les Comptes rendus de l'Académie des Sciences , 254 : 1370 –1371, МР  0172275.
Взято с "https://en.wikipedia.org/w/index.php?title=Ациклическая_ориентация&oldid=1255022573"