Ориентированный ациклический граф

Пример ориентированного ациклического графа

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

Направленные ациклические графы иногда называют ациклическими ориентированными графами. или ациклические орграфы .

Определения

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

Говорят, что вершина v ориентированного графа достижима из другой вершины u , если существует путь, который начинается в u и заканчивается в v . В частном случае каждая вершина считается достижимой из самой себя (путем с нулевыми ребрами). Если вершина может достичь себя по нетривиальному пути (путь с одним или несколькими ребрами), то этот путь является циклом, поэтому другой способ определить направленные ациклические графы состоит в том, что это графы, в которых ни одна вершина не может достичь себя через нетривиальный путь.

Математические свойства

Отношение достижимости, транзитивное замыкание и транзитивная редукция.

ДЕНЬ

Его транзитивная редукция

Отношение достижимости DAG можно формализовать как частичный порядок ≤ на вершинах DAG. В этом частичном порядке две вершины u и v упорядочиваются как u ≤ v точно тогда, когда существует направленный путь от u до v в DAG; то есть, когда u может достичь v (или v достижимо из u ). Однако разные DAG могут привести к одному и тому же отношению достижимости и одному и тому же частичному порядку. Например, DAG с двумя ребрами u → v и v → w имеет то же отношение достижимости, что и DAG с тремя ребрами u → v , v → w и u → w . Оба этих DAG создают один и тот же частичный порядок, в котором вершины упорядочены как u ≤ v ≤ w .

Транзитивное замыкание DAG — это граф с наибольшим количеством ребер, который имеет то же отношение достижимости, что и DAG. Он имеет ребро u → v для каждой пары вершин ( u , v ) в отношении достижимости ≤ DAG, и поэтому его можно рассматривать как прямой перевод отношения достижимости ≤ в термины теории графов. Тот же метод перевода частичных порядков в DAG работает в более общем плане: для каждого конечного частично упорядоченного набора ( S , ≤) граф, который имеет вершину для каждого элемента S и ребро для каждой пары элементов из ≤, автоматически является транзитивным. замкнутый DAG и имеет ( S , ≤) в качестве отношения достижимости. Таким образом, любое конечное частично упорядоченное множество можно представить как DAG.

Диаграмма Хассе, представляющая частичный порядок включения множества (⊆) среди подмножеств трехэлементного множества.

Транзитивная редукция DAG — это граф с наименьшим количеством ребер, имеющий то же отношение достижимости, что и DAG. Он имеет ребро u → v для каждой пары вершин ( u , v ) в отношении покрытия отношения достижимости ≤ DAG. Это подграф DAG, образованный путем отбрасывания ребер u → v , для которых DAG также содержит более длинный направленный путь от u до v .Как и транзитивное замыкание, транзитивная редукция однозначно определена для групп DAG. Напротив, для ориентированного графа, который не является ациклическим, может существовать более одного минимального подграфа с одним и тем же отношением достижимости. Транзитивные сокращения полезны при визуализации частичных порядков, которые они представляют, поскольку они имеют меньше ребер, чем другие графы, представляющие те же порядки, и, следовательно, приводят к более простым рисункам графов . Диаграмма Хассе частичного порядка — это рисунок транзитивной редукции, на котором ориентация каждого ребра показана путем размещения начальной вершины ребра в более низком положении, чем его конечная вершина.

Топологическое упорядочение

Топологическое упорядочение ориентированного ациклического графа: каждое ребро идет от более раннего (вверху слева) к более позднему по порядку (внизу справа). Ориентированный граф является ациклическим тогда и только тогда, когда он обладает топологическим упорядочением.

Добавление красных ребер к синему ациклическому графу дает еще один DAG — транзитивное замыкание синего графа. синего ребра u → v v u достижимо Для каждого красного или из u : существует синий путь, начинающийся в и заканчивающийся в v .

Топологическое упорядочение ориентированного графа — это упорядочение его вершин в последовательность, при котором для каждого ребра начальная вершина ребра встречается раньше в последовательности, чем конечная вершина ребра. Граф с топологическим упорядочением не может иметь циклов, поскольку ребро, ведущее в самую раннюю вершину цикла, должно быть ориентировано неправильно. Следовательно, каждый граф с топологическим упорядочением ацикличен. И наоборот, каждый направленный ациклический граф имеет хотя бы одно топологическое упорядочение. Таким образом, существование топологического упорядочения можно использовать как эквивалентное определение ориентированных ациклических графов: это именно те графы, которые имеют топологическое упорядочение. В общем, этот порядок не уникален; DAG имеет уникальный топологический порядок тогда и только тогда, когда он имеет направленный путь, содержащий все вершины, и в этом случае порядок такой же, как порядок, в котором вершины появляются на пути.

Семейство топологических порядков DAG совпадает с семейством линейных расширений отношения достижимости для DAG: поэтому любые два графа, представляющие один и тот же частичный порядок, имеют одинаковый набор топологических порядков.

