Это хорошая статья. Для получения дополнительной информации нажмите здесь.
Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

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

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

Определения [ править ]

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

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

Математические свойства [ править ]

Достижимость, транзитивное замыкание и транзитивная редукция [ править ]

Транзитивная редукция G

Отношения достижимости в любом ориентированном ациклическом графе можно формализовать как частичный порядок ≤ на вершинах 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]

Топологический порядок [ править ]

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

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

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

Комбинаторное перечисление [ править ]

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

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

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

[11]

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

Связанные семейства графиков [ править ]

Polytree , A ДАГ , образованный ориентируя края неориентированного дерева
Multitree , А ДАГ , в котором каждый подграф достижима из одной вершины (красной), дерево

Polytree представляет собой ориентированный граф , образованный путем ориентации ребер свободного дерева . [14] Каждое многодерево является DAG. В частности, это относится к древесным зарослям, образованным путем направления всех краев наружу от корней дерева.

Multitree (также называется сильно недвусмысленные графами или мангровым) представляет собой ориентированный граф , в котором существует не более одного путь направляется (в любом направлении) между любыми двумя вершинами; эквивалентно, это DAG, в котором для каждой вершины v подграф, достижимый из v, образует дерево. [15]

Вычислительные проблемы [ править ]

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

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

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

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

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

Любой неориентированный граф можно превратить в группу доступности базы данных, выбрав общий порядок для его вершин и направив каждое ребро от более ранней конечной точки в порядке к более поздней конечной точке. Полученная ориентация ребер называется ациклической ориентацией . Различные общие порядки могут привести к одной и той же ациклической ориентации, поэтому граф с 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]

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

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

Сети обработки данных [ править ]

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

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

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

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

Другой пример - нейронные сети с прямой связью .

Причинные структуры [ править ]

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

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

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

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

Генеалогия и история версий [ править ]

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

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

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

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

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

Графики цитирования [ править ]

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

Модель Прайса слишком проста, чтобы быть реалистичной моделью сети цитирования, но она достаточно проста, чтобы учесть аналитические решения для некоторых ее свойств. Многие из них можно найти, используя результаты , полученные из неориентированной версии модели Цены , по модели Barabási-Альберт . Однако, поскольку модель Прайса дает ориентированный ациклический граф, это полезная модель при поиске аналитических вычислений свойств, уникальных для ориентированных ациклических графов. Например, длина самого длинного пути от n-го узла, добавленного в сеть, до первого узла в сети, масштабируется как [55] .

Сжатие данных [ править ]

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

Же идея использования DAG , чтобы представить семейство путей происходит в схеме бинарного решения , [58] [59] группа доступность базы данных на основе структура данных для представления двоичных функций. На диаграмме двоичных решений каждая вершина, не являющаяся приемником, помечена именем двоичной переменной, а каждый приемник и каждое ребро помечены 0 или 1. Значение функции для любого присвоения истинности переменным - это значение в сток, найденный путем следования пути, начиная с единственной исходной вершины, который в каждой вершине, не являющейся стоком, следует за исходящим ребром, помеченным значением переменной этой вершины. Подобно тому, как ориентированные ациклические графы слов можно рассматривать как сжатую форму попыток, диаграммы бинарных решений можно рассматривать как сжатые формы деревьев решений.которые экономят место, позволяя путям воссоединяться, когда они согласовывают результаты всех оставшихся решений. [60]

