Лекція 3.2. Алгоритми визначення двохзв’язних компонент і їх оцінка

У цій лекції ми розглянемо застосування пошуку в глибину до виділення двохзв’язних компонентів графа. Тут справа обстоїть не так просто, як у попередній задачі. Звичайно, можна було б, видаляючи по черзі вершини графа і щораз виділяючи зв'язкові компоненти, знайти його точки зчленування і блоки. Такий підхід, однак, приводить до алгоритму складності принаймні O(|G||EG|). Використання більш глибоких властивостей ПГ дозволяє одержати лінійний по складності алгоритм розв’язку цієї задачі.

1. Дослідження властивостей алгоритму пошуку в глибину. Надалі зручно використовувати наступні терміни. Нехай D = (V, A) – орієнтоване дерево, x, y V. Назвемо x батьком вершини y, а y – сином вершини x, якщо дуга (x, y) належить А. Будемо говорити, що вершини x і y порівнянні, якщо при цьому y досяжна з x. Якщо при цьому y досяжна з x, то x – предок вершини y, а y – нащадок вершини x. Підграф графа D, породжений безліччю, що складається з вершини y і всіх її нащадків, будемо позначати через Dy і називати піддеревом з коренем y.

Нехай у графі G пророблений пошук у глибину з вершини v0 і отримане остовне глибинне дерево Т і безліч компонентів.

Теорема 74.1. Якщо дуга (x, y) належить У, то x є нащадком вершини y у Т.

Доказ. Треба довести, що вершина x належить піддереву Ту. Припустимо противне. Відповідно до твердження 73.2 вершина x одержує свій Пг-номер пізніше, ніж y. Тому присвоєння вершині x Пг-номера відбудеться не раніш, ніж будуть відвідані усі вершини дерева Ту і відбудеться повернення у вершину s = F(y). Але повернення в s не може відбутися перш, ніж усі вершини безлічі Ny одержать Пг-номера. Оскільки xNy і ПГ-номера до цього моменту не має, то одержуємо протиріччя.

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

Теорема 74.2. Вершина v0 є точкою зчленування графа G тоді і только тоді, коли вона має не менш двох синів.

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

Нехай тепер s1, s2, ...,sk – сини вершини v0. Розглянемо піддерева.

Б езперечно, що

Для доказу незв’язаності графу G - v0 досить показати, що в цьому графі немає ребер, що зв'язують вершини різних Тsi. Але це відразу випливає з твердження 74.1. 

Будемо говорити, что x – власний предок (нащадок) вершини y, якщо x – предок (нащадок) y і x  y.

