Операция 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]Вставить кусок из алгоритма для ОЛьги
|