Алгоритм пошуку у глибину

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

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

Якісний опис алгоритму пошуку в глибину

В процессі пошуку в глибину вершинам графа G послідовно привласнюються нові номери (ПГ-номери) від 1 до n, а ребра одержують позначки двох класів: «пряме ребро» і «зворотне ребро». Пошук починається з довільної вершини , якій привласнюється ПГ-номер 1: ПГ. Далі обирається будь-яке інцидентне до ребро позначається позначкою «пряме ребро» і вершині привласнюється ПГ-номер 2. Наступний (третій) крок пошуку починається у вершині , в якій ПГ, і підкоряється рекурентній процедурі, яку ми опишемо для довільного кроку . Припустимо, -й крок віконаний і деяка вершина одержала ПГ-номер ПГ.

Можливі дві ситуації:

1. У вершині існує інцидентне непозначене ребро . Якщо вершина вже має ПГ-номер, то ребро одержує позначку «зворотне», і продовжується пошук непозначеного ребра, що інцидентне вершині . Якщо ж вершина не має раніше привласненого ПГ-номеру, то їй провласнюється черговий ПГ-номер ПГ, ребро одержує позначку «пряме», і пошук переміщується у вершину .

2. Всі ребра, що інцидентні вершині , позначені на попередніх кроках. Тоді пошук повертається у вершину , що має попередній ПГ-номер ПГ.

Пошук у глибину закінчується, коли всі ребра графа виявляються позначеними.

Позначимо множина прямих ребер, множина зворотних ребер. Із процедури пошуку в глибину виходить твердження.

Твердження.Якщо – зв’язний граф, то підграф є остовне дерево в G , а підграф є додатковим до дереваT . А дерево T є орієнтованим кореневим з коренем .

Приклад.Розглянемонаступный граф.

Тому що , то кількість ребер у повинна дорівнювати .

Крок 1.Нехай , .

Крок 2., обираємо інцідентне ребро , , , ребро – пряме.

Крок 3., інцідентне непозначене ребро . , не має ПГ-позначки, отже , ребро – пряме, , .

Крок 4., інцідентне непозначене ребро . , не має ПГ-позначки, отже , ребро – пряме, , .

Крок 5., інцідентне непозначене ребро . , не має ПГ-позначки, отже , ребро – пряме, , .

Крок 6., –непозначене ребро. , має ПГ-номер, отже ребро –зворотнє. –непозначене ребро. , має ПГ-номер, отже ребро –зворотнє. не має непозначених ребер, .

Крок 7., не має непозначених ребер, .

Крок 8. , –непозначене ребро. , не має ПГ-позначки, отже , ребро – пряме, , алгоритм завершено.

–остовне дерево (кістяк) графу.

5. Задача про мінімальне з'єднання

Теорема Келі становить інтерес у зв'язку з наступною практичною задачею.

Нехай для деякої множини міст відома вартість будівлі дороги між будь-якими двома містами . Яка повинна бути мережа доріг між містами, що входять в , щоб по ній можна було проїхати з будь-якого міста в будь-яке місто й щоб вартість цієї мережі було мінімальною?

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

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

Як показує теорема Келі, рішення цієї задачі простим перебором вимагає надзвичайно більших обчислень навіть при невеликому числі вершин (при , існує дерев). Однак для її рішення є наступний ефективний алгоритм, запропонований чеським математиком Борувкой.

Крок 1. Вибирається ребро з найменшою мірою. Позначимо через остовний підграф .

Крок -й, . Нехай на -м кроці побудований остовний підграф ,який не містить циклів й містить компонент зв’язності. Тоді , . Якщо , то ; по теоремі 4 до графа можна приєднати ребро так, щоб отриманий граф не містив циклів (тому що цикломатичне число при цьому не збільшується).

На кроці ми будуємо граф , вибираючи так, щоб міра була мінімальною. Якщо таких ребер декілька, то вибираємо в якості будь-яке з них. Якщо ж , те, і граф є деревом. Це дерево називають звичайно економічним.

Твердження. Міра економічного дерева мінімальна.

Доказ. Допустимо, що наше припущення невірно. Нехай , відмінне від дерево мінімальної міри , що є кістяком графа ; – ребро з найменшим номером з , що не втримується в. Серед таких дерев виберемо те, у якому число максимально.

У дереві найдеться ланцюг , що з'єднує й (див. мал. 4.30);

Рис. 4.30

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

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