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

Cтраница 2

Файловая система, содержащая совместно используемый файл. [16]

На рис. 6.15 снова показана файловая система с рис. 6.6, только теперь один из файлов пользователя С присутствует также в каталоге пользователя В. Соединение между каталогом пользователя В и совместно используемым файлом называется связью. Сама файловая система теперь представляет собой ориентированный ациклический граф ( DAG, Directed Acyclic Graph), а не дерево. [17]

Файловая система, содержащая совместно используемый файл. [18]

С присутствует также в каталоге пользователя В. Соединение между каталогом пользователя В и совместно используемым файлом называется связью. Сама файловая система теперь представляет собой ориентированный ациклический граф ( DAG, Directed Acyclic Graph), а не дерево. [19]

Известно, что некоторые частные случаи задачи об изоморфизме графов ( например, изоморфизм планарных графов) легкие. Другие столь же трудны, как и общая задача. Покажите, что задача об изоморфизме корневых ориентированных ациклических графов имеет ту же сложность, что и задача об изоморфизме произвольных графов. [20]

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

Узлы графа представляют входы и переменные. Если / - - g h - шаг, то из g в / и из h в / идут ориентированные ребра. Заметим, что число шагов программы ровно вдвое меньше числа ребер. Поэтому нижняя оценка числа ребер в любом ориентированном ациклическом графе, соответствующем вычислению для конкретной задачи, дает нижнюю оценку числа шагов в любой неветвящейся программе для этой задачи. [22]

Страницы: 1 2