Метод исключения промежуточных узлов

Если нас интересуют условия работоспособности системы по схеме «вход-выход», то имеет смысл исключить внутренние узлы и тем самым уменьшить порядок матрицы узловых соединений. Будем через обозначать матрицу с одним исключенным узлом, через - с двумя и т.д. Понижать порядок будем до матрицы , где N – количество узлов в графе: - которая не содержит лишней информации.

Понижать порядок будем согласно простому правилу: при исключении s-ого узла графа в матрице узловых связей вычеркиваются s-ая строка и s-ый столбец и каждый элемент сокращенной матрицы равняется . Второе слагаемой логической суммы указывает на появление новой дуги от i-ого узла к j-ому через узел s.

Рассмотрим этот метод на предыдущем примере. Удалим второй узел, т.е. s=2. .

В матрице бывший третий узел занял место удаленного второго. Чтобы завершить вывод ФРС ещё раз вычеркнет второй столбец и вторую строку:

Как мы видим результат совпал с вычислениями по предыдущему методу, но количество вычислений было сильно сокращено.

Дата добавления: 2014-01-03