Задача
Для представления каждой задачи в таком взаимозависимом множестве задач создается узел, а требование о завершении 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, потому что все ребра идут слева направо. ■
Еще по теме Задача:
- ЗАДАЧИ ОБЩИЕ И ЗАДАЧИ СПЕЦИАЛЬНЫЕ
- 7. Каждый школьник – это сложнейший мир проблем и задач. Забота о своевременном решении этих проблем и задач составляет основу строительства новой школы
- Вторая зрелость наступает тогда, когда человек выполнил задачи зрелого человека, осознал задачи второй зрелости и готов их выполнять
- ЗАДАЧА
- ЗАДАЧА: РЕШЕНИЕ
- Основные задачи.
- в) Задачи
- в) Задачи
- ПСИХОАНАЛИЗ: ЗАДАЧА
- ЗАДАЧА ДВИГАТЕЛЬНАЯ