Матрица достижимости

Сокращенную матрицу смежности используют для определения рециклов и последовательности их расчета. Для этого с помощью булевой алгебры [16] находят степени матрицы смежности путем ее умножения. Для выявления замкнутых контуров и разомкнутых последовательностей внутри ХТС рассчитывают достижимые матрицы (М ) путем булевой суммы степенных матриц (Л") ЛГд =2 "- При п оо М М°°, где ЛГ°° — матрица достижимости, указывающая на существование какой-нибудь связи от блока i к блоку /, если элемент матрицы равен 1. Если диагональное значение какого-нибудь элемента матрицы равно 1, то, следовательно в ХТС имеется контур, в котором есть путь, связывающий блок i через п блоков с самим собой. Для определения номеров вершин, входящих в контур, авторы работы [16] предлагают применить матрицу пересечений [c.78]

Матрица достижимости, как и матрица смежности, симметрична относительно главной диагонали. При достаточно большом к нули в матрице достижимости имеют место, очевидно, только тогда, когда граф состоит более чем из [c.42]

Матрица достижимости ориентированного графа, построенная по правилам обычной алгебры, состоит из элементов г , каждый из которых равен числу маршрутов из вершины и в вершину V. [c.42]

Поэтому в блоке 2 алгоритма производится формирование матрицы достижимости на основе матрицы смежности свернутой сети. Пусть свернутая сеть задана матрицей смежности Ф = Ф > в которой элемент равен числу дуг, направленных из узла и в узел V, или пулю (в случае отсутствия дуги между этими узлами). [c.104]

Матрица достижимости , каждый элемент которой равен числу маршрутов длиною до г включительно, направленных из узла и в узел v сети (см. раздел 1 главы III), находится нри помощи [c.104]

При этом для первого шага (А = 1) матрица достижимости Ч о является нулевой. Условие окончания операций (1У.42) и (1У.43) заключается в отсутствии в матрице новых положительных элементов либо [c.105]

Как только на каком-то шаге к условия (1У.44) выполняются, в качестве матрицы достижимости принимается матрица [c.105]

Назовем матрицу Т скорректированной матрицей достижимости. Она образуется путем выполнения рекуррентных операций по формулам (1У.42) и (1У.43), в которых элементы матрицы ф - заменяются элементами скорректированной матрицы ф" . Условия окончания операций (IV.44) сохраняются такими же, как и при ползгчении матрицы Ч . [c.106]

Скорректированная матрица достижимости Т содержит данные только о простых путях, т. е. проходящих через узлы сети не более одного раза, поскольку все маршруты, не являющиеся простыми путями, разрываются при коррекции /с-той степени матрицы смежности. [c.106]

Тогда в скорректированной матрице Ф будут отражены эти маршруты, не являющиеся простыми путями и проходящие через узлы сети более одного раза. Например, если в сети имеется два одинаковых контура, не имеющих общих узлов и соединенных одним маршрутом (длина I), то на шаге к = р + I один из маршрутов, проходящий по первому контуру, будет отражен в матрице фф - , другой, проходящий по второму контуру, — в матрице ф - ф. Таким образом, коррекция матрицы достижимости не позволяет полностью исключить все отличные от простых маршруты, неоднократно проходящие через узлы сети, однако их число будет значительно меньше, чем в матрице достижимости, построенной без коррекции. [c.107]

Выделение двухполюсных подсетей по матрице достижимости начинается в блоке 3 алгоритма и состоит в выборе пар узлов и ж V, для которых значение суммы а1)цо + минимально (но не меньше, чем 2) для всех не рассмотренных на данном этапе пар узлов. [c.107]

В результате построения получаем, что подсеть с множеством узлов F, и дугами, соединяющими эти узлы, будет двухполюсной. Чтобы проверить, является ли она простой, по матрице достижимости устанавливается, входят ли во множество F, другие пары узлов, отличные от и и у, но соединенные тем же числом путей. Если таких пар нет, то легко показать, что построенная подсеть является простой двухполюсной с полюсами U и у. В противном случае, если такая пара узлов i и / существует и ни один из них не равен и или у, то в блоке 5 выделяется простая двухполюсная Подсеть с множеством узлов Vg (и, у). Полюсами этой подсети являются узлы i и j. Если есть пара узлов г, F и только один из них совпадает с узлом и или у, например г-тый, то простой двухполюсной подсетью является подсеть с множеством узлов F, и и полюсами и и /. [c.108]

Когда по матрице достижимости будут просмотрены все нары узлов и выделены все возможные двухполюсные подсети, в блоке 8 алгоритма осуществляется коррекция описания исходной сети и повторяется свертывание сети и т. д. [c.109]

Идентификация рециркуляционных последовательностей блоков — матрица достижимости [c.42]

Если в сети С отсутствуют контуры, то простые пути и маршруты в ней совпадают и пол5гченная матрица достижимости Ч отражает число простых путей длиною от 1 до г включительно, связывающих м-тый и у-тый узлы. При наличии же в сети контуров элементы матрицы достижимости, полученной по соотношениям (1У.42) и (1У.43), характеризуют не только простые пути, но и маршруты, проходящие через узлы сети неоднократно. Маршрут, проходящий через контур, теряет свою однозначность, его длина становится равной [c.105]

Справочник химика 21

Химия и химическая технология