Примеры сетевых топологий


Преобразования и сокращения - часть 2


Чтобы суммировать применение этих сокращений, предположим, что e и f соответствуют ребрам, которые соединены последовательно или параллельно, и пусть g является ребром, которое замещает эти два ребра в последовательном или параллельном сокращении.

Кратчайший путь: Для последовательного сокращения Lg является сверткой Le и Lf. Для параллельного сокращения Lg является минимумом Le и Lf

Максимальный поток: Для последовательного сокращения Сg является минимумом Сe и Сf. Для параллельного сокращения Сg является сверткой Сe и Сf.

Работоспособность сети PERT: Для последовательного сокращения Тg является сверткой Тe и Тf. Для параллельного сокращения Тg является максимумом Тe и Тf.

Во-первых, предположим, что Н является односвязной субсетью графа G c r подключенными точками, и пусть ФН и

являются системными оценочными функциями для соответствующей проблемы, где субсети Н и G\Н содержат терминалы s,v и v и t, соответственно. Тогда системная оценочная функция ФG удовлетворяет следующим условиям

Кратчайший путь и работоспособность сети PERT: ФG является сверткой ФН и

.

Максимальный поток: ФG является минимумом ФН и

.

Во-вторых, пусть Н является двухсвязной субсетью G с точками подключения x и y, и пусть Фху и Фух являются соответствующими системными оценочными функциями для субграфа Н, где ориентация направлена от х к у и от у к х, соответственно. Тогда функция надежности системы G является той же, что и полученная при подмене субграфа Н двумя ребрами (х,у) и (у,х), имеющими случайные параметры связи, распределенные согласно Фху и Фух, соответственно.




Начало  Назад  Вперед



Книжный магазин