Студопедия
Новини освіти і науки:
МАРК РЕГНЕРУС ДОСЛІДЖЕННЯ: Наскільки відрізняються діти, які виросли в одностатевих союзах


РЕЗОЛЮЦІЯ: Громадського обговорення навчальної програми статевого виховання


ЧОМУ ФОНД ОЛЕНИ ПІНЧУК І МОЗ УКРАЇНИ ПРОПАГУЮТЬ "СЕКСУАЛЬНІ УРОКИ"


ЕКЗИСТЕНЦІЙНО-ПСИХОЛОГІЧНІ ОСНОВИ ПОРУШЕННЯ СТАТЕВОЇ ІДЕНТИЧНОСТІ ПІДЛІТКІВ


Батьківський, громадянський рух в Україні закликає МОН зупинити тотальну сексуалізацію дітей і підлітків


Відкрите звернення Міністру освіти й науки України - Гриневич Лілії Михайлівні


Представництво українського жіноцтва в ООН: низький рівень культури спілкування в соціальних мережах


Гендерна антидискримінаційна експертиза може зробити нас моральними рабами


ЛІВИЙ МАРКСИЗМ У НОВИХ ПІДРУЧНИКАХ ДЛЯ ШКОЛЯРІВ


ВІДКРИТА ЗАЯВА на підтримку позиції Ганни Турчинової та права кожної людини на свободу думки, світогляду та вираження поглядів



Мінімізація мережі

Задача мінімізації мережі полягає в знаходженні ребер, які з’єднують всі вузли мережі і мають мінімальну сумарну довжину. Розв’язок задачі не повинен містити циклів. Він представляє собою мінімальне дерево. Його знаходження починаємо з будь-якого вузла, який з’єднуємо з найближчим вузлом мережі. З’єднані два вузли утворюють зв’язну множину, а всі решта – незв’язну. Тепер в незв’язній множині вибираємо вузол, який знаходиться найближче до одного з них і з’єднуємо їх. Процес повторюємо доти, доки у зв’язну множину не попадуть всі вузли мережі.

Приклад 2.1. Телевізійна фірма планує створити кабельну мережу для обслуговування п’яти районів-новобудов. Числа на ребрах вказують довжину кабеля, який з’єднує відповідні вузли. Вузол 1 – це телевізійний центр, а решта (2–6) відповідають п’яти новобудовам. Відсутність ребра між двома вузлами означає, що з’єднати ці вузли неможливо ( рис. 2.5).

 
 

 

 


Рис. 2.5

 

 

Розв’язок. Зобразимо на рис 2.6 поетапну побудову мінімальної мережі:

1. 2.

 

 

3. 4.

 

 

5.

 

Рис.2.6.

Вузол 3 можна зв’язувати як з вузлом 1 так і з вузлом 4. Оскільки всі вузли зв’язані, то мінімальна довжина кабелю дорівнює 1+3+4+5+3=16.

 


Читайте також:

  1. Абонентський стик ISDN мережі
  2. Автоматичне налагодження їх індуктивності на ємність мережі для забезпе1
  3. Аналіз вузьких місць у мережі
  4. Багатокрокове прогнозування з перенавчанням нейромережі на кожному кроці прогнозу
  5. Базові топології мережі
  6. Бальна оцінка стану контактної мережі
  7. Бездротові мережі
  8. Взаємодія контактної мережі і струмоприймача
  9. Вибір кількості та розміщення складської мережі
  10. Вибір раціональної напруги розподільчої мережі підприємства.
  11. Використання мережі Інтернет в інформаційних війнах
  12. Використання мережі Інтернет екстремістами і терористами




Переглядів: 720

<== попередня сторінка | наступна сторінка ==>
Матричне представлення графів | Задача про найкоротший шлях

Не знайшли потрібну інформацію? Скористайтесь пошуком google:

  

© studopedia.com.ua При використанні або копіюванні матеріалів пряме посилання на сайт обов'язкове.


Генерація сторінки за: 0.002 сек.