Cтраница 4
После определения значений потоков k, направленных в каждую Аг - ю ветвь, из всего набора имеющихся в пучке ветвей М выбирается L рациональных путей. Подготовительный этап к региональной маршрутизации и распределению в СПД, заканчивается выбором магистрального маршрута. Исследуем их последовательно, используя методику расчета кольцевых структур. Для этого необходимо кроме прямых, кратчайших отрезков магистрального Маршрута указать обходные пути методом поиска общих единиц с помощью матрицы связности. В результате получим регион RG. [46]
Алгоритмы определения самих компонент связности графа основаны на использовании матриц связности графов. В этом случае такого сорта матрицу называют матрицей связности. Матрицей связности графа Gen вершинами называют квадратную матрицу S размера п х п, у которой на пересечении г-ой строки и j - oro столбца стоит истинностное значение S ( i j) И, если г j или существует маршрут, соединяющий г-ую вершину с jf - ой. Поскольку ребра графа неориентированы, то S ( i j) S ( j i), т.е. матрица связности симметрична. [47]
Существует достаточно большое количество методов вычисления матриц связности и достижимости. В этой книге уже был описан алгоритм Уоршелла, предназначенный для вычисления матрицы достижимости ориентированного графа ( см. стр. Оказывается, с его помощью можно найти и матрицу связности неориентированного графа. Известная уже схема переносится на этот случай почти без изменений. Только в самое ее начало добавляется один шаг, обеспечивающий значения И на главной диагонали матрицы связности S. [48]
Алгоритмы определения самих компонент связности графа основаны на использовании матриц связности графов. В этом случае такого сорта матрицу называют матрицей связности. Матрицей связности графа Gen вершинами называют квадратную матрицу S размера п х п, у которой на пересечении г-ой строки и j - oro столбца стоит истинностное значение S ( i j) И, если г j или существует маршрут, соединяющий г-ую вершину с jf - ой. Поскольку ребра графа неориентированы, то S ( i j) S ( j i), т.е. матрица связности симметрична. [49]
В этом алгоритме первый цикл определяет Ф - процессоры 1-го процесса, на которых были блокирования по запросам к k - щ процессору, и заносит нуль в признак блокирования. Так как возможна ситуация, что запросивший А-процессор блокируется, не выполнив запроса от какого-либо предшествующего А-процессора этого же процесса, следовательно, также заблокированного, то при организации исполнения запроса организующая система должна проверить ситуацию на возможность самозамыкания. В отличие от исследования опасности самозамыкания во время формирования пакета задач для мультипрограммирования, где рассматривалось распределение ресурсов, самозамыкание в процессе реализации в основном происходит в результате ошибок в логике процесса. Поэтому, особенно в процессе отладки алгоритма, организующая система должна проверять ситуации, возникающие при блокировании процессов, на возможность самозамыкания. Для этого можно использовать то, что матрица г - го процесса в массиве block является матрицей смежности для графа, описывающего причины блокирования. Так как при возведении матрицы смежности в т степень элементы а будут отображать наличие путей длиной в т дуг, то при возведении матрицы связности в степень т матрица графа, не имеющего самозамыкания, будет равна нулю. [50]