stringtranslate.com

Направленный ациклический граф

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

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

Направленные ациклические графы также называются ациклическими направленными графами [1] или ациклическими орграфами [2] .

Определения

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

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

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

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

Отношение достижимости DAG можно формализовать как частичный порядок на вершинах DAG. В этом частичном порядке две вершины u и v упорядочены как uv именно тогда, когда существует направленный путь от u до v в DAG; то есть, когда u может достичь v (или v достижимо из u ). [5] Однако разные DAG могут приводить к одному и тому же отношению достижимости и одному и тому же частичному порядку. [6] Например, DAG с двумя ребрами uv и vw имеет то же отношение достижимости, что и DAG с тремя ребрами uv , vw , и uw . Оба этих DAG создают один и тот же частичный порядок, в котором вершины упорядочены как uvw .

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

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

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

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

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

Эрик В. Вайсштейн предположил [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]

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

Несколько иная формулировка ограничений планирования на основе 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]

Ссылки

  1. ^ ab Туласираман, К.; Свами, МНС (1992), "5.7 Ациклические направленные графы", Графы: теория и алгоритмы , John Wiley and Son, стр. 118, ISBN 978-0-471-51356-8.
  2. ^ abc Bang-Jensen, Jørgen (2008), "2.1 Ациклические орграфы", Орграфы: теория, алгоритмы и приложения , Springer Monographs in Mathematics (2-е изд.), Springer-Verlag, стр. 32–34, ISBN 978-1-84800-997-4.
  3. ^ Кристофидес, Никос (1975), Теория графов: алгоритмический подход , Academic Press, стр. 170–174.
  4. ^ Митрани, И. (1982), Методы моделирования для дискретных событийных систем, Cambridge Computer Science Texts, т. 14, Cambridge University Press, стр. 27, ISBN 9780521282826.
  5. ^ Козен, Декстер (1992), Разработка и анализ алгоритмов, Монографии по информатике, Springer, стр. 9, ISBN 978-0-387-97687-7.
  6. ^ Баннерджи, Утпал (1993), "Упражнение 2(c)", Циклические преобразования для реструктурирующих компиляторов: основы, Springer, стр. 19, Bibcode :1993ltfr.book.....B, ISBN 978-0-7923-9318-4.
  7. ^ Банг-Йенсен, Йорген; Гутин, Грегори З. (2008), "2.3 Транзитивные орграфы, транзитивные замыкания и сокращения", Орграфы: теория, алгоритмы и приложения, Springer Monographs in Mathematics, 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-е изд.), Эддисон-Уэсли, стр. 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. ^ ab Robinson, RW (1973), «Подсчет помеченных ациклических орграфов», в Harary, F. (ред.), Новые направления в теории графов , Academic Press, стр. 239–273. См. также Харари, Фрэнк ; Палмер, Эдгар М. (1973), Графическое перечисление , Academic Press , стр. 19, ISBN 978-0-12-324245-7.
  12. ^ Вайсштейн, Эрик В. , «Гипотеза Вайсштейна», MathWorld
  13. ^ Маккей, Б. Д .; Ройл, Г. Ф.; Ванлесс, И. М.; Оггиер , Ф. Э .; Слоан, Н. Я. А .; Вильф, Х. (2004), «Ациклические орграфы и собственные значения (0,1)-матриц», Журнал целочисленных последовательностей , 7 : 33, arXiv : math/0310423 , Bibcode : 2004JIntS...7...33M, Статья 04.3.3.
  14. ^ Фурнас, Джордж У .; Закс, Джефф (1994), «Мультидеревья: обогащение и повторное использование иерархической структуры», Труды конференции SIGCHI по человеческому фактору в вычислительных системах (CHI '94) , стр. 330–336, doi : 10.1145/191666.191778 , ISBN 978-0897916509, S2CID  18710118.
  15. ^ Ребейн, Джордж; Перл, Джудеа (1987), «Восстановление причинных поли-деревьев из статистических данных», в Трудах 3-й ежегодной конференции по неопределенности в искусственном интеллекте (UAI 1987), Сиэтл, Вашингтон, США, июль 1987 г. (PDF) , стр. 222–228.
  16. ^ аб Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Штейн, Клиффорд (2001) [1990], Введение в алгоритмы (2-е изд.), MIT Press и McGraw-Hill, ISBN 0-262-03293-7 Раздел 22.4, Топологическая сортировка, стр. 549–552.
  17. ^ ab Jungnickel (2012), стр. 50–51.
  18. ^ Для алгоритма топологической сортировки, основанного на поиске в глубину , эта проверка достоверности может быть перемежена с самим алгоритмом топологической сортировки; см., например, Skiena, Steven S. (2009), The Algorithm Design Manual, 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-полноты . Серия книг по математическим наукам (1-е изд.). Нью-Йорк: WH Freeman and Company . ISBN 9780716710455. MR  0519066. OCLC  247570676., Задачи GT7 и GT8, стр. 191–192.
  21. ^ Харари, Фрэнк ; Норман, Роберт З.; Картрайт, Дорвин (1965), Структурные модели: Введение в теорию направленных графов , John Wiley & Sons, стр. 63.
  22. ^ Скиена (2009), стр. 495.
  23. ^ Скиена (2009), стр. 496.
  24. ^ Банг-Дженсен и Гутин (2008), с. 38.
  25. ^ Пикар, Жан-Клод (1976), «Максимальное замыкание графа и приложения к комбинаторным задачам», Management Science , 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. ^ Скиена (2009), стр. 469.
  30. ^ Аль-Мутава, HA; Дитрих, Дж.; Марсланд, С.; Маккартин, К. (2014), «О форме циклических зависимостей в программах Java», 23-я Австралийская конференция по программной инженерии , IEEE, стр. 48–57, doi :10.1109/ASWEC.2014.15, ISBN 978-1-4799-3149-1, S2CID  17570052.
  31. ^ ab Гросс, Джонатан Л.; Йеллен, Джей; Чжан, Пин (2013), Справочник по теории графов (2-е изд.), CRC Press, стр. 1181, ISBN 978-1-4398-8018-0.
  32. ^ Шрикант, YN; Шанкар, Прити (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. ^ Сапатнекар, Сачин (2004), Timing, Springer, стр. 133, ISBN 978-1-4020-7671-8.
  35. ^ Деннис, Джек Б. (1974), «Первая версия языка процедур потока данных», симпозиум по программированию , заметки лекций по информатике, т. 19, стр. 362–376, doi :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. ^ Коуэлл, Роберт Г.; Дэвид, А. Филип ; Лауритцен, Штеффен Л .; Шпигельхальтер, Дэвид Дж. (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. ^ Босло, Сара (2008), Энциклопедия эпидемиологии, том 1, SAGE, стр. 255, ISBN 978-1-4129-2816-8.
  43. ^ Перл, Джудеа (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. ^ МакГаффин, М.Дж.; Балакришнан, Р. (2005), «Интерактивная визуализация генеалогических графов» (PDF) , Симпозиум IEEE по визуализации информации (INFOVIS 2005) , стр. 16–23, doi :10.1109/INFVIS.2005.1532124, ISBN 978-0-7803-9464-3, S2CID  15449409.
  46. ^ Бендер, Майкл А.; Пеммасани, Гиридхар; Скиена, Стивен; Сумазин, Павел (2001), «Поиск наименьших общих предков в направленных ациклических графах», Труды двенадцатого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам (SODA '01) , Филадельфия, Пенсильвания, США: Общество промышленной и прикладной математики, стр. 845–854, ISBN 978-0-89871-490-6.
  47. ^ Бартланг, Удо (2010), Архитектура и методы гибкого управления контентом в одноранговых системах, Springer, стр. 59, Bibcode :2010aamf.book.....B, ISBN 978-3-8348-9645-2.
  48. ^ Пах, Янош ; Шарир, Миха , Комбинаторная геометрия и ее алгоритмические приложения: Лекции в Алькале, Математические обзоры и монографии, т. 152, Американское математическое общество, стр. 93–94, ISBN 978-0-8218-7533-9.
  49. ^ Прайс, Дерек Дж. де Солла (30 июля 1965 г.), «Сети научных статей» (PDF) , Science , 149 (3683): ​​510–515, Bibcode : 1965Sci...149..510D, doi : 10.1126/science.149.3683.510, PMID  14325149.
  50. ^ Прайс, Дерек Дж. де Солла (1976), «Общая теория библиометрических и других кумулятивных процессов преимуществ», Журнал Американского общества информационной науки , 27 (5): 292–306, doi :10.1002/asi.4630270505, S2CID  8536863.
  51. ^ Клаф, Джеймс Р.; Голлингс, Джейми; Лоуч, Тамар В.; Эванс, Тим С. (2015), «Транзитивное сокращение сетей цитирования», Журнал сложных сетей , 3 (2): 189–203, arXiv : 1310.8224 , doi : 10.1093/comnet/cnu039, S2CID  10228152.
  52. ^ Эванс, ТС; Калмон, Л.; Василяускайте, В. (2020), «Самый длинный путь в модели цен», Scientific Reports , 10 (1): 10503, arXiv : 1903.03667 , Bibcode : 2020NatSR..1010503E, doi : 10.1038/s41598-020-67421-8, PMC 7324613 , PMID  32601403 
  53. ^ Crochemore, Maxime; Vérin, Renaud (1997), «Прямое построение компактных направленных ациклических графов слов», Combinatorial Pattern Matching , Lecture Notes in Computer Science, т. 1264, Springer, стр. 116–129, CiteSeerX 10.1.1.53.6273 , doi :10.1007/3-540-63220-4_55, ISBN  978-3-540-63220-7, S2CID  17045308.
  54. ^ Лотер, М. (2005), Прикладная комбинаторика в словах, Энциклопедия математики и ее приложений, т. 105, Cambridge University Press, стр. 18, ISBN 9780521848022.
  55. ^ Ли, CY (1959), «Представление коммутационных схем программами с бинарным решением», Bell System Technical Journal , 38 (4): 985–999, doi :10.1002/j.1538-7305.1959.tb01585.x.
  56. ^ Эйкерс, Шелдон Б. (1978), «Диаграммы бинарных решений», IEEE Transactions on Computers , C-27 (6): 509–516, doi :10.1109/TC.1978.1675141, S2CID  21028055.
  57. ^ Фридман, С. Дж.; Суповит, К. Дж. (1987), «Поиск оптимального порядка переменных для бинарных диаграмм решений», Труды 24-й конференции ACM/IEEE по автоматизации проектирования (DAC '87) , Нью-Йорк, США: ACM, стр. 348–356, doi :10.1145/37888.37941, ISBN 978-0-8186-0781-3, S2CID  14796451.

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