АЛГОРИТМИ ПОШУКУ ШЛЯХІВ В МЕРЕЖАХ

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

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

2.1Алгоритми пошуку безлічі шляхів

2.1.1. Матричні алгоритми пошуку безлічі шляхів

Розкладання булевого визначника структурної матриці В. Якщо в мережі є можливість передачі інформації з вузла i у вузол j (по прямих каналах або через проміжні вузли), то говорять, що існує зв'язок від i до j . Для здійснення зв'язку повинен існувати відповідний шлях або шляхи.

Введемо наступні позначення: µ_ij - шлях з вузла i у вузол j (з вершини i у вершину j графа); m_ij - безліч шляхів з i в j .

Шлях µ_ij - це впорядкований набір ребер, його складових.

Довжина шляху µ_ij - L_ij- це сума довжин l_xy ребер, його складових:

L_ij =

Ранг шляху R _ij -число ребер, утворюючих шлях.

Для графа, зображеного на рис. 2.1, для шляху µ₁₄ = а₁₂, а₂₅, а₅₃, а₃₄ ранг R₁₄ = 4, для шляху µ₁₄ = а₁₄ ранг R₁₄= 1, для шляху µ_{14 =} а₁₂, а₂₃, а₃₄ ранг R₁₄ = 3.

Структурна матриця графа рис. 2.1, представлена в табл. 2.1, може розглядатися як булева матриця, оскільки її елементами є булеві змінні. Дійсно, будь-який елемент матриці В - це змінна, її інверсія, константи 0 або 1. Таким чином, шлях як послідовність ребер може бути представлений кон’юнкцією (логічним множенням) ребер, його складових.

Таблиця 2.1 – Структурна матриця графа, зображеного на рис. 2.1

В =

Рисунок 2.1 – Зображення графа структурної матриці табл. 2.1

Розглянуті шляхи µ₁₄ запишемо у формі

µ₁₄ = agfc, µ₁₄ =h, µ₁₄ =abc .

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

Так, в даному прикладі

m₁₄ = agfc + h + abc .

Тут для позначення логічного множення і складання застосовуються символи алгебраїчного множення і складання . Окрім вказаних символів, використовуються також символи: ٨ - для позначення кон'юнкції, ٧ - для позначення диз'юнкції.

Безліч шляхів m_ij може бути одержане розкладанням визначника матриці В, з якої заздалегідь викреслюється стовбець з номером i і рядок з номером j ,тобто [7]:

(2.1)

Розкладання визначника матриці В _іj проведено по рядку з номером k. Розкладання (2.1) можна проводити по будь-якому рядку (стовбцю). Тут В _іj - матриця, одержана з початкової структурної матриці після викреслювання i -го стовпця і j -го рядка.

У стовпцях кожної вершини графа записані ребра, що в неї входять; у рядках кожної вершини графа записані ребра, які виходять з вершини.

Викресливши стовпець i і рядок j, ми тим самим виключимо ті ребра, які не можуть утворювати шляхів множини m_ij. |В_kl |- визначник, одержаний з det В _іj після викреслювання k -го рядка і 1-го стовпця.

Розкладання визначника(2.1) слід проводити за відомими правилами лінійної алгебри, проте операції алгебраїчного множення і складання замінюються на операції логічного множення і складання, відповідно.

При перетворенні матриці і визначників слід використовувати основні правила і закони булевої алгебри :

1) 1 + а = 1; 1·а = а;

2) 0 + а= а; 0·а = 0;

3) а + а = 1; а · а = 0;

4) а + а = а; а·а = а - закон повторення;

5) а + ab = а - закон поглинання;

6) (а + х) · (а + у) = а + ху - розподільний закон.

При розкладанні булевих визначників необхідно також користуватися наступними правилами:

1) визначник, що має одиницю в кожному рядку і стовпці, тотожно рівний одиниці;

2) якщо який-небудь рядок або стовпець складається з нулів, то визначник тотожно рівний нулю;

3) якщо перед визначником записаний множник «а», то всі елементи «а» у визначнику можна замінити на «1», а всі елементи «а» у визначнику можна замінити на «0»;

4) якщо у визначнику поміняти місцями два рядки або два стовпці або виробити його транспонування, то значення визначника не зміниться.

Розглянемо отримання безлічі шляхів m₁₄ з матриці В (див. табл 2.1):

m₁₄ = det В _іj =

Розкладання визначника проведемо по стовпцю з номером 4:

m₁₄ =

Упорядкуємо одержані шляхи по рангу, врахувавши послідовність ребер в шляхах. Одержимо:

m₁₄ =

Той же результат одержимо, розклавши визначника, наприклад, по першому рядку:

m₁₄ =

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

Тут n - число вершин графа, R_max - максимально можливий ранг шляхів в графі. R_max = n - 1 у разі, коли який-небудь шлях проходить через всі вершини графа.

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

В⁽²⁾ = В⁽¹⁾ · В⁽¹⁾ ,

В⁽³⁾ = В⁽²⁾ · В⁽¹⁾ і т.д.

Елемент матриці-співмножників С = A· D в лінійній алгебрі одержують відповідно до виразу

(2.2)

n- загальний розмір матриць А і D (число стовпців матриці А і рядків матриці D, у разі зведення квадратної матриці B в степінь n- число вершин).