Комбинаторное перечисление

Проблема перечисления графов подсчета ориентированных ациклических графов изучалась Робинсоном (1973) . Количество DAG на n помеченных вершинах для n = 0, 1, 2, 3,… (без ограничений на порядок, в котором эти числа появляются в топологическом порядке DAG) равно

1, 1, 3, 25, 543, 29281, 3781503, … (последовательность A003024 в OEIS ).

Эти числа можно вычислить с помощью рекуррентного соотношения

$a_{n}=\sum _{k=1}^{n}(-1)^{k-1}{n \choose k}2^{k(n-k)}a_{n-k}.$

Эрик В. Вайсстайн предположил: и Маккей и др. (2004) доказали, что одни и те же числа учитывают матрицы (0,1), которых все собственные значения являются положительными действительными числами . Доказательство является биективным : матрица A является матрицей смежности DAG тогда и только тогда, когда A + I является (0,1)-матрицей со всеми положительными собственными значениями, где I обозначает единичную матрицу . Поскольку DAG не может иметь циклов , его матрица смежности должна иметь нулевую диагональ, поэтому добавление I сохраняет свойство, согласно которому все коэффициенты матрицы равны 0 или 1.

Родственные семейства графов

Мультидерево . , DAG, в котором подграф, достижимый из любой вершины, порождает неориентированное дерево (например, выделено красным)

Полидерево , DAG , сформированное путем ориентации ребер неориентированного дерева.

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

