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

UptoLike

ВУЗ: 

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

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

Рубрика: 

96
пересечении со строкой 1. Вычеркиваем все единицы строки 1. В мат-
рице R
q
после этой операции оказывается свободным столбец 4. При-
сваиваем ему и строке 4 индекс "b". Этот же индекс проставляем в
строке столбца N
нач
таблицы дуг.
3-й шаг. Столбцу 3 матрицы R
q
присваиваем индекс "с". Этот же
индекс присваиваем строке 3 матрицы R
q
и проставляем в третьей стро-
ке столбца N
нач
таблицы. На этом нумерация столбцов, а следователь-
но, и вершин реберного графа заканчивается.
4-й шаг. Заполняем столбец N
кон
таблицы дуг реберного графа. В
столбцах "b" матрицы R
q
единицы находятся только в строке "а". По-
этому в соответствующую строку столбца N
кон
таблицы заносим ин-
декс "b". В столбце "с" единицы находятся в строках "b" матрицы R
q
.
Заносим индекс "с" в соответствующие строки столбца N
кон
таблицы. В
пустой строке столбца N
кон
делаем прочерк. На этом заполнение таб-
лицы заканчивается.
3-й этап. Построение диаграммы реберного графа
По таблице дуг реберного графа строим диаграмму графа, эквива-
лентного исходному. Столбец N
нач
таблицы содержит начальные вер-
шины дуг, столбец N
кон
– конечные вершины дуг, а столбец N
в
– номер
вершин исходного графа, эквивалентных соответствующим дугам. Вер-
шины, номеров которых нет у вершин исходного графа, считаются фик-
тивными. Такой вершиной являет-
ся вершина 4. Соответствующая
ей дуга изображается на графе
штриховой линией. Диаграмма ре-
берного графа представлена на
рис. 2.2.5.
В литературе по теории графов можно встретить следующее опре-
деление понятия реберного графа, которое применяется к неориентиро-
ванному графу.
Реберным (смежностным) графом или графом смежности ребер
для исходного графа называется граф, вершины которого взаимно одно-
значно сопоставлены ребрам исходного графа, причем две вершины ре-
берного графа имеют общие ребра в том и только в том случае, если
соответствующие им ребра исходного графа имеют общую вершину.
Матрица смежности вершин такого графа совпадает с матрицей
смежности ребер исходного графа. В дальнейшем, чтобы не возникало
Рис. 2.2.5. Диаграмма эквивалентного
реберного графа
2
a c db
1
4
3

Страницы