Оскільки матриця В - булева, зведення її в степінь здійснюється з використанням законів і тотожностей булевої алгебри. Крім того, у виразі (2.2) операції алгебраїчного множення і складання замінюються на операції логічного множення і складання, відповідно. При зведенні матриці В в степінь q кожен елемент b_ij ^(q) матриці В^(q) обчислюється за наступними правилами:

1)елементи і-го рядка матриці В^(q-1) логічно умножаються на відповідні елементи j-го стовпця матриці В⁽¹⁾;

2) одержані логічні співмножники логічно складаються, утворюючи шукане значення елементу b_ij ^(q) . Якщо при зведенні в деяку степінь q виявиться, В^(q) = В^(q-1) обчислення слід припинити. При цьому В^(q) = В^(q-1) = В^(Rmax) .

Покажемо процес отримання матриці B⁽²⁾ для графа рис. 2.1, матриця В якого представлена в табл. 2.1.

Для отримання елементу необхідно використовувати елементи першого рядка і другого стовпця матриці В⁽¹⁾ :

= − I рядок В⁽¹⁾ ─ II рядок В⁽¹⁾

Аналогічно одержимо решту елементів матриці B⁽²⁾ :

і т.д.

Одержані результати зведемо в матрицю B⁽²⁾ (табл 2.2)

Таблиця 2.2 – Матриця B⁽²⁾

З порівняння B⁽²⁾ іB⁽¹⁾ (табл.2.2 і 2.1) витікає, що одержана матриця B⁽²⁾ не є результуючою, оскільки B⁽²⁾ ≠B⁽¹⁾ і процес обчислень слід продовжувати, а саме:

1. Обчислити B⁽³⁾ =B⁽²⁾ · B⁽¹⁾.

2. Якщо B⁽³⁾= B⁽²⁾ ,то B⁽³⁾= В^(Rmax) , результат одержаний.

Якщо B⁽³⁾ ≠B⁽²⁾ , продовжити обчислення, тобто одержати B⁽⁴⁾

Оскільки R_max = 4 для даного графа мережі, матриця буде результуючою у будь-якому випадку, навіть якщо B⁽⁴⁾ ≠B⁽³⁾.

У одержаній результуючій матриці В^(Rmax) ,як указувалося раніше, кожен елемент b_ij^(Rmax) = m_ij ,тобто визначає множену всіх шляхів з вершини i у вершину j.

Так,

і т.д.

2.1.2. Мережевий алгоритм пошуку безлічі шляхів

Мережеві методи визначення множини шляхів між заданими вузлами мережі являються графічним еквівалентом матричних методів

Визначення безлічі шляхів засноване на побудові дерева шляхів з фіксованої вершини-витоку (коріння дерева ) у всю решту вершин-стоків графа. Мережеві методи визначення множини шляхів між заданими вузлами мережі являються графічним еквівалентом матричних методів.

Для побудови дерева шляхів необхідно перш за все відзначити «яруси» дерева. На ярусі R = 0 поміщається вершина-виток - «корінь» дерева. На ярусі R = 1 розташовуються вершини, суміжні вершині-витоку, тобто вершини, шляхи в які з вершини-витоку мають ранг, рівний одиниці .На ярусі R = 2 розташовуються вершини, суміжні вершинам, розташованим на ярусі R = 1, і т.д.

При записі вершин на ярус R = 2 і подальші яруси необхідно стежити за тим, щоб шляхи рангів, що утворюються, 2, 3 і т.д. були простими (самонепересічними), тобто щоб жодна вершина в шляху не повторювалася більше одного разу.

Максимальне значення ярусу (рангу шляху) R_maх = n-1 (n -число вершин графа).

Дерево шляхів містить всі шляхи з фіксованої вершини-витоку у всю решту вершин. При цьому на ярусі 1 містяться всі шляхи першого рангу, на ярусі 2 – всі шляхи другого рангу і т.д.

Таким чином, на деякому k-му ярусі міститься інформація про всі шляхи k -гo рангу з фіксованої вершини-витоку графа у всю решту вершин.

Для графа рис. 2.1 побудуємо дерево шляхів з вершини 1. Дана вершина є корінням дерева і поміщається на нульовий ярус .Значение рангу шляху тут R = 0. На перший ярус R= 1 поміщаються вершини 2, 4, 5, що мають безпосередній зв'язок з вершиною 1. Далі на другий ярус від вершини 2 поміщаються вершини, пов'язані з вершиною 2, а саме 3 і 5. Вершина 1 виключається з розгляду, оскільки шлях у вершину 2 пройшов через вершину 1.

Від вершини 4 на другий ярус записуються вершини 3 і 5, від вершини 5-вершини 4 і 3. Аналогічно записуються вершини на решту ярусів дерева.

Побудоване дерево для вершини-витоку 1 представлене на рис. 2.2. Як видно, в дереві є три шляхи першого рангу (R=1): а, h, e; шість шляхів другого рангу (R = 2):

ab, ag, hс, hd, e , e , на третьому ярусі (R = 3) записані шляхи третього рангу: ab , abc, ag , ag , hc , hсf, hd , e , e c, e . Нарешті, шляхичетвертого рангу (R = 4): ab , abсd, ag с, ag , hс g, hd b, e .

Звичайно, з дерева можна одержати безліч шляхів з фіксованої вершини в будь-яку вершину графа послідовним переглядом ярусів дерева. Так,