Математические модели в управлении. Заболотский В.П - 87 стр.

UptoLike

ВУЗ: 

СПб ГУАП | Санкт-Петербург

Составители: 

Рубрика: 

87
Это означает, что
2
1.
q
n
Lnn+≤+−
Таким образом, в результате выполнения первого этапа получают
квазиканоническую матрицу смежности R
q
размерности n + L
q
.
2-й этап. Нумерация вершин реберного графа
На этом этапе нумеруются вершины реберного графа и между ними
распределяются дуги, соответствующие вершинам исходного графа.
1-й шаг. Просматривают матрицу R
q
либо R
[n]
. Если в матрице име-
ется более одного пустого столбца, то к матрице R
q
добавляют слева
один столбец, а сверху – одну строку. В новую строку на местах, соот-
ветствующих пустым столбцам матрицы R
q
, проставляют единицы.
Добавленным столбцу и строке присваивают одинаковый номер. При
ручном счете этот номер может быть очередным. При реализации ме-
тодики на ЭВМ столбцы и строки следует перенумеровать в соответ-
ствии с их расположением в матрице, сохраняя возможность последую-
щего восстановления исходной нумерации.
Замечание. Данный шаг соответствует преобразованию графа к виду, в котором
только одна вершина не имеет входящих в нее дуг.
2-й шаг. Если в матрице R
q
либо R
[n]
имеется более одной пустой
строки, то к матрице R
q
добавляют справа один столбец, а снизу – одну
строку. В добавленный столбец на местах, соответствующих пустым
строкам матрицы R
q
, проставляют единицы. Добавленным столбцу и
строке присваивают одинаковый очередной номер.
Замечание. Второй шаг соответствует преобразованию графа к виду, в котором
только одна вершина не имеет исходящих из нее дуг.
3-й шаг. Справа от матрицы R
q
строят таблицу дуг реберного гра-
фа. Таблица имеет три столбца N
в
, N
нач
, N
кон
и число строк, соответ-
ствующее числу строк матрицы R
q
. В столбец N
в
проставляются номе-
ра строк матрицы R
q
. Столбцы N
нач
и N
кон
заполняются в процессе вы-
полнения дальнейших шагов второго этапа.
4-й шаг. Пустому столбцу матрицы R
q
присваивают некоторый но-
мер (индекс). Этот номер присваивают соответствующей строке мат-
рицы R
q
, т. е. строке, номер которой соответствовал номеру столбца до
присваивания ему индекса. Присвоенный индекс проставляется также
в столбце N
нач
таблицы дуг реберного графа в соответствующей строке.

Страницы