ВУЗ:
Составители:
Рубрика:
Глава 1. Основные понятия теории графов 39
2) длина критического пути графа на 1 меньше минимального
числа индексов, которыми можно пометить все его вершины;
3) для любого целого числа s ≤ n, но большего длины критическо-
го пути, существует такая разметка вершин ациклического графа G,
в которой используются все s индексов.
Граф, размеченный в соответствии с утверждением 1.10, называ-
ется параллельной формой графа, а процесс разметки вершин назы-
вается топологической сортировкой графа [9]. Такая сортировка на-
зывается линейной, если все верши-
ны помечены разными индексами.
Например, на рис. 1.43 вершины
графа линейно отсортированы и
s = 5.
Если при разметке графа все
входные вершины окажутся в од-
ной группе с индексом 1, то такая
форма называется канонической. У графа такая форма единственна.
Для детерминированных алгоритмов программная реализация не
содержит условных операторов. Соответствующие им информаци-
онные графы имеют наиболее простую структуру. В этом случае
всегда существует взаимно-однозначное отображение между верши-
нами информационного графа алгоритма и всеми операциями соот-
ветствующей ему программы. Отметим, что в любой программе реа-
лизуются только явные вычисления, поэтому информационный граф
детерминированного алгоритма всегда является ациклическим орг-
рафом. Допустим, что все операции алгоритма разделены на группы,
причем каждая операция любой группы зависит либо от начальных
данных, либо от результатов выполнения операций, находящихся в
предыдущих группах. Такое представление алгоритма называется
параллельной формой алгоритма (ПФА). Каждая группа операций
называется ярусом ПФА, число групп – высотой ПФА, максималь-
ное число операций в ярусе – шириной ПФА.
Пусть точками на плоскости, которые будем считать вершинами
орграфа, изображено множество всех операций алгоритма. Каждой
вершине можно поставить в соответствие имя и размер (количество
1
32
5
4
Рис. 1.43
Страницы
- « первая
- ‹ предыдущая
- …
- 37
- 38
- 39
- 40
- 41
- …
- следующая ›
- последняя »
