Побудова маршрутних матриць

3.4.1 Вивчіть пункти п.п. 2.1, 2.3.5, 2.3.6 Ключових положень

 

3.4.2 Побудуйте маршрутні матриці для кожного вузла мережі (n=10), що забезпечують вибір основного напрямку, а також двох обхідних при упорядкуванні сполучних трактів від розгладуваного вузла до всієї решти вузлів.

Для основного напрямку (шляху першого вибору) необхідно використовувати найкоротші шляхи з вузла s (s=1,...,n) в інші пункти мережі. Для обхідних (шляхів другого і третього виборів) – найкоротші за транзитами шляху за максимально припустимої транзитності Т₀ = 2. За наявності декількох шляхів однакової транзитності превагу слід надавати шляху, найкоротшому за довжиною.

Для визначення шляхів, найкоротших за довжиною, за вихідну матрицю довжин ліній, що зв'язують узловие пункти мережі, скористайтеся матрицею вагів, дістаною при виконанні завдання 3.1, а для віднайдення шляхів мінімальної транзитности – матриці суміжності.

 

3.4.3 Методичні вказівки

Маршрутні матриці зберігаються на кожному ВКi мережі і призначені для визначення напрямку вихідної лінії зв'язку (каналу зв'язку) при проключениі тракту передавання інформаційного повідомлення від вихідного пункту до пункту призначення. На конкретному ВКs за наявності технічних можливостей комутаційного устаткування можна передбачити вибір додаткових напрямків (обхідних) у випадку зайнятості напрямку першого вибору. Порядок вибору напрямків визначається маршрутною матрицею, кількість і нумерація рядків якої відповідає числу p шляхів і призначеного порядку їхнього заняття, а число стовпчиків – номерам пунктів призначення.(рис. 3.1).

 

       1  2  …  j       i   …  n

1				j	I
2				r	J

…………………………………………………......

 

p

l

L

 

                           Рисунок 3.1

Елементом mij маршрутної матриці для ВКs є номер вузла, суміжного до ВКs в шляху відповідного вибору з ВКs у пункт призначення J.

 

3.4.4 У пояснювальній записці наведіть загальну постановку задачі (вербальну модель), результати розв´язання й відповідні до них пояснення.

 

3.4.5 Дайте письмову відповідь на наступні ключові запитання:

· До якого класу задач належить задача побудови маршрутних матриць?

· Що називається путхм у мережі, довжиною шляху, транзитністю шляху, найкоротшим шляхом?

· Наведіть практичні ситуації, у яких виникає задача визначення найкоротшого шляху?

· На чому базується алгоритм Дейкстри, пошуку найкоротших шляхів?

· Якого виду позначки використовуються при роботі алгоритму Декстри?

· Чи можна за допомогою алгоритму Дейкстри відшукати множину шляхів найкоротших за транзитністю? Які вихідні дані для цього потрібні?  

· Яким методом можна дістати множину шляхів заданої транзитності?

· В чому полягає ідея методу побудови ярусного дерева?      

Оцінка пропускної здатності мережі поміж парою пунктів

 

3.5.1 Вивчіть пункти 2.1, 2.3.7 Ключових положень

 

3.5.2 Визначте пропускну здатність поміж парою пунктів мережі, номера яких відповідають двом останнім цифрам номера студентського квитка.

Дано: мережа, що зв'язує, що містить n=10 пунктів і матриця пропускних спроможностей ліній зв'язку. За останню вкористайте матрицю вагів, дістаною при виконанні завдання 3.1, вважаючи, що значення елементів цієї матриці відповідають пропускним здатностям ліній.

 

3.5.3 В пояснювальній записці наведіть загальну постановку задачі, розв´язок її результат і пояснення до нього.

 

3.5.4 Дайте письмову відповідь на такі ключові питання:

· Що називається потоком із джерела в стік?

· Дайте визначення перерізу мережі?

· Який переріз називається мінімальним?

· Сформулюйте теорему про максимальний потік і мінімальний переріз.

· Яка мережа називається двополюсною? Багатополюсною? Однопродуктовою? Багатопродуктовою?

· В чому полягає відмінність багатополюсної мережі від багатопродуктової?

· В чому полягає основна ідея оцінки пропускної здатності мережі?