В математике , в частности теории графов и информатике , в ориентированный ациклический граф ( DAG или даг / д æ ɡ / ( слушать ) ) представляет собой ориентированный граф без каких - либо направленных циклов . То есть он состоит из вершин и ребер (также называемых дугами ), причем каждое ребро направлено от одной вершины к другой, так что следование этим направлениям никогда не образует замкнутый цикл. Ориентированный граф является DAG тогда и только тогда, когда он может быть топологически упорядочен, расположив вершины в линейном порядке, который согласуется со всеми направлениями ребер. У DAG есть множество научных и вычислительных приложений, от биологии (эволюция, родословные, эпидемиология) до социологии (сети цитирования) и вычислений (планирование).
Определения
Граф образован вершинами и ребрами , соединяющих пары вершин, где вершины могут быть любой вид объекта , который соединен попарно ребрами. В случае ориентированного графа каждое ребро имеет ориентацию от одной вершины к другой вершине. Путь в ориентированном графе представляет собой последовательность ребер , обладающего свойство , что окончание вершины каждого ребра в последовательности является тем же самым в качестве исходного вершины следующего ребра в последовательности; путь образует цикл, если начальная вершина его первого ребра равна конечной вершине его последнего ребра. Ориентированный ациклический граф - это ориентированный граф без циклов. [1] [2] [3]
Вершина v ориентированного графа называется достижимой из другой вершины u, если существует путь, который начинается в u и заканчивается в v . Как частный случай, каждая вершина считается достижимой из самой себя (путем с нулевыми ребрами). Если вершина может достичь себя через нетривиальный путь (путь с одним или несколькими ребрами), то этот путь является циклом, поэтому другой способ определения ориентированных ациклических графов состоит в том, что они являются графами, в которых ни одна вершина не может достичь себя через нетривиальный путь. [4]
Математические свойства
Достижимость, транзитивное замыкание и транзитивная редукция
Отношения достижимости в любом ориентированном ациклическом графе можно формализовать как частичный порядок ≤ на вершинах DAG. В этом частичном порядке две вершины u и v упорядочены как u ≤ v именно тогда, когда существует направленный путь от u к v в DAG; то есть, когда v достижимо из u . [5] Однако разные группы DAG могут привести к одному и тому же отношению достижимости и одному и тому же частичному порядку. [6] Например, DAG с двумя ребрами a → b и b → c имеет то же отношение достижимости, что и граф с тремя ребрами a → b , b → c и a → c . Оба этих DAGS производят один и тот же частичный порядок, в котором вершины упорядочены как a ≤ b ≤ c .
Если G является DAG, его транзитивное замыкание - это граф с наибольшим количеством ребер, который представляет одно и то же отношение достижимости. У него есть ребро u → v, когда u может достичь v . То есть у него есть ребро для каждой связанной пары u ≤ v различных элементов в отношении достижимости группы G , и поэтому его можно рассматривать как прямой перевод отношения достижимости ≤ в термины теории графов. Тот же метод преобразования частичных порядков в DAG работает в более общем плане: для каждого конечного частично упорядоченного набора ( S , ≤) граф, имеющий вершину для каждого члена S и ребро для каждой пары элементов, связанных соотношением u ≤ v, является автоматически транзитивно замкнутый DAG и имеет ( S , ≤) в качестве отношения достижимости. Таким образом, каждый конечный частично упорядоченный набор может быть представлен как отношение достижимости DAG.
Транзитивен сокращение из DAG G называется граф с наименьшим количеством ребер , которые имеют то же отношение как достижимости G . Это подграф G , образованный отбрасыванием ребер u → v, для которых G также содержит более длинный путь, соединяющий те же две вершины. Подобно транзитивному замыканию, транзитивное сокращение однозначно определяется для групп DAG. Напротив, для ориентированного графа, который не является ациклическим, может быть более одного минимального подграфа с одним и тем же отношением достижимости. [7]
Если ДАГ G имеет отношение достижимости , описываемое частичный порядок ≤ , то переходное уменьшение G является подграфом G , который имеет край ¯u → V для каждой пары в покрывающем отношении от ≤ . Транзитивные редукции полезны для визуализации частичных порядков, которые они представляют, потому что они имеют меньше ребер, чем другие графы, представляющие те же порядки, и, следовательно, приводят к более простым чертежам графов . Диаграмма Хассе частичного порядка является нанесение переходного сокращения , в котором ориентация каждого ребра показано, помещая начальную вершину кромки в нижнем положении , чем его окончание вершины. [8]
Топологический порядок
Топологическое упорядочение ориентированного графа является упорядочением его вершин в последовательность, таким образом, что для каждого ребра начала вершины края происходит раньше в последовательности , чем заканчивающаяся вершина ребра. Граф с топологическим упорядочением не может иметь никаких циклов, потому что ребро в самую раннюю вершину цикла должно быть неправильно ориентировано. Следовательно, любой граф с топологическим упорядочением ацикличен. И наоборот, каждый ориентированный ациклический граф имеет хотя бы один топологический порядок. Таким образом, существование топологического упорядочения можно использовать как эквивалентное определение ориентированных ациклических графов: это именно те графы, которые имеют топологический порядок. [2] В общем, этот порядок не уникален; DAG имеет уникальный топологический порядок тогда и только тогда, когда он имеет направленный путь, содержащий все вершины, и в этом случае порядок совпадает с порядком, в котором вершины появляются в пути. [9]
Семейство топологических порядков DAG совпадает с семейством линейных расширений отношения достижимости для DAG [10], поэтому любые два графа, представляющие один и тот же частичный порядок, имеют одинаковый набор топологических порядков.
Комбинаторное перечисление
Проблема перечисления графов подсчета ориентированных ациклических графов была изучена Робинсоном (1973) . [11] Количество групп DAG на n помеченных вершинах для n = 0, 1, 2, 3,… (без ограничений на порядок, в котором эти числа появляются в топологическом порядке DAG) равно
Эти числа могут быть вычислены с помощью рекуррентного соотношения
Eric W. Weisstein высказал предположение, [12] , и Маккей и соавт. (2004) доказали, что одни и те же числа учитывают (0,1) матрицы, для которых все собственные значения являются положительными действительными числами . Доказательство биективно : матрица A является матрицей смежности DAG тогда и только тогда, когда A + I является матрицей (0,1) со всеми положительными собственными значениями, где I обозначает единичную матрицу . Поскольку в DAG не может быть петель , его матрица смежности должна иметь нулевую диагональ, поэтому добавление I сохраняет свойство, согласно которому все коэффициенты матрицы равны 0 или 1. [13]
Связанные семейства графов
Polytree представляет собой ориентированный граф , образованный путем ориентации ребер свободного дерева . [14] Каждое многодерево является DAG. В частности, это относится к древесным зарослям, образованным путем направления всех краев наружу от корней дерева.
Multitree (также называется сильно недвусмысленные графами или мангровым) представляет собой ориентированный граф , в котором существует не более одного путь направляется (в любом направлении) между любыми двумя вершинами; эквивалентно, это DAG, в котором для каждой вершины v подграф, достижимый из v, образует дерево. [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 . Задача может быть сформулирована для ориентированных графов без предположения об ацикличности, но без большей общности, поскольку в этом случае она эквивалентна той же задаче о сгущении графа. Ее можно решить за полиномиальное время, используя задачу сведения к максимальному потоку . [25]
Алгоритмы пути
Некоторые алгоритмы упрощаются при использовании в DAG вместо общих графов, основанных на принципе топологического упорядочения. Например, можно найти кратчайшие и самые длинные пути из заданной начальной вершины в DAG за линейное время, обрабатывая вершины в топологическом порядке и вычисляя длину пути для каждой вершины как минимальную или максимальную длину, полученную с помощью любого входящих краев. [26] В отличие от этого , для произвольных графов кратчайший путь может потребовать более медленные алгоритмы , такие как алгоритм Дейкстры или Беллмана-Форда алгоритма , [27] и длинных путей в произвольных графов NP-трудно найти. [28]
Приложения
Планирование
Направленные ациклические графы, представляющие частичные упорядочения, имеют множество приложений в планировании систем задач с ограничениями порядка. [29] Важный класс проблем этого типа касается наборов объектов, которые необходимо обновить, таких как ячейки электронной таблицы после изменения одной из ячеек или объектные файлы компьютерного программного обеспечения после его источника. код был изменен. В этом контексте граф зависимостей - это граф, который имеет вершину для каждого обновляемого объекта и ребро, соединяющее два объекта, когда один из них необходимо обновить раньше, чем другой. Цикл на этом графике называется циклической зависимостью и обычно не допускается, потому что не было бы возможности последовательно планировать задачи, участвующие в цикле. Графы зависимостей без циклических зависимостей образуют группы DAG. [30]
Например, при изменении одной ячейки электронной таблицы необходимо пересчитать значения других ячеек, которые прямо или косвенно зависят от измененной ячейки. Для этой проблемы необходимо запланировать задачи по пересчету значений отдельных ячеек электронной таблицы. Зависимости возникают, когда выражение в одной ячейке использует значение из другой ячейки. В таком случае используемое значение должно быть пересчитано раньше, чем выражение, которое его использует. Топологическое упорядочение графа зависимостей и использование этого топологического порядка для планирования обновлений ячеек позволяет обновлять всю электронную таблицу с помощью только одной оценки для каждой ячейки. [31] Подобные проблемы с упорядочением задач возникают в make-файлах для компиляции программ [31] и планирования инструкций для низкоуровневой оптимизации компьютерных программ. [32]
Несколько иная формулировка ограничений планирования на основе DAG используется в методике оценки и анализа программ (PERT), методе управления крупными человеческими проектами, который был одним из первых приложений 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] от Derek J. Прайса , который пошел на производство первой модели сети цитирования, цена модели . [50] В этом случае количество цитирований статьи - это просто внутренняя степень соответствующей вершины сети цитирования. Это важная мера при анализе цитирования . Судебные решения являются еще одним примером, поскольку судьи подтверждают свои выводы по одному делу, ссылаясь на другие решения, вынесенные ранее по предыдущим делам. Последний пример - патенты, которые должны относиться к предшествующему уровню техники , более ранние патенты, которые имеют отношение к текущей патентной заявке. Принимая во внимание особые свойства направленных ациклических графов, можно анализировать сети цитирования с помощью методов, недоступных при анализе общих графов, рассматриваемых во многих исследованиях, с использованием сетевого анализа . Например, транзитивная редукция позволяет по-новому взглянуть на распределение цитирования в различных приложениях, подчеркивая явные различия в механизмах создания сетей цитирования в разных контекстах. [51] Другой метод - анализ основного пути , который отслеживает ссылки цитирования и предлагает наиболее важные цепочки цитирования в данном графе цитирования .
Модель Прайса слишком проста, чтобы быть реалистичной моделью сети цитирования, но она достаточно проста, чтобы учесть аналитические решения для некоторых ее свойств. Многие из них можно найти, используя результаты , полученные из неориентированной версии модели Цены , по модели Barabási-Альберт . Однако, поскольку модель Прайса дает ориентированный ациклический граф, это полезная модель при поиске аналитических вычислений свойств, уникальных для ориентированных ациклических графов. Например, длина самого длинного пути от n-го узла, добавленного в сеть, до первого узла в сети, масштабируется как [52] .
Сжатие данных
Направленные ациклические графы также могут использоваться как компактное представление набора последовательностей. В приложении этого типа можно найти группу DAG, в которой пути образуют заданные последовательности. Когда многие из последовательностей совместно используют одни и те же подпоследовательности, эти общие подпоследовательности могут быть представлены общей частью DAG, что позволяет представлению использовать меньше места, чем для перечисления всех последовательностей по отдельности. Например, ориентированный ациклический граф слов - это структура данных в информатике, образованная ориентированным ациклическим графом с одним источником и ребрами, помеченными буквами или символами; пути от источника к стокам на этом графике представляют собой набор строк , таких как английские слова. [53] Любой набор последовательностей может быть представлен как пути в дереве путем формирования вершины дерева для каждого префикса последовательности и создания родительского элемента одной из этих вершин, представляющего последовательность с одним меньшим элементом; дерево, сформированное таким образом для набора строк, называется деревом . Направленный ациклический граф слов экономит место в дереве, позволяя путям расходиться и пересекаться, так что набор слов с одинаковыми возможными суффиксами может быть представлен одной вершиной дерева. [54]
Же идея использования DAG , чтобы представить семейство путей происходит в схеме двоичного решения , [55] [56] группа доступность базы данных на основе структура данных для представления двоичных функций. На диаграмме бинарных решений каждая вершина, не являющаяся приемником, помечена именем двоичной переменной, а каждый приемник и каждое ребро помечены 0 или 1. Значение функции для любого присвоения истинности переменным - это значение в приемник, найденный путем прохождения пути, начиная с единственной исходной вершины, который в каждой вершине, не являющейся приемником, следует за исходящим ребром, помеченным значением переменной этой вершины. Подобно тому, как ориентированные ациклические графы слов можно рассматривать как сжатую форму попыток, диаграммы бинарных решений можно рассматривать как сжатые формы деревьев решений, которые экономят место, позволяя путям соединяться, когда они согласовывают результаты всех оставшихся решений. [57]
Рекомендации
- ^ Туласираман, К .; Свами, Миннесота (1992), «5.7 Ациклические ориентированные графы», Графы: теория и алгоритмы , Джон Уайли и сын, стр. 118, ISBN 978-0-471-51356-8.
- ^ а б Банг-Йенсен, Йорген (2008), «2.1 Ациклические орграфы», орграфы: теория, алгоритмы и приложения , Монографии Springer по математике (2-е изд.), Springer-Verlag, стр. 32–34, ISBN 978-1-84800-997-4.
- ^ Кристофидес, Никос (1975), Теория графов: алгоритмический подход , Academic Press, стр. 170–174..
- ^ Митрани И. (1982), Методы моделирования для систем с дискретными событиями , Cambridge Computer Science Texts, 14 , Cambridge University Press, стр. 27, ISBN 9780521282826.
- ^ Козен, Декстер (1992), Разработка и анализ алгоритмов , Монографии по компьютерным наукам, Springer, стр. 9, ISBN 978-0-387-97687-7.
- ^ Банерджи, Утпал (1993), «Упражнение 2 (с)», Преобразования цикла для реструктуризации компиляторов: основы , Springer, p. 19, Bibcode : 1993ltfr.book ..... B , ISBN 978-0-7923-9318-4.
- ^ Банг-Йенсен, Йорген; Гутин, Грегори З. (2008), «2.3 Транзитивные орграфы, транзитивные замыкания и редукции», Орграфы: теория, алгоритмы и приложения , Монографии Springer по математике, Springer, стр. 36–39, ISBN 978-1-84800-998-1.
- ^ Юнгникель, Дитер (2012), Графы, сети и алгоритмы , алгоритмы и вычисления в математике, 5 , Springer, стр. 92–93, ISBN 978-3-642-32278-5.
- ^ Седжвик, Роберт ; Уэйн, Кевин (2011), «4,2,25 Уникальный топологический порядок», Алгоритмы (4-е изд.), Addison-Wesley, стр. 598–599, ISBN 978-0-13-276256-4.
- ^ Бендер, Эдвард А .; Уильямсон, С. Гилл (2005), «Пример 26 (Линейные расширения - топологические виды)», Краткий курс дискретной математики , Dover Books on Computer Science, Courier Dover Publications, стр. 142, ISBN 978-0-486-43946-4.
- ^ а б Робинсон, Р.В. (1973), «Подсчет помеченных ациклических орграфов», в Харари, Ф. (ред.), Новые направления в теории графов , Academic Press, стр. 239–273.. Смотрите также Харари, Фрэнк ; Палмер, Эдгар М. (1973), Graphical Enumeration , Academic Press , стр. 19, ISBN 978-0-12-324245-7.
- ^ Вайсштейн, Эрик В. , «Гипотеза Вайсштейна» , MathWorld
- ^ McKay, BD ; Ройл, Г.Ф . ; Wanless, IM; Оггиер, ИП ; Слоан, штат Нью-Джерси ; Уилф, H. (2004), "ациклические орграфы и собственные значения (0,1) -матриц" , журнал целочисленных последовательностей , 7 : 33, Arxiv : математика / 0310423 , Bibcode : 2004JIntS ... 7 ... 33М, Статья 04.3.3.
- ^ Ребане, Джордж; Перл, Иудея (1987), «Восстановление причинных полидеревьев из статистических данных», в Proc. 3-я ежегодная конференция по неопределенности в искусственном интеллекте (UAI 1987), Сиэтл, Вашингтон, США, июль 1987 г. (PDF) , стр. 222–228.[ постоянная мертвая ссылка ] .
- ^ Фурнас, Джордж У .; Закс, Джефф (1994), "Многодеревья: обогащение и повторное использование иерархической структуры", Proc. SIGCHI конференция по Factors человека в вычислительных системах (CHI '94) , стр 330-336,. Да : 10,1145 / 191666,191778 , ISBN 978-0897916509, S2CID 18710118.
- ^ а б Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Стейн, Клиффорд (2001) [1990], Введение в алгоритмы (2-е изд.), MIT Press и McGraw-Hill, ISBN 0-262-03293-7 Раздел 22.4, Топологическая сортировка, стр. 549–552.
- ^ a b Jungnickel (2012) , стр. 50–51.
- ^ Дляалгоритма топологической сортировки, основанного на поиске в глубину , эта проверка достоверности может чередоваться с самим алгоритмом топологической сортировки; см. например Скиена, Стивен С. (2009), Руководство по разработке алгоритмов , Springer, стр. 179–181, ISBN 978-1-84800-070-4.
- ^ Стэнли, Ричард П. (1973), «Ациклические ориентации графов» (PDF) , Дискретная математика , 5 (2): 171–178, DOI : 10.1016 / 0012-365X (73) 90108-8.
- ^ Гарей, Майкл Р .; Джонсон, Дэвид С. (1979), Компьютеры и несговорчивость: Руководство по теории NP-полноты , У. Х. Фриман , ISBN 0-7167-1045-5, Проблемы GT7 и GT8, стр. 191–192.
- ^ Харари, Фрэнк ; Норман, Роберт З .; Картрайт, Дорвин (1965), Структурные модели: Введение в теорию ориентированных графов , John Wiley & Sons, стр. 63.
- ^ Скиена (2009) , стр. 495.
- ^ Скиена (2009) , стр. 496.
- ↑ Bang-Jensen & Gutin (2008) , стр. 38.
- ^ Пикар, Жан-Клод (1976), "Максимальное закрытие графика и приложения к комбинаторным задачам", Управление науки , 22 (11): 1268-1272, DOI : 10,1287 / mnsc.22.11.1268 , MR 0403596.
- ^ Кормен и др. 2001, раздел 24.2, Кратчайшие пути из одного источника в ориентированных ациклических графах, стр. 592–595.
- ^ Кормен и др. 2001, разделы 24.1, Алгоритм Беллмана – Форда, стр. 588–592, и 24.3, Алгоритм Дейкстры, стр. 595–601.
- ^ Кормен и др. 2001, стр. 966.
- ^ Скиена (2009) , стр. 469.
- ^ Аль-Мутава, штат Джорджия; Дитрих, Дж .; Marsland, S .; McCartin, C. (2014), "О форме круговых зависимостей в программах на Java", двадцать третий Australian Software Engineering Conference , IEEE, С. 48-57,. Дои : 10,1109 / ASWEC.2014.15 , ISBN 978-1-4799-3149-1, S2CID 17570052.
- ^ а б Гросс, Джонатан Л .; Йеллен, Джей; Чжан, Пинг (2013), Справочник по теории графов (2-е изд.), CRC Press, стр. 1181, ISBN 978-1-4398-8018-0.
- ^ Срикант Ю.Н.; Шанкар, Прити (2007), Справочник по проектированию компиляторов: Оптимизация и генерация машинного кода (2-е изд.), CRC Press, стр. 19–39, ISBN 978-1-4200-4383-9.
- ^ Ван, Джон X. (2002), Что каждый инженер должен знать о принятии решений в условиях неопределенности , CRC Press, стр. 160, ISBN 978-0-8247-4373-4.
- ^ Сапатнекар, Сачин (2004), Timing , Springer, стр. 133, ISBN 978-1-4020-7671-8.
- ^ Деннис, Джек Б. (1974), "Первая версия потока данных языка процедуры", Программирование Symposium , конспекты лекций по информатике, 19 , стр 362-376,. DOI : 10.1007 / 3-540-06859-7_145 , ISBN 978-3-540-06859-4.
- ^ Туати, Сид; де Динечин, Бенуа (2014), Расширенная оптимизация серверной части, John Wiley & Sons, стр. 123, ISBN 978-1-118-64894-0.
- ^ Гарланд, Джефф; Энтони, Ричард (2003), Крупномасштабная программная архитектура: Практическое руководство с использованием UML , John Wiley & Sons, стр. 215, ISBN 9780470856383.
- ^ Гопник, Элисон; Шульц, Лаура (2007), Причинное обучение , Oxford University Press, стр. 4, ISBN 978-0-19-803928-0.
- ^ Шмулевич Илья; Догерти, Эдвард Р. (2010), Вероятностные булевы сети: моделирование и контроль регулирующих генных сетей , Общество промышленной и прикладной математики, стр. 58, ISBN 978-0-89871-692-4.
- ^ Коуэлл, Роберт Дж .; Давид, А. Филип ; Лауритцен, Штеффен Л .; Шпигельхальтер, Дэвид Дж. (1999), «3.2.1 Морализация», Вероятностные сети и экспертные системы , Springer, стр. 31–33, ISBN 978-0-387-98767-5.
- ^ Дорф, Ричард К. (1998), Справочник по управлению технологиями , CRC Press, стр. 9-7, ISBN 978-0-8493-8577-3.
- ^ Босло, Сара (2008), Энциклопедия эпидемиологии, том 1 , SAGE, стр. 255, ISBN 978-1-4129-2816-8.
- ^ Pearl, Иудея (1995), "причинные схемы для эмпирического исследования" , Biometrika , 82 (4): 669-709, DOI : 10,1093 / Biomet / 82.4.669.
- ^ Киркпатрик, Бонни Б. (апрель 2011), "гаплотипы против генотипов по родословных", алгоритмы молекулярной биологии , 6 (10): 10, DOI : 10,1186 / 1748-7188-6-10 , PMC 3102622 , PMID 21504603.
- ^ Макгаффин, MJ; Балакришнан, Р. (2005), «Интерактивная визуализация генеалогических графиков» (PDF) , Симпозиум IEEE по визуализации информации (INFOVIS 2005) , стр. 16–23, doi : 10.1109 / INFVIS.2005.1532124 , ISBN 978-0-7803-9464-3.
- ^ Бендер, Майкл А .; Пеммасани, Гиридхар; Скиена, Стивен; Сумазин, Павел (2001), «Поиск наименее общих предков в ориентированных ациклических графах» , Труды двенадцатого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам (SODA '01) , Филадельфия, Пенсильвания, США: Общество промышленной и прикладной математики, стр. 845–854, ISBN 978-0-89871-490-6.
- ^ Бартланг, Удо (2010), Архитектура и методы гибкого управления контентом в одноранговых системах , Springer, стр. 59, Bibcode : 2010aamf.book ..... B , ISBN 978-3-8348-9645-2.
- ^ Пах, Янош ; Шарир, Миха , Комбинаторная геометрия и ее алгоритмические приложения: лекции Алкалы , математические обзоры и монографии, 152 , Американское математическое общество, стр. 93–94, ISBN 978-0-8218-7533-9.
- ^ Прайс, Дерек Дж. Де Солла (30 июля 1965 г.), «Сети научных статей» (PDF) , Science , 149 (3683): 510–515, Bibcode : 1965Sci ... 149..510D , doi : 10.1126 / science.149.3683.510 , PMID 14325149.
- ^ Прайс, Дерек Дж. Де Солла (1976), "Общая теория библиометрических и других процессов накопления преимуществ", J.Amer.Soc.Inform.Sci. , 27 (5): 292-306, DOI : 10.1002 / asi.4630270505.
- ^ Клаф, Джеймс Р .; Голлингс, Джейми; Вьюн, Тамар В .; Эванс, Тим С. (2015), «Переходное сокращение сетей цитирования», Журнал сложных сетей , 3 (2): 189–203, arXiv : 1310.8224 , doi : 10.1093 / comnet / cnu039 , S2CID 10228152.
- ^ Evans, TS; Calmon, L .; Василяускайте, В. (2020), «Самый длинный путь в ценовой модели», Научные отчеты , 10 (1): 10503, arXiv : 1903.03667 , Bibcode : 2020NatSR..1010503E , doi : 10.1038 / s41598-020-67421-8 , PMC 7324613 , PMID 32601403
- ^ Крошмор, Максим; Верен, Рено (1997), "Прямое построение компактных ориентированных ациклических графов слов", Комбинаторное сопоставление с образцом, конспект лекций по информатике, 1264 , Springer, стр. 116–129, CiteSeerX 10.1.1.53.6273 , doi : 10.1007 / 3 -540-63220-4_55 , ISBN 978-3-540-63220-7.
- ^ Лотэр, М. (2005), Прикладная комбинаторика слов , Энциклопедия математики и ее приложений, 105 , Cambridge University Press, стр. 18, ISBN 9780521848022.
- ^ Ли, CY (1959), "Представление коммутационных схем программами двоичного решения", Bell System Technical Journal , 38 (4): 985–999, doi : 10.1002 / j.1538-7305.1959.tb01585.x.
- ^ Акерс, Шелдон B. (1978), "Бинарные диаграммы решения", IEEE Transactions на компьютерах , C-27 (6): 509-516, DOI : 10,1109 / TC.1978.1675141 , S2CID 21028055.
- ^ Фридман, SJ; Supowit, KJ (1987), "Нахождение оптимального порядка переменных для диаграмм двоичных решений", Proc. Двадцать четвёртая ACM / IEEE Design Automation Conference (DAC '87) , Нью - Йорк, Нью - Йорк, США:. ACM, стр 348-356, DOI : 10,1145 / 37888,37941 , ISBN 978-0-8186-0781-3, S2CID 14796451.
Внешние ссылки
- Вайсштейн, Эрик В. , "Ациклический диграф" , MathWorld
- DAGitty - онлайн-инструмент для создания DAG