Ссылки [ править ]

  1. ^ Туласираман, К .; Свами, Миннесота (1992), «5.7 Ациклические ориентированные графы», Графы: теория и алгоритмы , Джон Уайли и сын, стр. 118, ISBN 978-0-471-51356-8.
  2. ^ a b Банг-Дженсен, Йорген (2008), «2.1 Ациклические орграфы», орграфы: теория, алгоритмы и приложения , Монографии Springer по математике (2-е изд.), Springer-Verlag, стр. 32–34, ISBN 978-1-84800-997-4.
  3. ↑ Кристофидес, Никос (1975), Теория графов: алгоритмический подход , Academic Press, стр. 170–174.
  4. ^ Митрани, I. (1982), Методы моделирования для систем с дискретными событиями , Cambridge Computer Science Texts, 14 , Cambridge University Press, стр. 27, ISBN 9780521282826.
  5. Перейти ↑ Kozen, Dexter (1992), The Design and Analysis of Algorithms , Monographs in Computer Science, Springer, p. 9, ISBN 978-0-387-97687-7.
  6. ^ Банерджи, Утпал (1993), «Упражнение 2 (с)», Преобразования цикла для реструктуризации компиляторов: основы , Springer, стр. 19, ISBN 978-0-7923-9318-4.
  7. ^ Банг-Дженсен, Йорген; Гутин, Грегори З. (2008), «2.3 Транзитивные орграфы, транзитивные замыкания и редукции», Орграфы: теория, алгоритмы и приложения , Монографии Springer по математике, Springer, стр. 36–39, ISBN 978-1-84800-998-1.
  8. ^ Юнгникель, Дитер (2012), Графы, сети и алгоритмы , алгоритмы и вычисления в математике, 5 , Springer, стр. 92–93, ISBN 978-3-642-32278-5.
  9. ^ Седжвик, Роберт ; Уэйн, Кевин (2011), «4,2,25 Уникальный топологический порядок», Алгоритмы (4-е изд.), Addison-Wesley, стр. 598–599, ISBN 978-0-13-276256-4.
  10. ^ Бендер, Эдвард А .; Уильямсон, С. Гилл (2005), «Пример 26 (Линейные расширения - топологические виды)», Краткий курс дискретной математики , Dover Books on Computer Science, Courier Dover Publications, стр. 142, ISBN 978-0-486-43946-4.
  11. ^ a b Робинсон, Р. У. (1973), «Подсчет помеченных ациклических орграфов», в Харари, Ф. (ред.), Новые направления в теории графов , Academic Press, стр. 239–273. См. Также Harary, Frank ; Палмер, Эдгар М. (1973), Graphical Enumeration , Academic Press , стр. 19, ISBN 978-0-12-324245-7.
  12. ^ Вайсштейн, Эрик В. , "Гипотеза Вайсштейна" , MathWorld
  13. ^ Маккей, BD ; Ройл, Г.Ф . ; Wanless, IM; Оггиер, ИП ; Слоан, штат Нью-Джерси ; Уилф, Х. (2004), "Ациклические орграфы и собственные значения (0,1) -матриц" , Журнал целочисленных последовательностей , 7, Статья 04.3.3.
  14. ↑ Ребане, Джордж; Перл, Иудея (1987), «Восстановление причинных поли-деревьев из статистических данных», в Proc. 3-я ежегодная конференция по неопределенности в искусственном интеллекте (UAI 1987), Сиэтл, Вашингтон, США, июль 1987 г. (PDF) , стр. 222–228 [ постоянная мертвая ссылка ] .
  15. ^ Фурнас, Джордж У .; Закс, Джефф (1994), "Многодеревья: обогащение и повторное использование иерархической структуры", Proc. SIGCHI конференция по Factors человека в вычислительных системах (CHI '94) , стр 330-336,. Да : 10,1145 / 191666,191778 , ISBN 978-0897916509, S2CID  18710118.
  16. ^ а б Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Стейн, Клиффорд (2001) [1990], Введение в алгоритмы (2-е изд.), MIT Press и McGraw-Hill, ISBN 0-262-03293-7 Раздел 22.4, Топологическая сортировка, стр. 549–552.
  17. ↑ a b Jungnickel (2012) , стр. 50–51.
  18. ^ Дляалгоритма топологической сортировки на основе поиска в глубину эта проверка достоверности может чередоваться с самим алгоритмом топологической сортировки; см., например, Скиена, Стивен С. (2009), Руководство по разработке алгоритмов , Springer, стр. 179–181, ISBN 978-1-84800-070-4.
  19. ^ Стэнли, Ричард П. (1973), «Ациклические ориентации графов» (PDF) , Дискретная математика , 5 (2): 171–178, DOI : 10.1016 / 0012-365X (73) 90108-8 .
  20. ^ Гарей, Майкл Р .; Джонсон, Дэвид С. (1979), Компьютеры и несговорчивость: Руководство по теории NP-полноты , У. Х. Фриман , ISBN 0-7167-1045-5, Проблемы GT7 и GT8, стр. 191–192.
  21. ^ Харари, Фрэнк ; Норман, Роберт З .; Картрайт, Дорвин (1965), Структурные модели: Введение в теорию ориентированных графов , John Wiley & Sons, стр. 63.
  22. ^ Skiena (2009) , стр. 495.
  23. ^ Skiena (2009) , стр. 496.
  24. ↑ Bang-Jensen & Gutin (2008) , стр. 38.
  25. ^ Пикар, Жан-Клод (1976), "Максимальное закрытие графика и приложения к комбинаторным задачам", Управление науки , 22 (11): 1268-1272, DOI : 10,1287 / mnsc.22.11.1268 , MR 0403596 .
  26. ^ Кормен и др. 2001, раздел 24.2, Кратчайшие пути из одного источника в ориентированных ациклических графах, стр. 592–595.
  27. ^ Кормен и др. 2001, разделы 24.1, Алгоритм Беллмана – Форда, стр. 588–592, и 24.3, Алгоритм Дейкстры, стр. 595–601.
  28. ^ Кормен и др. 2001, стр. 966.
  29. ^ Skiena (2009) , стр. 469.
  30. ↑ Аль-Мутава, штат Джорджия; Дитрих, Дж .; 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.
  31. ^ a b Гросс, Джонатан Л .; Йеллен, Джей; Чжан, Пинг (2013), Справочник по теории графов (2-е изд.), CRC Press, стр. 1181, ISBN 978-1-4398-8018-0.
  32. ^ Срикант, Ю.Н. Шанкар, Прити (2007), Справочник по проектированию компиляторов: Оптимизация и генерация машинного кода (2-е изд.), CRC Press, стр. 19–39, ISBN 978-1-4200-4383-9.
  33. ^ Ван, Джон X. (2002), Что должен знать каждый инженер о принятии решений в условиях неопределенности , CRC Press, стр. 160, ISBN 978-0-8247-4373-4.
  34. ^ Sapatnekar, Сэчины (2004), Timing , Springer, стр. 133, ISBN 978-1-4020-7671-8.
  35. ^ Деннис, Джек Б. (1974), "Первая версия потока данных языка процедуры", Программирование Symposium , Lecture Notes в области компьютерных наук, 19 , стр 362-376,. Дои : 10.1007 / 3-540-06859-7_145 , ISBN 978-3-540-06859-4.
  36. ^ Туати, Сид; де Динешин, Бенуа (2014), Расширенная оптимизация серверной части, John Wiley & Sons, стр. 123, ISBN 978-1-118-64894-0.
  37. ^ Гарланд, Джефф; Энтони, Ричард (2003), Крупномасштабная программная архитектура: Практическое руководство с использованием UML , John Wiley & Sons, стр. 215, ISBN 9780470856383.
  38. ↑ Гопник, Элисон; Шульц, Лаура (2007), Причинное обучение , Oxford University Press, стр. 4, ISBN 978-0-19-803928-0.
  39. ^ Шмулевич, Илья; Догерти, Эдвард Р. (2010), Вероятностные булевы сети: моделирование и управление регулирующими генными сетями , Общество промышленной и прикладной математики, стр. 58, ISBN 978-0-89871-692-4.
  40. ^ Коуэлл, Роберт G .; Давид, А. Филип ; Lauritzen, Steffen L .; Шпигельхальтер, Дэвид Дж. (1999), «3.2.1 Морализация», Вероятностные сети и экспертные системы , Springer, стр. 31–33, ISBN 978-0-387-98767-5.
  41. ^ Дорф, Ричард К. (1998), Справочник по управлению технологиями , CRC Press, стр. 9-7, ISBN 978-0-8493-8577-3.
  42. ^ Boslaugh, Сара (2008), Энциклопедия эпидемиологии, Том 1 , SAGE, стр. 255, ISBN 978-1-4129-2816-8.
  43. ^ Pearl, Иудея (1995), "причинные схемы для эмпирического исследования" , Biometrika , 82 (4): 669-709, DOI : 10,1093 / Biomet / 82.4.669.
  44. ^ Киркпатрик, Бонни Б. (апрель 2011), "гаплотипы по сравнению с генотипами по родословных", алгоритмы молекулярной биологии , 6 (10): 10, DOI : 10,1186 / 1748-7188-6-10 , PMC 3102622 , PMID 21504603  .
  45. ^ Макгаффин, MJ; Балакришнан, Р. (2005), «Интерактивная визуализация генеалогических графов» (PDF) , Симпозиум IEEE по визуализации информации (INFOVIS 2005) , стр. 16–23, doi : 10.1109 / INFVIS.2005.1532124 , ISBN  978-0-7803-9464-3.
  46. ^ Бендер, Майкл А .; Пеммасани, Гиридхар; Скиена, Стивен; Сумазин, Павел (2001), "Поиск наименее общих предков в ориентированных ациклических графах" , Труды двенадцатого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам (SODA '01) , Филадельфия, Пенсильвания, США: Общество промышленной и прикладной математики, стр. 845–854, ISBN 978-0-89871-490-6.
  47. ^ Канн, Ребекка L .; Стоункинг, Марк; Уилсон, Аллан К. (январь 1987 г.). «Митохондриальная ДНК и эволюция человека» . Природа . 325 (6099): 31–36. DOI : 10.1038 / 325031a0 . ISSN 1476-4687 . 
  48. ^ Форстер, Питер; Форстер, Люси; Ренфрю, Колин; Форстер, Майкл (2020-04-08). «Филогенетический сетевой анализ геномов SARS-CoV-2» . Труды Национальной академии наук . 117 (17): 9241–9243. DOI : 10.1073 / pnas.2004999117 . ISSN 0027-8424 . PMC 7196762 . PMID 32269081 .   
  49. ^ "gitglossary Documentation" . Git . Сохранение свободы программного обеспечения . Дата обращения 7 ноября 2020 .
  50. ^ Бартланг, Удо (2010), Архитектура и методы гибкого управления контентом в одноранговых системах , Springer, стр. 59, ISBN 978-3-8348-9645-2.
  51. ^ Пах, Янош ; Шарир, Мика , Комбинаторная геометрия и ее алгоритмические приложения: лекции Алкалы , математические обзоры и монографии, 152 , Американское математическое общество, стр. 93–94, ISBN 978-0-8218-7533-9.
  52. ^ Цена, Derek J. де Солла (30 июля 1965 г.), "Сети научных трудов" (PDF) , Science , 149 (3683): 510-515, Bibcode : 1965Sci ... 149..510D , DOI : 10.1126 /science.149.3683.510 , PMID 14325149  .
  53. ^ Прайс, Дерек Дж. Де Солла (1976), "Общая теория библиометрических и других процессов накопления преимуществ", J.Amer.Soc.Inform.Sci. , 27 : 292-306, DOI : 10.1002 / asi.4630270505.
  54. ^ Клаф, Джеймс Р .; Голлингс, Джейми; Вьюн, Тамар В .; Эванс, Тим С. (2015), "Переходное сокращение сетей цитирования", Журнал сложных сетей , 3 (2): 189–203, arXiv : 1310.8224 , doi : 10.1093 / comnet / cnu039 , S2CID 10228152 .
  55. ^ Эванс, TS; Calmon, L .; Василяускайте, В. (2020), «Самый длинный путь в ценовой модели», Научные отчеты , 10 (1): 10503, arXiv : 1903.03667 , Bibcode : 2020NatSR..1010503E , doi : 10.1038 / s41598-020-67421-8 , PMC 7324613 , PMID 32601403  
  56. ^ Crochemore, Максим; Верен, Рено (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.
  57. ^ Lothaire, М. (2005), Applied Комбинаторика на словах , энциклопедии математики и ее приложений, 105 , Cambridge University Press, стр. 18, ISBN 9780521848022.
  58. ^ Ли, CY (1959), "Представление схем переключения программами двоичного решения", Bell System Technical Journal , 38 (4): 985–999, doi : 10.1002 / j.1538-7305.1959.tb01585.x.
  59. ^ Акерс, Шелдон Б. (1978), "Бинарные диаграммы решения", IEEE Transactions на компьютерах , C-27 (6): 509-516, DOI : 10,1109 / TC.1978.1675141 , S2CID 21028055 .
  60. ^ Фридман, 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