Задача

Направленные ациклические графы (DAG) очень часто встречаются в теории об- работки информации, потому что многие типы сетей зависимостей (см. раздел 3.1) ацикличны. Следовательно, DAG могут естественным образом использоваться для представления отношений предшествования или зависимостей.
Допустим, имеется множество задач {1, 2, ..., n}, которые требуется выполнить; между задачами суще- ствуют зависимости — допустим, они указывают, что для пары i и j задача i должна быть выполнена до j. Скажем, задачи могут представлять учебные курсы, а некий курс можно пройти только после завершения необходимых вводных курсов. Или же задачи могут соответствовать последовательности вычислительных задач; за- дача j получает свои входные данные на выходе задачи i, поэтому задача i должна быть завершена до задачи j.

Для представления каждой задачи в таком взаимозависимом множестве задач создается узел, а требование о завершении i до j представляется направленным ребром (i, j). Чтобы отношения предшествования имели реальный смысл, полу- ченный граф G должен быть направленным ациклическим графом, то есть DAG. В самом деле, если граф содержит цикл C, то никакие задачи из C выполнены быть не могут: так как каждая задача из C не может начаться до завершения другой за- дачи из C, ни одна из них не может быть выполнена первой.

Давайте немного разовьем это представление DAG как отношений предшество- вания. Для заданного множества задач с зависимостями возникает естественный вопрос о нахождении действительного порядка выполнения этих задач с соблю- дением всех зависимостей, а именно: для направленного графа G топологическим упорядочением называется такое упорядочение его узлов v1, v2, ..., v , при котором для каждого ребра (vi, v) выполняется условие i < j.

Иначе говоря, все ребра в этом упорядочении указывают «вперед». Топологическое упорядочение задач описывает порядок их безопасного выполнения, то есть когда мы приходим к задаче vj, все задачи, которые ей должны предшествовать, уже были выполнены. На рис. 3.7, b узлы DAG из части (a) помечены в соответствии с их топологическим упорядоче- нием; каждое ребро действительно ведет от узла с малым индексом к узлу с более высоким индексом.

Более того, топологическое упорядочение G может рассматриваться как прямое «свидетельство» отсутствия циклов в G.

(3.18) Если в графе G существует топологическое упорядочение, то граф G является DAG.

Доказательство. Действуя от обратного, предположим, что в графе G существу- ет топологическое упорядочение v1, v2, ..., vn и цикл C. Пусть v — узел C с наимень- шим индексом, а v. — узел C, непосредственно предшествующий v; следовательно, существует ребро (v., v). Но согласно нашему выбору i выполняется условие j > i, а это противоречит предположение о том, что v1, v2, ..., vn является топологическим упорядочением.

Гарантия ацикличности, предоставляемая топологическим упорядочением, может быть очень полезной даже на визуальном уровне. На рис. 3.7, c изображен тот же граф, что и на рис. 3.7, a и b, но с расположением узлов в соответствии с то- пологическим упорядочением. С первого взгляда видно, что граф (c) представляет собой DAG, потому что все ребра идут слева направо. ■

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

Еще по теме Задача:

  1. ЗАДАЧИ ОБЩИЕ И ЗАДАЧИ СПЕЦИАЛЬНЫЕ
  2. 7. Каждый школьник – это сложнейший мир проблем и задач. Забота о своевременном решении этих проблем и задач составляет основу строительства новой школы
  3. Вторая зрелость наступает тогда, когда человек выполнил задачи зрелого человека, осознал задачи второй зрелости и готов их выполнять
  4. ЗАДАЧА
  5. ЗАДАЧА: РЕШЕНИЕ
  6. Основные задачи.
  7. в) Задачи
  8. в) Задачи
  9. ПСИХОАНАЛИЗ: ЗАДАЧА
  10. ЗАДАЧА ДВИГАТЕЛЬНАЯ