knigechka: 2.4.Cетевой метод оценки алгоритма для графа с циклами

Если граф, для оцениваемого алгоритма содержит циклы, то применяется предварительный метод сжатия циклов и замены их вершинами с эквивалентными им трудоёмкостями.

Напомним, что циклом называется совокупность вершин и дуг, охватываемых дугой обратной связи.

Циклы могут быть многократно вложены друг в друга.

Циклом 1-го ранга называется цикл, не содержащий внутри себя ни одного цикла.

Очевидно, что тело цикла 1-го ранга – ориентированный граф без циклов.

Циклом 2-го ранга называется цикл, содержащий хоть бы один цикл 1-го ранга.

Циклом S-го ранга называется цикл, содержащий внутри себя хотя бы один цикл (S-1)-го ранга и, возможно, циклы меньших рангов.

Процесс сжатия циклов в эквивалентные им по трудоемкости вершины начинается с самых внутренних циклов, т.е. с циклов 1-го ранга.

Поскольку тело такого цикла – ориентированный граф без циклов, то к нему может быть применим сетевой метод оценки трудоемкости, после чего все вершины этого подграфа, за исключением условной вершины цикла легко «сжать» в одну вершину С, присвоив ей трудоемкость . Пусть трудоемкость условной вершины Y равна q_y.

В процессе сжатия циклов 1-го ранга встречаются следующие типы циклов:

Воспользуемся методом марковских цепей для оценки средней трудоемкости q_цi каждого типа цикла:

После такого подсчета все вершины цикла Ц_i сжимаются в одну вершину цикла с трудоемкостью q_ц и с вероятностями входа и выхода равными 1.

После сжатия циклов 1-го ранга, они исчезают, а циклы 2-го ранга становятся циклами 1-го ранга. Процесс повторяется до тех пор, пока все циклы не будут сжаты и не получен граф без циклов, к которому может быть применен сетевой метод.

Рассмотрим пример: