Операция 1

Матрица должна иметь в точности один пустой столбец и одну пустую строку[ЧП2].

Пустому столбцу приписываем № 1. Этот же номер присваивается соответствующей строке. Номер столбца вписывается в дополнительную строку под матрицей и в дополнительный столбец справа от матрицы.

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

Операция 2

Пустому столбцу присваивается № 1. Этот же номер присваивается соответствующей строке. Номер столбца вписывается в дополнительную строку под матрицей (рис. 4а) и в дополнительный столбец , приписанный к матрице справа.

Операция 3

Общий шаг. Из матрицы вычеркиваются элементы пронумерованной ранее строки (строк). Например, из строки , которой присваивается № 1, вычеркиваются три элемента: , и .

Операция 4

Рассматривается подмножество непронумерованных столбцов, имеющих вычеркнутые элементы . В нашем примере такими столбцами будут: , , и . Элементы этих столбцов входят в очередную подматрицу . Всем соответствующим столбцам присваивается очередной номер. Этот же номер присваивается соответствующим строкам. В нашем примере № 2 получат столбцы , , и (рис. 12). Ячейки подкрасим желтым цветом. Таким образом, пронумерована вершина 2.

а)	б)

Рис. 12

Операция 5

Матрица переписывается с новым порядком рядов (рис. 13), полученным после выполнения операций 3 и 4.

Операция 6 (определение номеров начальных событий)

Определение номеров начальных событий для дуг графа (обыкновенной сетевой модели) происходит следующим образом. Номера рядов матрицы , полученные в операциях 2, 3 и 4 – суть номера подматриц , на которые распадается матрица или номера начальных событий для работ, которым соответствуют столбцы матрицы . Эти номера в виде упорядоченного ряда чисел выписаны под матрицей на рис. 13. Справа от матрицы составлена таблица, столбец которой получен путем транспонирования строки .

В данный момент у нас всего два номера (1 и 2).

а)	б)

Рис. 13

Операция 7 (определение номеров конечных событий)

Определение номеров конечных событий для каждой работы (дуги) выполняется путем проецирования строки на элементы матрицы (стрелка ) и далее путем проецирования полученного элемента на столбец (стрелка ). Процесс наглядно представлен на рис. 4б. В последней строке столбца , соответствующей пустой строке матрицы , выписывается номер конечной вершины всего графа (или сетевой модели) на единицу больший, чем наибольший номер в столбце . Пронумерована вершина 2.

Снова делаем первый общий шаг. Вычеркиваем элементы , и из строки с номером 2 и снова операция 6: ставим 3 в строку под матрицей.

Снова операция 5

Операция 5

Матрица переписывается с новым порядком рядов (рис. 14), полученным после выполнения операций 3 и 4.

а)	б)

Рис. 14

Операция 6 (определение номеров начальных событий)

Определение номеров начальных событий для дуг графа (обыкновенной сетевой модели) происходит следующим образом. Номера рядов матрицы , полученные в операциях 2, 3 и 4 – суть номера подматриц , на которые распадается матрица или номера начальных событий для работ, которым соответствуют столбцы матрицы . Эти номера в виде упорядоченного ряда чисел выписаны под матрицей на рис. 14. Справа от матрицы составлена таблица, столбец которой получен путем транспонирования строки .

Далее операция 7. Номер получила вершина 4.

Операция 7 (определение номеров конечных событий)

Определение номеров конечных событий для каждой работы (дуги) выполняется путем проецирования строки на элементы матрицы (стрелка ) и далее путем проецирования полученного элемента на столбец (стрелка ). Процесс наглядно представлен на рис. 4б. В последней строке столбца , соответствующей пустой строке матрицы , выписывается номер конечной вершины всего графа (или сетевой модели) на единицу больший, чем наибольший номер в столбце .

Снова переписываем матрицу с новым порядком рядов: меняем местами столбцы и в целях упорядочения номеров конечных событий.

а)	б)

Рис. 15

И нумеруем вершину 5.

а)	б)

 

а)	б)

 

а)	б)

 

а)	б)

 

[ЧП1]Вставить кусок из алгоритма для ОЛьги

[ЧП2]Вставить кусок из алгоритма для ОЛьги