Автор работы: Пользователь скрыл имя, 14 Января 2011 в 21:44, контрольная работа
Структура информационно-вычислительной сети – это топология и совокупность пунктов (терминалов, узлов коммутации и т.п.) и соединяющих их линий или каналов связи. Она показывает потенциальные возможности сети по доставке информации между отдельными пунктами этой сети. В качестве модели структуры сети наиболее часто используются графовые модели. Граф имеет множество вершин, соответствующих пунктам сети, и множество дуг (ребер) – линий связи между пунктами.
Задание. 3
Теоретическая часть 4
Решение контрольной работы. 6
Во втором случае, если для некоторых клеток (i,j) таблицы имеет место неравенство:
lj – li > lij; i=1,...,n;
j=1,...,n,
то значения lj и li могут быть уменьшены.
Если
справедливо (3), тогда исправим значение lj0,
пересчитав его по формуле: l¢j0=li0+li0,j0.
Знаком “+” будем отмечать неравенство удовлетворяющее (2), а знаком “–” – неравенство удовлетворяющее (3).
l2 – l1 = 1,90– 0 = 1,90 ≤ l1,2 = 1,90 (+)
l3 – l1 = 16 – 0 = 16 ≤ l1,3 = 16 (+)
l4 – l2 = 2,11 – 1,9 = 0,21 ≤ l2,4 = 0,21 (+)
l4 – l3 = 2,11 – 16 = - 13,89 ≤ l3,4 = 1,7 (+)
l5 – l2 = 5,1 – 1,9 = 3,2 ≤ l2,5 = 3,2 (+)
l5 – l3 = 5,1 – 16 = - 10,9 ≤ l3,5 = 50 (+)
l6 – l4 = 8,1 – 2,11 = 5,99 ≤ l4,6 = 20 (+)
l6 – l5 = 8,1 – 5,1 = 3 ≤
l5,6 = 3 (+)
Расчет
показал, что полученные l1, l2, …, ln удовлетворяют
условиям оптимальности по неравенству lj
– li £
lij; lij¹0; j=1,2,...,n; j=1,2,...,n,
(2)
Этап 4.
Нахождение кратчайшего пути. Здесь очевидно,
что r1 = n, а значит lr1 = ln.
lrj,ri
= lrj
– lri,
где lrj,ri (i=2..n) берется из таблицы, причем lri выбирается так, чтобы выполнилось равенство (5). Таким образом, определим ri. Далее продолжим ту же операцию, но будем считать, последней не Pn, а Pr1. Будем продолжать до тех пор, пока rn не станет равной 1.
Таким
образом, кратчайший маршрут проходит
через Pr1,Pr2,...,Prn, а длина
маршрута Lmin=lr2,r1+lr3,r2+...+lrn,rn-
Здесь очевидно, что r1=n, а значит . Отсюда, r1=6, а значит . По формуле найдем остальные и определим кратчайшее расстояние.
При r1=6 имеем:
Анализируя это равенство, приходим к выводу, что оно выполняется при r2=5. На самом деле:
Таким образом, кратчайший маршрут равен:
Решение задачи, полученное методом Форда, и оптимальное значение маршрута прокладки вычислительной сети полностью совпали, они равны 8,1.