Полидерево ) — это мультидерево , (также называемое ориентированным деревом сформированное путем ориентации ребер неориентированного дерева.

Древовидность ориентации — это полидерево, образованное путем ребер неориентированного дерева от определенной вершины, называемой корнем древовидности.

Вычислительные проблемы

Топологическая сортировка и распознавание

Основная статья: Топологическая сортировка

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

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

Построение из циклических графов

Любой неориентированный граф можно превратить в DAG, выбрав общий порядок его вершин и направив каждое ребро от более ранней конечной точки порядка к более поздней конечной точке. Результирующая ориентация ребер называется ациклической ориентацией . Разные общие порядки могут привести к одной и той же ациклической ориентации, поэтому граф с n вершинами может иметь меньше n ! ациклические ориентации. Число ациклических ориентаций равно | х (−1)| , где χ — хроматический полином данного графа.

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

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

Транзитивное замыкание и транзитивная редукция

Транзитивное замыкание данного DAG с n вершинами и m ребрами может быть построено за время O ( mn ), используя либо поиск в ширину , либо поиск в глубину для проверки достижимости из каждой вершины. Альтернативно, ее можно решить за время O ( n ^ой ) где ω < 2,373 — показатель степени для алгоритмов умножения матриц ; это теоретическое улучшение по сравнению с ограничением O ( mn ) для плотных графов .

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

Проблема закрытия

Основная статья: Проблема закрытия

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

Алгоритмы пути

Некоторые алгоритмы становятся проще при использовании в DAG вместо общих графов, основанных на принципе топологического упорядочения. Например, можно найти кратчайшие и самые длинные пути из заданной начальной вершины в DAG за линейное время, обрабатывая вершины в топологическом порядке и вычисляя длину пути для каждой вершины как минимальную или максимальную длину, полученную с помощью любого его входящих ребер. Напротив, для произвольных графов кратчайший путь может потребовать более медленных алгоритмов, таких как алгоритм Дейкстры или алгоритм Беллмана-Форда . а самые длинные пути в произвольных графах NP-трудно . найти

Приложения

Планирование

Представления частичного упорядочения в виде направленного ациклического графа имеют множество применений при планировании систем задач с ограничениями порядка. Важный класс проблем этого типа касается наборов объектов, которые необходимо обновить, например ячеек электронной таблицы после изменения одной из ячеек или объектных файлов части компьютерного программного обеспечения после того, как ее исходный код был изменен. измененный.В этом контексте граф зависимостей — это граф, который имеет вершину для каждого обновляемого объекта и ребро, соединяющее два объекта, когда один из них необходимо обновить раньше, чем другой. Цикл на этом графике называется циклической зависимостью и, как правило, не допускается, поскольку не будет возможности последовательно планировать задачи, участвующие в цикле.Графы зависимостей без циклических зависимостей образуют группы DAG.

Например, при изменении одной ячейки электронной таблицы необходимо пересчитать значения других ячеек, которые прямо или косвенно зависят от измененной ячейки. Для этой задачи планируются задачи по пересчету значений отдельных ячеек электронной таблицы. Зависимости возникают, когда выражение в одной ячейке использует значение из другой ячейки. В таком случае используемое значение должно быть пересчитано раньше, чем выражение, в котором оно используется. Топологическое упорядочение графа зависимостей и использование этого топологического порядка для планирования обновлений ячеек позволяет обновлять всю электронную таблицу с помощью только одной оценки для каждой ячейки. Аналогичные проблемы с упорядочиванием задач возникают в make-файлах для компиляции программ. и планирование инструкций для низкоуровневой оптимизации компьютерных программ.

Диаграмма PERT для проекта с пятью этапами (помеченными 10–50) и шестью задачами (помеченными A–F). Есть два критических пути: ADF и BC.

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

Сети обработки данных

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

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

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

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

нейронные сети с прямой связью Еще одним примером являются .

Причинные структуры

Основная статья: Байесовская сеть

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

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

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

Генеалогия и история версий

Генеалогическое древо династии Птолемеев , с многочисленными браками между близкими родственниками, приводящими к распаду родословной .

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

История версий распределенной системы контроля версий , такой как Git , обычно имеет структуру направленного ациклического графа, в котором есть вершина для каждой ревизии и ребро, соединяющее пары ревизий, которые были непосредственно получены друг от друга. Это не деревья вообще из-за слияний.

Во многих рандомизированных алгоритмах вычислительной геометрии алгоритм поддерживает историю DAG, представляющую историю версий геометрической структуры в ходе последовательности изменений в структуре. Например, в рандомизированном инкрементном алгоритме триангуляции Делоне триангуляция изменяется за счет замены одного треугольника тремя меньшими треугольниками при добавлении каждой точки, а также за счет операций «переворота», которые заменяют пары треугольников другой парой треугольников. Исторический DAG для этого алгоритма имеет вершину для каждого треугольника, построенного как часть алгоритма, и ребра от каждого треугольника к двум или трем другим треугольникам, которые его заменяют. Эта структура позволяет эффективно отвечать на запросы о местоположении точек : чтобы найти местоположение точки запроса q в триангуляции Делоне, следуйте по пути в истории DAG, на каждом шаге переходя к треугольнику замены, который содержит q . Последний треугольник, достигнутый на этом пути, должен быть треугольником Делоне, содержащим q .

Графики цитирования

В графе цитирования вершинами являются документы с одной датой публикации. Края представляют собой цитаты из библиографии одного документа на другие обязательно более ранние документы. Классический пример — цитирование научных статей, как указано в статье 1965 года «Сети научных статей». Дерек Дж. де Солла Прайс , который разработал первую модель сети цитирования, модель Прайса . В этом случае количество цитирований статьи — это просто степень входа соответствующей вершины сети цитирования. Это важная мера при анализе цитирования . Решения судов служат еще одним примером, поскольку судьи подкрепляют свои выводы по одному делу, ссылаясь на другие ранее принятые решения по предыдущим делам. Последним примером являются патенты, которые должны относиться к более раннему уровню техники , более ранние патенты, которые имеют отношение к текущей патентной заявке. Принимая во внимание особые свойства направленных ациклических графов, можно анализировать сети цитирования методами, недоступными при анализе общих графов, рассматриваемых во многих исследованиях с использованием сетевого анализа . Например, транзитивная редукция дает новое представление о распределении цитирования в разных приложениях, подчеркивая явные различия в механизмах создания сетей цитирования в разных контекстах. Другой метод – это анализ основных путей , который отслеживает связи цитирования и предлагает наиболее значимые цепочки цитирования в данном графе цитирования .

Модель Прайса слишком проста, чтобы быть реалистичной моделью сети цитирования , но она достаточно проста, чтобы обеспечить аналитические решения для некоторых ее свойств. Многие из них можно найти, используя результаты, полученные на основе неориентированной версии модели Прайса , модели Барабаши-Альберта . Однако, поскольку модель Прайса дает ориентированный ациклический граф, она является полезной моделью при поиске аналитических расчетов свойств, уникальных для ориентированных ациклических графов. Например,длина самого длинного пути от n-го узла, добавленного в сеть, до первого узла в сети масштабируется как $\ln(n)$.

Сжатие данных

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

Та же идея использования DAG для представления семейства путей встречается в диаграмме двоичного решения . структура данных на основе DAG для представления двоичных функций. В диаграмме двоичного решения каждая вершина, не являющаяся стоком, помечена именем двоичной переменной, а каждый сток и каждое ребро помечены цифрой 0 или 1. Значением функции для любого истинного присвоения переменным является значение в сток, найденный путем следования по пути, начиная с единственной исходной вершины, который в каждой вершине, не являющейся стоком, следует за исходящим ребром, помеченным значением переменной этой вершины. Точно так же, как ориентированные ациклические графы слов можно рассматривать как сжатую форму попыток, бинарные диаграммы решений можно рассматривать как сжатые формы деревьев решений, которые экономят пространство, позволяя путям воссоединиться, когда они согласуются с результатами всех оставшихся решений.

Внешние ссылки

• Вайсштейн, Эрик В. , «Ациклический орграф» , MathWorld
• DAGitty – онлайн-инструмент для создания групп DAG.