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

Кільцеві топології фізичних зв'язків, як випливає з попередніх розділів, часто використовують для побудови сегментів телекомунікаційних мереж, особливо транспортних мереж.

У термінах теорії графів кільцеву топологію визначають як цикл або контур.

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

Пошук циклу (контуру) є доцільний лише в «надлишковому» відносно деревоподібного графа, тобто в графі, кількість ребер якого є більшою від числа n його вершин. Власне кажучи, в задачах синтезу в такому сенсі вихідний граф допустимих зв'язків між вершинами завжди є надлишковим. У такому графі можна утворити n! циклів, які містять дуги (ребра) різної ваги, серед яких можна відшукати цикл найменшої сумарної ваги дуг (ребер). Розв’язавши подібну задачу можна, наприклад, оптимізувати витрати на побудову транспортної мережі.

Задача про знаходження циклу найменшої довжини в теорії графів є відомою як «задача комівояжера». Вона може бути формалізована наступним чином.

Дано граф G(N,V), вершини якого – це міста в зоні обслуговування комівояжера, а дуги – відповідно зв'язки між парами міст. Маршрутом комівояжера називається контур, який містить всі вершини графа G. Необхідно знайти маршрут найменшої довжини.

Розв’язком цієї задачі є гамільтонов контур в графі G(N,V), який відповідає маршруту найменшої довжини. Назва «гамільтонов контур» походить від прізвища ірландського математика Вільяма Гамільтона, який у 1859 року вперше розпочав дослідження цих задач.

О з н а ч е н н я. Контур, у якому розміщено кожну вершину графа G(N, V) тільки один раз, називають гамільтоновим контуром (або гамільтоновим циклом).

Задачу про знаходження гамільтонового контуру можна розв’язати за допомогою точного методу.

Пронумеруємо n міст цілими числами від 1 до n. За базовим містом закріпимо номер n. Звернемо увагу на те, що тур комівояжера однозначно відповідає перестановці цілих чисел 1, 2,..., (n - 1). Базове місто під номером n при цьому постійно займає останню позицію та в процесах перестановки не бере участь. Кожній перестановці можна поставити у відповідність деяке число, яке визначає довжину маршруту комівояжера як суму довжин ребер циклу, який з'єднує всі n вершин графа.

Утворивши всі перестановки з (n-1) чисел і отримавши довжини маршрутів, кількість яких визначається як (n-1)!, необхідно знайти маршрут найменшої довжини.

Не важко переконатися, що ефективність обчислювальної процедури для вирішення цього завдання точним методом різко зменшується зі збільшенням числа n вершин графа. Як доводить практика, ефективність можна вважати задовільною, якщо кількість вершин у графі не більша від 30. У зв'язку з цим для розв’язування задачі про знаходження гамільтонового контуру часто використовують евристичні алгоритми.

Наближений алгоритм для розв’язання задачі про комівояжера можна отримати, наприклад, використовуючи евристики: – «на кожному кроці рухаємося тільки до найближчого пункту». Використання такої евристики дає змогу одержати прийнятне рішення за час, необхідний для побудови тільки одного контуру. Переконайтесь в цьому, спробуйте знайти цикл найменшої довжини для вихідного повноз’язного графа, який використано для ілюстрації роботи алгоритма Пріма.

7. Математичні моделі типових задач аналізу телекомунікаційних мереж. Методи й алгоритми їх розв’язання.

Задачі аналізу телекомунікаційної мережі, як уже зазначено вище, ґрунтуються на синтезованої топології фізичних зв'язків, і найчастіше зводяться до з’ясування оптимальних топологій логічних зв'язків. Це стосується побудови оптимальних планів розподілу інформаційних потоків у мережі, вибору найкращих маршрутів передавання інформаційних повідомлень, підвищення надійності та живучості мережі та ін.

Задачі синтезу та аналізу дуже пов'язані між собою, оскільки можливості оптимізації топології логічних зв'язків обмежуються топологією фізичних зв'язків у мережі. Якщо неможливо виконати умови оптимальної побудови топології логічних зв'язків, доводиться повертатися до синтезу інших топологій фізичних зв'язків. У результаті побудова телекомунікаційної мережі та її сегментів перетворюється на ітераційний процес.

Нижче розглядаємо окремі класичні задачі аналізу зв'язувальних мереж, що засновані на графових моделях.