Проектирование элементов информационного обеспечения и оценка функционирования АСОУ. Косников Ю.Н. - 19 стр.

                                                                                       19

       Анализ графа проводится обычно в следующей последовательности:
А. Выявление ошибок построения графа. При построении граф-схемы
потока данных в неё ошибочно могут быть включены элементы, не
имеющие к ней отношения (не связанные с другими элементами графа).
Таким элементам в матрице                       A1     соответствуют строка и столбец,
заполненные нулями. Так, в граф на рисунке 2,а ошибочно включена
вершина      4,   что    проявляется              в    одновременном    равенстве   нулю
содержимого четвёртой строки и четвёртого столбца. Другая ошибка —
наличие контуров. Контур — это замкнутый путь в графе, то есть путь, у
которого начальная и конечная вершины совпадают. Признаком контура
является наличие единиц на главной диагонали любой матрицы A L .
Номера позиций, в которых стоят единицы, указывают на образующие
контур вершины.
Б.     Определение      входных             и     выходных      элементов.    К   входным
элементам дуги от других вершин графа не подходят, из выходных
элементов дуги к другим вершинам не отходят. Поэтому эти элементы
легко выявляются по матрице смежности: для входных σ j (L = 1) = 0 (сумма

единиц в столбце равна нулю), для выходных σ i (L = 1) = 0 (сумма единиц в
строке равна нулю).
В. Определение диаметра графа. Полезным для многих приложений
является определение диаметра графа d. Если d ij — длина минимального

пути между входным x i и выходным x j элементами, выраженная числом

дуг,    составляющих               этот   путь,       то   диаметр   графа   определяется
выражением:        d = max d ij .
                        xi , x j


       Диаметр — это максимальный из минимальных путей, соединяющих
во всех возможных сочетаниях входные и выходные вершины графа. Для
информационных потоков он характеризует их временную задержку (в
тактах), то есть время, которое пройдёт от момента подачи исходных