Теорема 74.3. Вершина v  v0 дявляется точкою зчленування графа G тоді і только тоді, коли для де-якого сина s цієї вершини не існує дуги (x, y)B такої,що x – нащадок (не обов'язково власний) вершини s а y – власний предок вершини v.

Доказ. Нехай v – точка зчленування графа G і G1 , G2 , ...,Gm, m  2, – блоки цього графа, що містять вершину v. Нехай, далі, v = F(v), тобто v – батько вершини v. Не втрачаючи спільності вважаємо, что вершина v міститься в блоці G1. Кожний з інших блоків повинний, очевидно, містити хоча б одну вершину, що є сином вершини v. Нехай, наприклад, s – син вершини v і s ( G2. Якщо тепер допустити існування «зворотнього» ребра ab ( тобто дуги (a, b) ( У) такої, що а – нащадок s, а b – власний предок вершини v, то прийдемо до існування в графі G простого циклу, що містить вершини s і v( належать одному блоку. Одержали протиріччя.

Доведемо тепер другу частину твердження. Нехай вершина s є сином вершини v, для якого виконується умова, що фігурує у форуліровці твердження. Ця умова разом із твердженням 74.1 означає, що якщо ab – «зворотнє» ребро й а ( Тs, те або b ( Тs, або b = v. Останнє означає, що всі ребра графа G, що зв'язують вершини безлічі Vтs, інцідентні вершині v, тобто v – крапка зчленування графа G. 

C1

v0

C2

x

c3

c4

y

Мал. 74.1

Перейдемо тепер безпосередньо до розробки алгоритму виділення блоків графа.

2. Алгоритм виділення блоків графа. Щоб усвідомити схему застосування ПГ до розв’язку цієї задачі, звернемося до прикладу. На мал. 74.1. зображений граф «з точністю до блоків». ПГ починається у вершині v0. Після декількох кроків прийдемо в одну з крапок зчленування графа, наприклад, у з2. Нехай, далі, обирається і позначається як «пряме» ребро c2x блоків У4. Після цього подальша робота ПГ аж до повернення в з2 відбувається точно так, ніби було v0 = з2 і блоків У1, У2, У3 у графі G не було б зовсім. Тому повернення в з2 відбудеться пізніше, ніж повернення в з3 і з4 з висячих блоків У5, У6, У7. Ці розгляди приводять до наступного важливого висновку. Найперше повернення в точку зчленування відбудеться відразу ж після завершення обходу всіх ребер деякого висячого блоку Вк. Це ж справедливо і стосовно подальшого поводження ПГ у графі, який отримано із графа G видаленням блоку Вк.

Покажемо, як використовувати сказане вище в припущенні, якщо ми маємо спосіб, що дозволяє при кожнім поверненні з вершини v у F(v) визначати, ли є F(v) точкою зчленування. З цією метою заведемо стек S, у який будемо заносити всяке ребро графа G відразу після одержання їм позначки “пряме” чи “зворотне”. Таким чином, усі ребра додаються в кінець списку S. Нехай у нашому прикладі повернення з вершини y у c4 (див. рис 74.1 ) є самим першим поверненням у крапку зчленування. Тоді до моменту повернення в c4 ребра блоку В6 будуть займати всі t останніх місць у стеці S, де t - число ребер цього блоку. Важливо при цьому, що ребро з4y займає перше серед t зазначених місць. Це дозволяє, переглядаючи стек S зправа ліворуч, виділити (тобто , наприклад, перемістити в окремий список) усі ребра блоку В6 . Потім ці ребра виводять з S.

Отже, з огляду на сказане, необхідно вміти в процесі ПГ швидко визначати повернення у вершину, що є точкою зчленування. Твердження 74.2 і 74.3 дають відповідні критерії, і нам треба их “алгоритмизивати”. З цією метою для кожної вершини v є VG визначимо безліч P(v). У цю безліч включимо вершину v і кожного її предка w, для якого існує “зворотнє” ребро xw таке, что х – нащадок вершини v в остовному глибинному дереві Т. Іншими словами, безліч P(v) складається з усіх предків вершини v, яких можна досягти з v, проходячи спочатку декілька (можливо, жодної) дуг дерева Т, а потім одну дугу безлічі В.

Уведемо тепер функцію l(v), v є VG, припускаючи l(v) = min ПГ(х) , х є P(v). Наприклад у графі на мал. 73.1 l(1)=1, l(2)=1, l(3)=1, l(4)=3, l(5)=1, l(6)=3, l(7)=3.

Використовуючи функцію l(v), сформулюємо твердження 74.3 у наступному вигляді, більш зручному для організації обчислень.

Теорема 74.4. Вершина v <> v0 є точкою зчленування графа G тоді і только тоді, коли існує такий син s цієї вершини, что l(s)>= ПГ(v).

Обчислити значення л(в) неважко, якщо відомі значення функції л для всіх синів вершини в. Саме, якщо S1, S2, ... , Sm – сини вершини в, то має місце формула

l(v) = min {{ l(S1) , l(S2) , ... , l(Sm), ПГ(v)} U {ПГ(w)| (v,w) є B }} (1)

Справедливість цього співвідношення стає очевидною якщо помітити наступне: Безліч передків вершини v, досяжних з неї з використанням дуг дерева Т та не більш однієї дуги з У, складається з предків v, досяжних такім самим шляхом з вершин S1, S2, ... , Sm, і безлічі вершин, до яких ведуть зворотні ребра від вершини v.

Використовуючи співвідношення (1) , функцію l можна обчислювати разом з виконанням звичайних операцій пошуку в глибину. При першому відвідуванні вершини v разом із присвоєнням ПГ – номера думаємо l(v) = ПГ(v). Надалі це значення коректується відповідно до формули (1) у такий спосіб. Усякий раз, коли відбувається повернення у вершину v з деякого її сина s, думаємо l(v):= min {l(s),l(v)}. Крім того, коли деяке ребро vw позначається як “зворотнє”, думаємо l(v):=min {l(v), ПГ(w)}. До моменту повернення з v у вершину х = F(v) буде обчислене щире значення l(v) , що надалі використовується для коректування l(х). Істотно, що кожне з цих коректувань вимагає тільки ПРО(1) додатковий час. Тому ПГ разом з обчисленням функції l як і раніше буде виконуватися за час ПРО(|EG|+|G|).

Ще одна добавка до “стандартного” пошуку в глибину пов'язана з точками зчленування. Для виявлення точки зчленування досить після кожного повернення у вершину в з деякого її сина порівняти величини l(s) і ПГ(v). Якщо виявиться, что l(s) >= ПГ(v), то всі ребра стека S, починаючи з останнього і кінчаючи sv, віддаляються з цього списку. Вилучені ребра складають один із блоків графа G. Відповідно до твердження 74.4 нерівність l(s) >= ПГ(v) означає, что або вершина v – крапка зчленування, або v=v0 і v не є точкою зчленування. Помітимо, что другий випадок не вимагає особливого розгляду. У цьому випадку вилучені зі стека S ребра відповідають єдиному блоку графа, що містить v0. І, нарешті, остання деталь. Виділення блоку графа G ми розуміємо як видалення всіх ребер цього блоку зі стека S. Можна вважати, что одночасно з видаленням з S кожне таке ребро заноситься в деякий інший список, причому безліч ребер різних блоків розділені в цьому списку, наприклад, символом 0. Процедура побудови цього нового списку очевидна, і щоб не захаращувати опису алгоритму, ми не приводимо її в явному виді.

Порівняння l(s) із ПГ(v) виробляється |G| - 1 разів, і, отже, сумарний час, витрачений на виконання порівнянь, складає O(|G|). Кожне ребро графа один раз включається в стек S і один раз виключається з нього. Тому вся робота, зв'язана зі зміною S, виконується за час O(|EG|). Таким чином, пошук у глибину разом з виділенням блоків буде виконуватися за час O(|EG|+|G|).

Алгоритм A2 пошуки в глибину з виділенням двусвязных компонент.

1. ПГ(v0):=1, l(v0):=1, S:= , F(v0):=0, T:= , B:= , k:=1, p:=1, Q(1):=v0.

2. v:=Q(p).

3. Переглядаючи список NV знайти таку вершину w, что ребро vw не позначене, і перейти до п.4. Якщо таких вершин ні, то перейти до п.5.

4. Якщо вершина w имееет ПГ- номер, то помістити ребро vw как «зворотне», занести ребро в стек S, l(v):=min{l(v),ПГ(w)} [ виконане коректування l(v)]. Перейти до п.3 і продовжити перегляд списку NV. Інакше ребро vw позначити як «пряме», k:=k+1, ПГ(w):=k, l(w):=k, F(w):=v, p:=p+1, Q(p):=w. Перейти до п.2.

5. p:=p-1. Якщо p=0, то кінець. Інакше перейти до п.6.

6. Нехай x=F(v). Якщо l(v)>=ПГ(x), то перейти до п.7. Інакше l(x):=min{l(x),l(v)} [виконане коректування l(x)] і перейти до п.2.

7. Видалити зі стека S усі ребра аж до xv [вилучені ребра составляютблок графа G] Перейти до п.2

Приклад. На мал. 74.2 зображений граф G і приведені списки суміжності его вершин. Цей граф має чотири блоки В1, У2, У3, У4 і дві крапки зчленування d і x. Пошук у глибину починається з вершини a, тобто v0=a. На мал. 74.3 відбита ситуація, що склалася безпосередньо перед виділенням блоку B4. До цього моменту шість ребер позначені як «прямые» і одне как «зворотне». Прямі ребра проведені жирними лініями, а зворотне – пунктирної. Тим і іншим додана відповідна орієнтація. Позначені ребра розташовані в стеці S у тім порядку, у якому вони одержували позначки. Пари чисел (,), приписана вершині v, має наступний сенс: =ПГ(v), а  - значення l(v), обчислене до розглянутого моменту.

Після того, як ребро tx одержало пометко «зворотне», відбулося повернення у вершину z. При цьому порівняння величин ПГ(z)=6 і l(t)=5 показало, что вершина z не є точкою зчленування. Далі при поверненні з вершини z у x виявляється, что l(z) = 5 = ПГ(x). Отже, усі ребра від tx до xz у стеці S складають блок графа G. Ці ребра –tx, tz, xz – віддаляються з S, і тим самим виділений блок B4.

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

Виділення останнього блоку, т.е видалення его ребер зі стека S, відбудеться при поверненні у вершину v0=a, для якої ПГ(a)=1=l(c). Таким чином, на вершину v0=a алгоритм «реагує» точно так само, як на крапку зчленування.

На закінчення відзначимо, что пошук у глибину виявляється корисним і при відшуканні 3-зв'язних компонентів графа. Відомий заснований на пошуку в глибину алгоритм, що вирішує цю задачу за час O(|EG+|G|).

Лекція 3.1. Мінімальний кістяк

Задача про мінімальний кістяк складається у відшуканні кістяка мінімальної ваги у зваженому графі (G,w). Вона вважається однією із самих «легких» оптимізаційних задач на графах. Розв’язок цієї задачі можна одержати за допомогою «жадібного» алгоритму, якщо вказати процедуру, що за будь-якою аціклічесною безліччю ребер X EG і ребру e  EG визначає, чи містить безліч ребер Xe цикл графа G. Як таку процедуру можна використовувати, наприклад, пошук у глибину, оскільки виявлення циклу в безлічі Xe, де e=ab, рівнозначно відшуканню (a,b) – ланцюга в породженому підграфі G(X). У процесі роботи «жадібного» алгоритму ця процедура виконується не більше |E| раз, і, отже, витрати часу складуть O(|EG|*|G|). Для упорядкування безлічі EG за незменшуванностю ваги відомі алгоритми складності O(|EG|*log|EG|). Таким чином, навіть нехітра реалізація “жадібної” стратегії пошуку мінімального кістяка приводить (незалежно від способу завдання графа G) , до поліноміального алгоритму. З цього погляду задача про мінімальний кістяк дійсно є легкою.

Ми зараз розглянемо два алгоритми розв’язку цієї задачі, що мають кращі оцінки швидкодії.

1. Розробка й оцінка алгоритму визначення мінімального кістяка.

Нехай T = {(V1,T1), (V2,T2), ..., (Vk,Tk) } – кістяковий ліс зваженого графа G, Vi, Ti -безлічі вершин ребер i – й компоненти лісу T, w(x,y) – вага ребра xy графа G. Обидва алгоритми побудови мінімального кістяка спираються на наступну просту теорему.

Теорема 75.1. Нехай ребро ab має мінімальну вагу серед усіх ребер, y якому рівно один кінець міститься в VT1. Тоді серед кістяків графа G, що містять T  ab, знайдеться такий, вага якого не більш ваги будь-якого кістяка, що містить T.

Доказ. Нехай T ’ – довільний кістяк графа G, що містить Т і не утримуючий ребра ab. Додамо це ребро до Т ’. Отриманий граф буде містити цикл S (теорема 13.1). Цей цикл включає ребро ab і принаймні ще одне ребро a’b’, у якого рівно один кінець міститься в V1 . За умовою w(a,b) <= w(а',b’). Отже,

w(T’ + ab -а'b’) = w(T’)+w(ab)-w(a’b’)<=w(T’).

C іншої сторони, граф Т’ + ab – a’b’ є кістяком графа G, що містить Т  ab. 

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

Теорема відразу підказує наступну стратегію побудови мінімального кістяка. На першому кроці розглянемо кістяковий ліс T¹ з n=|G| компонентами. Кожен його компонент складається з однієї вершини, тобто V_i¹ = {vi} . Цей ліс, очевидно, міститься в будь-якому кістяку графа G. Серед ребер, инцідентних v1 , виберемо ребро мінімальної ваги v1vk1 і приєднаємо його до Т¹ . Відповідно до теореми 75.1 існує мінімальний кістяк, що містить ліс Т² = Т¹ {v₁v_k1}, у якого компонента (V₁²,T₁²) містить дві вершини v₁ і v_k1 і ребро v₁v_k1 , а інші компоненты одновершинні. На наступному кроці буде обране і додано до Т² ребро мінімальної ваги серед ребер, що з'єднують {v₁v_k1} з VG \ {v₁v_k1} і т.д.

Отже, стратегія побудови мінімального кістяка зовсім ясна: на кожнім кроці приєднується ребро, мінімальне по вазі серед ребер, що з'єднують уже побудований фрагмент мінімального кістяка з вершинами, ще не включеними у фрагмент. Нам залишається тільки подбати про ощадливу реалізацію кроків цього процесу. З цією метою зв'яжемо з кожною вершиною xVG дві мітки (x) і (x), зміст яких полягає в наступному. Нехай пророблено k кроків і (V₁^k,T₁^k ) – фрагмент мінімального кістяка, побудований до цього моменту, тобто ця компонента лісу, до якої на попередніх кроках приєднувалися ребра мимнимальної ваги. Тоді

(x) = min w(x,v) =w(x,v*), (x) = v*

v  V₁^k

Таким чином, (x) – вага мінімального по вазі ребра, що з'єднує вершину x з побудованим фрагментом мінімального кістяка, а (x) – ім'я другої вершини цього ребра. Метки (x) і (x) дозволяють швидко знаходити на кожнім кроці ребро мінімальної ваги. Крім того, після приєднання чергової вершини v до фрагмента мітки легко відрегувати. Для этого досить порівняти «старе» значення (x) з w(v,x) і вибрати з них менше в якості «нового» значення (x).

В описі алгоритму, що приводиться нижче, побудови мінімального кістяка крім ((x) і ((x) використані наступні позначення: VT, ET - безлічі вершин і ребер споруджуваного фрагмента мінмального кістяка; Nx - оточення вершини x; |G| = n. Граф G заданий матрицею ваг.

Алгоритм A3 побудови мінімального кістяка.

1. Покласти ET:=, VT:={a}, де a – будь-яка вершина з VG. Кожній вершині xa, приписати мітки (x) = w(x,a), якщо xN_a і (x) = , якщо xN_a , (x) = a.

2. [відшукання вершини, «найближчої» до фрагмента]. Вибрати вершину v*  VG\VT

(v*) = min (v).

v*  VG\VT

3. [збільшення фрагмента]. Нехай v’ = (v*). Змінити VT і ET, думаючи VT:=VT  {v*}, ET:=ET  v’v*.

4. Якщо |VT| = n, то кінець. Ребра, що знаходяться в безлічі ET, складають мінімальний кістяк.

5. Для кожної вершини v N_v*  (VG\VT) змінити мітки в такий спосіб. Якщо (v)>w(v*,v), то (v):=w(v*,v), (v):=v*. Якщо ж (v)<=w(v*,v), то мітку вершини v не змінювати. Перейти до п.2.

Теорема 75.2. Алгоритм A3 будує мінімальний кістяк за час O(|G|²).

Доказ. Тому що всякий раз до ET додається ребро, один кінець якого належить VT, а інший ні, граф T=(VT,ET) на кожнім кроці є деревом. Після завершення роботи алгоритму це дерево буде кістяковим, оскільки алгоритм припиняє роботу тільки якщо VT=VG.

Доведемо мінімальність кістяка Т. Для этого досить довести, що після k – го (k=1..n-1) виконання п.3. алгоритму граф Т^k = (VТ^k, EТ^k) міститься в деякому мінімальному кістяку. Доводити будемо індукцією по k. При k=1 наше твердження безпосереднє випливає з теореми 75.1. Припустимо, что воно справедливо для де-якого k>1, т.ч. граф Т^k , побудований у результаті k виконань п.3, міститься в деякому мінімальному кістяку. З огляду на правило вибору ребра е для приєднання до Т^k , застосуємо теорему 75.1. Одержимо, що граф Т^k+1 = Т^k  е, побудований у результаті (k+1) – го виконання п.3, також міститься в деякому мінімальному кістяку.

З'ясуємо тепер швидкодію алгоритму. Однократне виконання п.2 вимагає не більше O(|G|). Стільки ж часу досить для відновлення міток у п.5, а п.3 і п.4 виконуються за час O(1). Оскільки кожний із пп. 2-5 виконується n-1 раз, то оцінка трудомісткості алгоритму O(|G|²).

Приклад 1. На мал. 75.1 зображені граф G і послідовність Tⁱ (i=1..n-1) фрагментів мінімального кістяка, що виходять після кожної ітерації алгоритму. Числа, приписані ребрам графа G, означають ваги цих ребер. Кожній вершині x , що ще не ввійшла в Tⁱ , приписана пара чисел [(x),(x)], якими вона позначена в результаті i – го виконання п.5 алгоритму.

Якщо граф G заданий матрицею ваг, то всякий алгоритм побудови мінімального кістяка в такому графі буде мати складність не менш чим O(|G|²) , оскільки він, відповідно до зауваження 1, повинний переглядати всі елементи матриці ваг. Отже, у цій ситуації алгоритм A3 має незменшувану один по одному трудомісткість. Якщо ж граф G заданий списком ребер або списками суміжності і |EG| істотно менше чем |G|², то швидкодія алгоритму A3 далеко від оптимального. Іншими словами, алгоритм A3 недостатньо ефективний у застосуванні до «рідкіх» графів, тобто до графів, слабко насиченними ребрами.

2 Алгоритм побудови мінімального кістяка, орієнтований на роботу з «рідкими» графами. Цей алгоритм (алгоритм A4 ), як і попередній, спирається на теорему 75.1, однак більш повно використовує надані нею можливості. Саме, якщо в алгоритмі A3 ребро приєднується всякий раз до одній і тієї ж компоненту лісу, то в алгоритмі A4 ребра приєднуються до кожного компонента.

Нехай T = {(V1,T1), (V2,T2), ..., (Vp,Tp) } – кістяковий ліс графа G. Назвемо ребро ab мінімальним по вазі для компонента (Vl,Tl), 1<=l<=p, якщо a Vl, b Vl, і w(a,b) = min w(x,y), x Vl, y Vl . Будемо говорити, що M=M(T) множин--безліч мінімальних по вазі ребер для лісу Т, якщо для каждого l=1..p безліч М містить хоча б одне мінімальне по вазі ребро для коипоненти (Vl,Tl) і, крім того, М – мінімальне по включенню безліч, що володіє цією властивістю.

Теорема 75.3. Якщо М = безліч мінімальних по вазі ребер для T = {(V1,T1), (V2,T2), ..., (Vp,Tp) } то граф T’=T+M не містить циклів.

Доказ. Доводимо від противного. Припустимо, что T містить цикл S, що не втрачаючи спільності будемо вважати простим. Нехай a1b1, a2,b2, ...,al,bl – ребра безлічі S  M, виписані в тій послідовності, як вони розташовані в циклі S. Цієї послідовності відповідає послідовність компонентів (V_k1, T_k1), (V_k2, T_k2), ... , (V_kl, T_kl) лісу Т, така, що a1 V_{k1 ,} b1 V_{k2 ,} a2 V_k2, b2 V_k3 , ... , al V_{kl ,} bl V_kl виберемо серед ребер a_ib_i (i=1..l) максимальне по вазі. Нехай це буде ребро a₁b₁. Ясно, що a₁b₁ є мінімальним по вазі ребром принаймні для одного з компонентів (V_k1, T_k1), чи (V_k2, T_k2). Не втрачаючи спільності вважаємо, що ребро a₁b₁ мінімальне по вазі для (V_kl, T_kl). Тоді w(a₁ ,b₁) = w(a_l ,b_l) і, отже, безліч М\ a₁ ,b₁ містить хоча б одне мінімальне по вазі ребро для кожного компонента лісу Т. Останнє суперечить мінімальності безлічі М. 

Перейдемо тепер до викладу алгоритму A4. Цей алгоритм, також, як і A3 , на першій ітерації має справу з кістяковим лісом графа G, що складає з n=|G| одновершинних компонентів. Кожна ітерація алгоритму складається в наступному. Спочатку будується безліч М мінімальних по вазі ребер для лісу Т, отриманого в результаті попередніх ітерацій. (Важливо відзначити, что зробити це можна за один перегляд елементів безлічі EG.) Потім за допомогою пошуку в глибину виділяються зв'язні компоненти графу T’=T+M, що відповідно до твердження 75.2 є лісом. Після цього починається наступна ітерація з новим лісом T’, що має очевидно, менше компонент, ніж T.

В описі алгоритму А4, що приводиться нижче, використовуються наступні позначення. Ребра графа G містяться в списку E, т.ч. E(і) - пари номерів кінцевих вершин i-го ребра. Список W містить ваги ребер графу G, тобто W(і) – вага i-го ребра. Щоб щораз будувати безліч мінімальних по вазі ребер для поточного лісу за один перегляд списку E, використовуються списки HMP, BMP і КОМП:

HMP(i) - номер мінімального по вазі ребра для i-й компоненты поточного лісу;

BMP(i) - вага цього ребра;

КОМП(i) – номер компонента поточного лісу, що містить вершину j.

Нехай, далі, ET – безліч ребер поточного лісу T, a p – число его компонентів; E1 – безліч мінімальних по вазі ребер для поточного лісу Т.

Алгоритм A4 побудови мінімального кістяка.

1. ЕТ:=(, КОМП(і):=і, BMP(і):=( для і=1..n, p:=n. [Пп. 2-8 – побудова безлічі Е1 мінімальних по вазі ребер для лісу T] .

2. k:=1.

3. Нехай Е(k) = uv; і:=КОМП(u), j:=КОМП(v) [і і j – номера компонентів лісу, що містять вершини u і v відповідно].

4. Якщо і(j, то перейти до п.5, інакше перейти до п.7.

5. Якщо w(u,v)=W(k)<BMP(j), то BMP(j):=w(u,v), HMP(j):=k.

6. Якщо w(u,v) = W(k)<BMP(і), то BMP(і):=w(u,v), HMP(і):=k.

7. Якщо k=|EG|, то перейти до п.8. Інакше k:=k+1 і перейти до п.3. [ДО моменту виконання п.8. перші p елементів HMP містять номера ребер, що складають безліч мінімальних по вазі ребер для T.]

8. Переглянути перші p елементів масиву HMP і сформувати безліч Е1 мінімальних по вазі ребер для лісу Т.

9. ЕТ:=ET ( E1 [ЕТ – безліч ребер «нового» лісу Т'].

10. Виділити за допомогою алгоритму пошуку в глибину зв'язні компоненты графы Т’=T+E1 [обновлений список КОМП, отримане нове значення р].

11. Якщо р=1, то кінець [ЕТ - безліч ребер мінімального кістяка]. Інакше перейти до п.2.

Теорема 75.4. Алгоритм A4 будує мінімальний кістяк за час O(|EG|log|G|).

Доказ. Неважко переконатися, что після кожного виконання п.8 безліч Е1 є безліччю мінімальних по вазі ребер для лісу Т, розглянутого в цей момент. Тому відповідно до твердження 75.2 граф Т’ = T+E1 знову є кістяковим лісом. Це означає, что алгоритм будує деякий кістяк графа G. Мінімальність цього кістяка доводиться за допомогою теореми 75.1 точно так само, як при обґрунтуванні попереднього алгоритму. З'ясуємо тепер швидкодію алгоритму A4. Для однократного виконання кожного з пп. 3-6 досить часу ПРО(1) і, отже, побудова Е1 здійснюється за час ПРО(|EG|). Таких самих витрат досить і для однократного виконання пп. 8-11. Таким чином, витрати на перехід від Т к Т' = T +E1 (тобто на виконання однієї ітерації) складають ПРО(|EG|) операцій. Оцінимо тепер число ітерацій алгоритму. Оскільки одне ребро може бути мінімальним по вазі не більш ніж для двох компонентів лісу Т, то на кожній ітерації |E1| >= p(T)/2. А тому що T+E1 – ліс, то p(T+E1)<=p(T)/2, тобто на кожній ітерації число компонент зменшується принаймні вдвічі. Це означає, что число ітерацій алгоритму не перевершує log|G|, отже, він будує мінімальний кістяк за час O(|EG|log|G|).

Мал. 75.2

Приклад 2. Застосуємо алгоритм A4 до графу, зображеному на мал. 75.2 На першій ітерації буде знайдена безліч E1={a1a2, a1a3,a4a7,a5a8,a6a9,a9a10} мінімальних по вазі ребер для лісу, що має одновершинні компоненты. Кістякові ліси, отримані в результаті виконання 1-й, 2-ї, і 3-ї ітерацій, зображені на мал. 75.3. Останній з них є мінімальним кістяком.