В математике , в частности в теории графов , и информатике , ориентированный ациклический граф ( DAG ) — это ориентированный граф без направленных циклов . То есть он состоит из вершин и ребер (также называемых дугами ), причем каждое ребро направлено от одной вершины к другой, так что следование этим направлениям никогда не образует замкнутую петлю. Ориентированный граф является DAG тогда и только тогда, когда его можно топологически упорядочить , расположив вершины в линейном порядке, который согласуется со всеми направлениями ребер. DAG имеют многочисленные научные и вычислительные приложения, начиная от биологии (эволюция, генеалогические деревья, эпидемиология) и заканчивая информатикой (сети цитирования) и вычислениями (планирование).
Направленные ациклические графы также называются ациклическими направленными графами [1] или ациклическими орграфами [2] .
Граф образован вершинами и ребрами, соединяющими пары вершин, где вершины могут быть любым видом объекта, который соединен попарно ребрами. В случае ориентированного графа каждое ребро имеет ориентацию, от одной вершины к другой вершине. Путь в ориентированном графе — это последовательность ребер , обладающая тем свойством, что конечная вершина каждого ребра в последовательности совпадает с начальной вершиной следующего ребра в последовательности; путь образует цикл, если начальная вершина его первого ребра равна конечной вершине его последнего ребра. Направленный ациклический граф — это направленный граф, который не имеет циклов. [1] [2] [3]
Говорят, что вершина v направленного графа достижима из другой вершины u , когда существует путь, который начинается в u и заканчивается в v . В качестве особого случая каждая вершина считается достижимой из самой себя (путем с нулевыми ребрами). Если вершина может достичь себя по нетривиальному пути (пути с одним или несколькими ребрами), то этот путь является циклом, поэтому другой способ определения направленных ациклических графов состоит в том, что это графы, в которых ни одна вершина не может достичь себя по нетривиальному пути. [4]
Отношение достижимости DAG можно формализовать как частичный порядок ≤ на вершинах DAG. В этом частичном порядке две вершины u и v упорядочены как u ≤ v именно тогда, когда существует направленный путь от u до v в DAG; то есть, когда u может достичь v (или v достижимо из u ). [5] Однако разные DAG могут приводить к одному и тому же отношению достижимости и одному и тому же частичному порядку. [6] Например, 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. Напротив, для направленного графа, который не является ациклическим, может быть более одного минимального подграфа с тем же отношением достижимости. [7] Транзитивные редукции полезны для визуализации частичных порядков, которые они представляют, потому что они имеют меньше ребер, чем другие графы, представляющие те же порядки, и поэтому приводят к более простым рисункам графов . Диаграмма Хассе частичного порядка представляет собой рисунок транзитивной редукции, в котором ориентация каждого ребра показана путем помещения начальной вершины ребра в более низкое положение, чем его конечная вершина. [8]
Топологическое упорядочение ориентированного графа — это упорядочение его вершин в последовательность, такое, что для каждого ребра начальная вершина ребра встречается раньше в последовательности, чем конечная вершина ребра. Граф, имеющий топологическое упорядочение, не может иметь никаких циклов, потому что ребро в самую раннюю вершину цикла должно было бы быть ориентировано неправильно. Следовательно, каждый граф с топологическим упорядочением является ациклическим. Наоборот, каждый ориентированный ациклический граф имеет по крайней мере одно топологическое упорядочение. Следовательно, существование топологического упорядочения может быть использовано как эквивалентное определение ориентированного ациклического графа: это в точности графы, имеющие топологические упорядочения. [2] В общем случае это упорядочение не является уникальным; DAG имеет уникальное топологическое упорядочение тогда и только тогда, когда у него есть направленный путь, содержащий все вершины, и в этом случае упорядочение совпадает с порядком, в котором вершины появляются в пути. [9]
Семейство топологических упорядочений DAG совпадает с семейством линейных расширений отношения достижимости для DAG [10], поэтому любые два графа, представляющие один и тот же частичный порядок, имеют один и тот же набор топологических порядков.
Проблема перечисления графов для подсчета направленных ациклических графов была изучена Робинсоном (1973). [11] Количество DAG на n помеченных вершинах для n = 0, 1, 2, 3, … (без ограничений на порядок, в котором эти числа появляются в топологическом упорядочении DAG) равно
Эти числа можно вычислить с помощью рекуррентного соотношения
Эрик В. Вайсштейн предположил [12] , а Маккей и др. (2004) доказали, что те же числа учитывают матрицы (0,1) , для которых все собственные значения являются положительными действительными числами . Доказательство является биективным : матрица A является матрицей смежности DAG тогда и только тогда, когда A + I является матрицей (0,1) со всеми положительными собственными значениями, где I обозначает единичную матрицу . Поскольку DAG не может иметь самопетли , ее матрица смежности должна иметь нулевую диагональ, поэтому добавление I сохраняет свойство, что все коэффициенты матрицы равны 0 или 1. [13]
Мультидерево (также называемое строго однозначным графом или мангровым деревом ) — это DAG, в котором существует не более одного направленного пути между любыми двумя вершинами. Эквивалентно, это DAG, в котором подграф, достижимый из любой вершины, индуцирует ненаправленное дерево . [14]
Полидерево (также называемое направленным деревом ) — это мультидерево, образованное путем ориентирования рёбер ненаправленного дерева. [15]
Древовидное дерево — это полидерево, образованное путем ориентирования ребер неориентированного дерева от определенной вершины, называемой корнем древовидного дерева.
Топологическая сортировка — это алгоритмическая задача поиска топологического порядка заданного DAG. Она может быть решена за линейное время . [16] Алгоритм Кана для топологической сортировки строит порядок вершин напрямую. Он поддерживает список вершин, которые не имеют входящих ребер от других вершин, которые еще не были включены в частично построенный топологический порядок; изначально этот список состоит из вершин, не имеющих входящих ребер вообще. Затем он многократно добавляет одну вершину из этого списка в конец частично построенного топологического порядка и проверяет, следует ли добавлять ее соседей в список. Алгоритм завершается, когда все вершины будут обработаны таким образом. [17] В качестве альтернативы топологический порядок может быть построен путем обращения нумерации постпорядка обхода графа поиска в глубину . [16]
Также возможно проверить, является ли заданный направленный граф DAG за линейное время, либо попытавшись найти топологическое упорядочение, а затем проверив для каждого ребра, является ли полученное упорядочение допустимым [18], либо, в качестве альтернативы, для некоторых алгоритмов топологической сортировки, проверив, что алгоритм успешно упорядочивает все вершины, не встречая условия ошибки. [17]
Любой неориентированный граф можно превратить в DAG, выбрав полный порядок для его вершин и направив каждое ребро от более ранней конечной точки в порядке к более поздней конечной точке. Результирующая ориентация ребер называется ациклической ориентацией . Различные полные порядки могут приводить к одной и той же ациклической ориентации, поэтому граф с n вершинами может иметь меньше, чем n ! ациклических ориентаций. Количество ациклических ориентаций равно | χ (−1)| , где χ — хроматический многочлен данного графа. [19]
Любой ориентированный граф можно превратить в DAG, удалив набор вершин обратной связи или набор дуг обратной связи , набор вершин или ребер (соответственно), который касается всех циклов. Однако наименьший такой набор NP-трудно найти. [20] Произвольный ориентированный граф также можно преобразовать в DAG, назвав его конденсацией , стянув каждый из его сильно связанных компонентов в одну супервершину. [21] Когда граф уже ацикличен, его наименьшие наборы вершин обратной связи и наборы дуг обратной связи пусты , а его конденсация — это сам граф.
Транзитивное замыкание заданного DAG с n вершинами и m ребрами может быть построено за время O ( mn ) с использованием либо поиска в ширину , либо поиска в глубину для проверки достижимости из каждой вершины. [22] В качестве альтернативы, его можно решить за время O ( n ω ), где ω < 2,373 — показатель степени для алгоритмов умножения матриц ; это теоретическое улучшение по сравнению с ограничением O ( mn ) для плотных графов . [23]
Во всех этих алгоритмах транзитивного замыкания можно отличить пары вершин, которые достижимы по крайней мере одним путем длины два или более, от пар, которые могут быть соединены только путем длины один. Транзитивное сокращение состоит из ребер, которые образуют пути длины один, которые являются единственными путями, соединяющими их конечные точки. Следовательно, транзитивное сокращение может быть построено за те же асимптотические временные границы, что и транзитивное замыкание. [24]
Задача замыкания принимает в качестве входных данных вершинно-взвешенный направленный ациклический граф и ищет минимальный (или максимальный) вес замыкания – множества вершин C , такого, что ни одно ребро не покидает C . Задача может быть сформулирована для направленных графов без предположения об ацикличности, но без большей общности, поскольку в этом случае она эквивалентна той же задаче о конденсации графа. Она может быть решена за полиномиальное время с использованием сведения к задаче максимального потока . [25]
Некоторые алгоритмы становятся проще при использовании на DAG вместо общих графов, основанных на принципе топологического упорядочения. Например, можно найти кратчайшие пути и длиннейшие пути из заданной начальной вершины в DAG за линейное время, обрабатывая вершины в топологическом порядке и вычисляя длину пути для каждой вершины, чтобы она была минимальной или максимальной длиной, полученной через любое из ее входящих ребер. [26] Напротив, для произвольных графов кратчайший путь может потребовать более медленных алгоритмов, таких как алгоритм Дейкстры или алгоритм Беллмана–Форда , [27] а длиннейшие пути в произвольных графах являются NP-трудными для поиска. [28]
Представления направленных ациклических графов частичных порядков имеют множество приложений в планировании для систем задач с ограничениями упорядочения. [29] Важный класс задач этого типа касается наборов объектов, которые необходимо обновить, таких как ячейки электронной таблицы после изменения одной из ячеек или объектные файлы части компьютерного программного обеспечения после изменения ее исходного кода . В этом контексте граф зависимостей — это граф, имеющий вершину для каждого объекта, который необходимо обновить, и ребро, соединяющее два объекта, когда один из них необходимо обновить раньше другого. Цикл в этом графе называется циклической зависимостью и, как правило, не допускается, поскольку не было бы способа последовательно планировать задачи, включенные в цикл. Графы зависимостей без циклических зависимостей образуют DAG. [30]
Например, когда изменяется одна ячейка электронной таблицы , необходимо пересчитать значения других ячеек, которые напрямую или косвенно зависят от измененной ячейки. Для этой проблемы задачи, которые необходимо запланировать, — это пересчет значений отдельных ячеек электронной таблицы. Зависимости возникают, когда выражение в одной ячейке использует значение из другой ячейки. В таком случае используемое значение должно быть пересчитано раньше, чем выражение, которое его использует. Топологическое упорядочение графа зависимостей и использование этого топологического порядка для планирования обновлений ячеек позволяет обновлять всю электронную таблицу с помощью только одной оценки на ячейку. [31] Аналогичные проблемы упорядочения задач возникают в make-файлах для компиляции программ [31] и планировании инструкций для оптимизации низкоуровневых компьютерных программ. [32]
Несколько иная формулировка ограничений планирования на основе DAG используется в методе оценки и обзора программ (PERT), методе управления крупными человеческими проектами, который был одним из первых применений DAG. В этом методе вершины DAG представляют собой вехи проекта, а не конкретные задачи, которые необходимо выполнить. Вместо этого задача или действие представлены ребром DAG, соединяющим две вехи, которые отмечают начало и завершение задачи. Каждое такое ребро помечено оценкой количества времени, которое потребуется команде работников для выполнения задачи. Самый длинный путь в этом DAG представляет собой критический путь проекта, тот, который контролирует общее время проекта. Отдельные вехи могут быть запланированы в соответствии с длиной самых длинных путей, заканчивающихся в их вершинах. [33]
Для представления сети обрабатывающих элементов может использоваться направленный ациклический граф. В этом представлении данные поступают в обрабатывающий элемент через его входящие ребра и покидают элемент через его исходящие ребра.
Например, в проектировании электронных схем статические комбинационные логические блоки могут быть представлены как ациклическая система логических вентилей , которая вычисляет функцию входа, где вход и выход функции представлены как отдельные биты . В общем случае выход этих блоков не может быть использован в качестве входа, если он не захвачен регистром или элементом состояния, который поддерживает его ациклические свойства. [34] Схемы электронных схем на бумаге или в базе данных представляют собой форму направленных ациклических графов, использующих экземпляры или компоненты для формирования направленной ссылки на компонент более низкого уровня. Сами электронные схемы не обязательно являются ациклическими или направленными.
Языки программирования потоков данных описывают системы операций над потоками данных и связи между выходами некоторых операций и входами других. Эти языки могут быть удобны для описания повторяющихся задач обработки данных, в которых один и тот же ациклически связанный набор операций применяется ко многим элементам данных. Они могут быть выполнены как параллельный алгоритм , в котором каждая операция выполняется параллельным процессом, как только другой набор входов становится доступным для него. [35]
В компиляторах прямой код (то есть последовательности операторов без циклов или условных ветвей) может быть представлен DAG, описывающим входы и выходы каждой арифметической операции, выполняемой в коде. Это представление позволяет компилятору эффективно выполнять устранение общих подвыражений . [36] На более высоком уровне организации кода принцип ациклических зависимостей гласит, что зависимости между модулями или компонентами большой программной системы должны образовывать направленный ациклический граф. [37]
Еще одним примером являются нейронные сети прямого распространения .
Графы, в которых вершины представляют события, происходящие в определенное время, и где ребра всегда указывают от ранней вершины времени к поздней вершине времени ребра, обязательно являются направленными и ациклическими. Отсутствие цикла следует из того, что время, связанное с вершиной, всегда увеличивается по мере того, как вы следуете по любому пути в графе, поэтому вы никогда не сможете вернуться к вершине на пути. Это отражает нашу естественную интуицию, что причинность означает, что события могут влиять только на будущее, они никогда не влияют на прошлое, и, таким образом, у нас нет причинных циклов . Примером такого типа направленного ациклического графа являются те, которые встречаются в подходе причинных множеств к квантовой гравитации, хотя в этом случае рассматриваемые графы являются транзитивно полными. В примере истории версий ниже каждая версия программного обеспечения связана с уникальным временем, как правило, временем, когда версия была сохранена, зафиксирована или выпущена. В примерах графа цитирования ниже документы публикуются одновременно и могут ссылаться только на более старые документы.
Иногда события не связаны с определенным физическим временем. При условии, что пары событий имеют чисто причинно-следственную связь, то есть ребра представляют причинно-следственные связи между событиями, у нас будет направленный ациклический граф. [38] Например, байесовская сеть представляет собой систему вероятностных событий как вершин в направленном ациклическом графе, в котором вероятность события может быть вычислена из вероятностей его предшественников в DAG. [39] В этом контексте моральный граф DAG — это ненаправленный граф, созданный путем добавления (ненаправленного) ребра между всеми родителями одной и той же вершины (иногда называемого бракосочетанием ), а затем замены всех направленных ребер ненаправленными ребрами. [40] Другой тип графа с похожей причинно-следственной структурой — это диаграмма влияния , вершины которой представляют либо решения, которые необходимо принять, либо неизвестную информацию, а ребра — причинно-следственные влияния от одной вершины к другой. [41] В эпидемиологии , например, эти диаграммы часто используются для оценки ожидаемой ценности различных вариантов вмешательства. [42] [43]
Обратное также верно. То есть в любом приложении, представленном направленным ациклическим графом, есть причинная структура, либо явный порядок или время в примере, либо порядок, который может быть выведен из структуры графа. Это следует из того, что все направленные ациклические графы имеют топологическое упорядочение, т. е. существует по крайней мере один способ расположить вершины в порядке, таком, что все ребра указывают в одном направлении вдоль этого порядка.
Генеалогические деревья можно рассматривать как направленные ациклические графы с вершиной для каждого члена семьи и ребром для каждого отношения родитель-ребенок. [44] Несмотря на название, эти графы не обязательно являются деревьями из-за возможности браков между родственниками (так что у ребенка есть общий предок как со стороны матери, так и со стороны отца), что приводит к краху родословной . [45] Графы матрилинейного происхождения (отношения мать-дочь) и патрилинейного происхождения (отношения отец-сын) являются деревьями внутри этого графа. Поскольку никто не может стать своим собственным предком, генеалогические деревья являются ациклическими. [46]
История версий распределенной системы контроля версий , такой как Git , обычно имеет структуру направленного ациклического графа, в котором есть вершина для каждой ревизии и ребро, соединяющее пары ревизий, которые были напрямую получены друг из друга. Это не деревья в целом из-за слияний. [47]
Во многих рандомизированных алгоритмах в вычислительной геометрии алгоритм поддерживает историю DAG , представляющую историю версий геометрической структуры в ходе последовательности изменений структуры. Например, в рандомизированном инкрементном алгоритме для триангуляции Делоне триангуляция изменяется путем замены одного треугольника тремя меньшими треугольниками при добавлении каждой точки и операциями «переворота», которые заменяют пары треугольников другой парой треугольников. История DAG для этого алгоритма имеет вершину для каждого треугольника, построенного как часть алгоритма, и ребра от каждого треугольника к двум или трем другим треугольникам, которые его заменяют. Эта структура позволяет эффективно отвечать на запросы местоположения точек : чтобы найти местоположение точки запроса q в триангуляции Делоне, следуйте по пути в истории DAG, на каждом шаге перемещаясь к заменяющему треугольнику, который содержит q . Последний треугольник, достигнутый на этом пути, должен быть треугольником Делоне, который содержит q . [48]
В графе цитирования вершины представляют собой документы с одной датой публикации. Ребра представляют собой ссылки из библиографии одного документа на другие, обязательно более ранние документы. Классический пример — это ссылки между академическими работами, как указано в статье 1965 года «Сети научных работ» [49] Дерека Дж. де Соллы Прайса , который затем создал первую модель сети цитирования, модель Прайса . [50] В этом случае количество цитирований статьи — это просто входящая степень соответствующей вершины сети цитирования. Это важная мера в анализе цитирования . Судебные решения представляют собой еще один пример, поскольку судьи подтверждают свои выводы в одном деле, ссылаясь на другие более ранние решения, принятые в предыдущих делах. Последний пример — патенты, которые должны ссылаться на более ранний уровень техники , более ранние патенты, которые имеют отношение к текущему патентному иску. Принимая во внимание особые свойства направленных ациклических графов, можно анализировать сети цитирования с помощью методов, недоступных при анализе общих графов, рассматриваемых во многих исследованиях с использованием сетевого анализа . Например, транзитивная редукция дает новое представление о распределениях цитирования, обнаруженных в различных приложениях, подчеркивая четкие различия в механизмах создания сетей цитирования в различных контекстах. [51] Другой метод — анализ основного пути , который отслеживает связи цитирования и предлагает наиболее значимые цепочки цитирования в заданном графе цитирования .
Модель Прайса слишком проста, чтобы быть реалистичной моделью сети цитирования , но она достаточно проста, чтобы допускать аналитические решения для некоторых ее свойств. Многие из них можно найти, используя результаты, полученные из неориентированной версии модели Прайса , модели Барабаши–Альберта . Однако, поскольку модель Прайса дает направленный ациклический граф, она является полезной моделью при поиске аналитических вычислений свойств, уникальных для направленных ациклических графов. Например, длина самого длинного пути от n-го узла, добавленного в сеть, до первого узла в сети масштабируется как [52] .
Направленные ациклические графы также могут использоваться в качестве компактного представления набора последовательностей. В этом типе приложения можно найти DAG, в котором пути формируют заданные последовательности. Когда многие из последовательностей разделяют одни и те же подпоследовательности, эти общие подпоследовательности могут быть представлены общей частью DAG, что позволяет представлению использовать меньше места, чем потребовалось бы для перечисления всех последовательностей по отдельности. Например, направленный ациклический граф слов — это структура данных в информатике, образованная направленным ациклическим графом с одним источником и ребрами, помеченными буквами или символами; пути от источника к стокам в этом графе представляют собой набор строк , таких как английские слова. [53] Любой набор последовательностей можно представить как пути в дереве, сформировав вершину дерева для каждого префикса последовательности и сделав родительскую вершину одной из этих вершин представляющей последовательность с одним элементом меньше; дерево, сформированное таким образом для набора строк, называется trie . Направленный ациклический граф слов экономит место по сравнению с префиксным деревом, позволяя путям расходиться и воссоединяться, так что набор слов с одинаковыми возможными суффиксами может быть представлен одной вершиной дерева. [54]
Та же идея использования DAG для представления семейства путей встречается в диаграмме бинарных решений , [55] [56] структуре данных на основе DAG для представления бинарных функций. В диаграмме бинарных решений каждая вершина, не являющаяся стоком, помечена именем бинарной переменной, а каждый сток и каждое ребро помечены 0 или 1. Значение функции для любого назначения истинности переменным — это значение в стоке, найденное путем следования по пути, начинающемуся с единственной исходной вершины, который в каждой вершине, не являющейся стоком, следует за исходящим ребром, помеченным значением переменной этой вершины. Так же, как направленные ациклические графы слов можно рассматривать как сжатую форму попыток, диаграммы бинарных решений можно рассматривать как сжатые формы деревьев решений , которые экономят пространство, позволяя путям воссоединяться, когда они согласуются с результатами всех оставшихся решений. [57]
