Побудува мережі мінімальної довжини для графа
Побудова мережі мінімальної довжини для графа: побудова матриці суміжності, вибір початкової вершини та пошук мінімального елементу та відстані до ізольованих вершин, повтор ітерацій поки вони є. Зображення графічного рішення мережі мінімальної довжини.
| Рубрика | Коммуникации, связь, цифровые приборы и радиоэлектроника |
| Вид | задача |
| Язык | украинский |
| Дата добавления | 08.08.2009 |
| Размер файла | 26,6 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Задача
Побудувати мережу мінімальної довжини для графа, що зображений на малюнку.
Крок 1:
Будуємо матрицю суміжності
|
1 |
2 |
3 |
4 |
5 |
6 |
||
|
1 |
- |
2 |
- |
7 |
- |
6 |
|
|
2 |
2 |
- |
4 |
- |
1 |
- |
|
|
3 |
- |
4 |
- |
3 |
- |
5 |
|
|
4 |
7 |
- |
3 |
- |
1 |
- |
|
|
5 |
- |
1 |
- |
1 |
- |
3 |
|
|
6 |
6 |
- |
5 |
- |
3 |
- |
Крок 2:
Вибираємо за початкову вершину х1. Для цієї вершини знаходимо найближчу сусідню вершину. З таблиці суміжності вибираємо рядок, що відповідає х1.
|
1 |
2 |
3 |
4 |
5 |
6 |
||
|
1 |
- |
2 |
- |
7 |
- |
6 |
Серед елементів а1j знаходимо мінімальний. Таким буде а12= 2. Це означає, що х1 та х2 утворюють фрагмент (х1,х2).
Крок 3:
Щоб розширити отриманий на кроці 2 фрагмент необхідно знайти відстань до всіх ізольованих вершин 3, 4, 5, 6. Використовуючи матрицю суміжностей заповнюємо таблицю.
|
3 |
4 |
5 |
6 |
||
|
1 |
- |
7 |
- |
6 |
|
|
2 |
4 |
- |
1 |
- |
|
|
Найкоротший шлях |
1 |
Мінімальний елемент таблиці вказує на те, яку вершину слід приєднати до фрагмента. Вершину х5 слід сполучити ланкою з вершиною х2, оскільки мінімальний елемент стоїть в рядку, що відповідає вершині х2.
Крок 4:
Оцінки ще є ізольовані вершини, то переходимо до наступної ітерації
|
3 |
4 |
6 |
||
|
1 |
- |
7 |
6 |
|
|
2 |
4 |
- |
- |
|
|
5 |
- |
1 |
3 |
|
|
Найкоротший шлях |
1 |
Сполучаємо ланкою вершину х4 з х5.
Крок 5:
|
3 |
6 |
||
|
1 |
- |
6 |
|
|
2 |
4 |
- |
|
|
5 |
- |
3 |
|
|
4 |
3 |
- |
|
|
Найкоротший шлях |
3 |
Сполучаємо ланками вершини х3 з х4 і х6 з х5.
Крок 6:
|
Ітерація |
Ланка найкоротшої мережі |
Довжина ланки |
|
|
1 |
1-2 |
2 |
|
|
2 |
2-5 |
1 |
|
|
3 |
5-4 |
1 |
|
|
4 |
4-3 |
3 |
|
|
5 |
5-6 |
3 |
|
|
Довжина найкоротшої мережі |
10 |
Крок 7:
Оцінки ізольованих вершин більше не залишилось. То алгоритм роботу закінчив. Мережа мінімальної довжини зображена на малюнку.
Подобные документы
Вибір топології проектованої первинної мережі та типу оптичного волокна. Розрахунок довжини ділянок регенерації й кількості регенераторів. Синхронізація мережі SDH з чарунковою топологією. Дослідження режимів її роботи в нормальному і в аварійному станах.
курсовая работа [1,3 M], добавлен 16.07.2015Вибір розміру мережі та її структури. Огляд і аналіз комп’ютерних мереж, використаних в курсовій роботі. Побудова мережі і розрахунок вартості. Недоліки мережі, побудованої на основі заданої модифікації мережної технології, рекомендації по їх усуненню.
курсовая работа [1,7 M], добавлен 20.09.2012Еволюція телекомунікаційних послуг. Побудова телефонної мережі загального користування. Цифровізація телефонної мережі. Етапи розвитку телекомунікаційних послуг і мереж. Необхідність модернізації обладнання та програмного забезпечення на всіх АТС мережі.
реферат [236,4 K], добавлен 14.01.2011Створення IN на базі станції АХЕ-10 фірми Ericsson. Інтелектуальні мережі компанії Huawei Technologies TELLIN. Російський варіант IN - АПКУ. Побудова IN на базі обладнання фірми Siemens. Етапи нарощування ресурсів мережі. Основні переваги IN TELLIN.
реферат [1,0 M], добавлен 16.01.2011Техніко-економічне обґрунтування побудови мережі LTE. Розрахунок кількості потенційних абонентів, вибір оптичного кабелю та обладнання транспортної мережі. Аналіз радіо покриття. Частотно-територіальний поділ і ситуаційне розташування ENB на території.
курсовая работа [3,9 M], добавлен 05.12.2013Побудова комп'ютерної мережі за визначеними параметрами, додаткове включення мережного принтера. Характеристика сервера, комутатора, їх підключення до робочої станції. Фізична топологія мережі; статистика завантаженості; звіт з компонентів і витрат.
контрольная работа [1,6 M], добавлен 16.02.2011Побудова мультисервісної мережі з одночасною реконструкцію телефонної мережі на базі обладнання ЦСК SI2000 і ПКСК SI3000. Визначення кількості обладнання територіально-розподілених об’єктів ЦСК, вузла доступу, комутації MSAN. Розробка функціональних схем.
курсовая работа [427,2 K], добавлен 18.03.2014Варіанти організації доступу абонентів до послуг інтелектуальної мережі IN каналами базової телефонної мережі через вузли комутації послуг – SSP. Оптимальний вибір рівня розміщення та кількості SSP. Основні критерії вибору точки та способу доступу.
контрольная работа [217,6 K], добавлен 16.01.2011Види пристроїв синхронізації. Принципи фізичної реалізації стандартів частоти. Параметри сигналів на виходах пристроїв синхронізації. Дослідження зв'язку фази і частоти сигналу при дрейфі частоти. Вплив просковзування на якість передачі інформації.
курсовая работа [898,0 K], добавлен 01.10.2015- Структуровані кабельні системи. Фізична структуризація локальної мережі. Повторювачі і концентратори
Стандартизація структурованих кабельних систем. Структура та топологія кабельних систем. Архітектура ієрархічної зірки. Перелік основного обладнання магістральної підсистеми. Розрахунок довжини кабельної системи. Розрахунок системи електроживлення.
курсовая работа [1,4 M], добавлен 08.10.2014
