Page 22 - 4517

ЛАБОРАТОРНА РОБОТА № 7
ПРИКЛАД СИНТЕЗУ НАЙКОРОТШОГО ЛАНЦЮГА
(6 год.)

Мета: одержання практичних навичок синтезу
найкоротшого ланцюга.

Теоретичні відомості

Допустимо, що є мережа, у якій кожній дузі A поставлена
ij
у відповідність довжина, або віддаль d . Довжиною ланцюга
ij
називається сума довжин d , яка взята за всіма дугами цього
ij
ланцюга. Необхідно знайти ланцюг мінімальної довжини із
заданого вузла N у заданий вузол N . Будемо вважати, що
s f
d  0. Якщо деяка пара вузлів N і N не зв’язана
ij i j
безпосередньо дугою, то вважаємо d   . Відмітимо, що
ij
величини d не обов’язково повинні задовольняти умові
ij
симетричності d  d .
ij ji
Теоретичні відомості викладені в конспекті лекцій [1] на
сторінках 125 – 145.

Завдання до лабораторної роботи

Для мережі, яка показана на рисунку А.1, знайти
найкоротші ланцюги між всіма парами вузлів. Довжини дуг
вказані у табл. А.1.
Приклад графа мережа з вказаними пропускними
можливостями дуг для варіанту № 33 зображено на рисунку 7.1

Індивідуальні завдання

Індивідуальне завдання представлене в додатку А.
20