Неорієнтований граф G = (V, Е) складається з нескінченної множини вершин V і множини ребер Е. На відміну від орієнтованого графа, тут кожне ребро (v. w) відповідає неврегульованій парі вершин1: якщо (v, w) — неорієнтоване ребро, то (v, w) = (w,v). Далі неорієнтований граф ми називатимемо просто графом.
Графи широко використовуються в різних областях науки і техніки для моделювання симетричних відносин між об'єктами. Об'єкти відповідають вершинам графа, а ребра — відношенням між об'єктами. У цьому розділі будуть описані різні структури даних, які застосовні для представлення графів. Ми також розглянемо алгоритми рішення трьох типових задач, що виникають при роботі з графами, побудови мінімальних остовних дерев, визначення двозв’язних компонент і знаходження максимального попарного сполучення графа.
7.1. Основні визначення
Багато що з термінології орієнтованих графів застосовно до неорієнтованих граф. Наприклад, вершини v і w називаються суміжними, якщо існує ребро (v, w). Ми також говоритимемо, що ребро (v, w) інцидентно вершинам v і w.
Шляхом називається така послідовність вершин v1, v2, ..., vn, що для всіх і, 1 ≤ і < п, існують ребра (vi , vi+1). Шлях називається простим, якщо всі вершини шляху різні, за винятком, можливо, вершин v1 і vn . Довжина шляху рівна кількості ребер, що становлять шлях, тобто довжина рівна п - 1 для шляху з п вершин. Якщо для вершин v1 і vn  існує шлях v1, v2, ..., vn, то ці вершини називаються зв’язаними. Граф називається зв'язним, якщо в ньому будь-яка пара вершин зв'язана.
Нехай є граф G = {V, Е) з множиною вершин V і множиною ребер Е. Граф G' = (V`, Е') називається підграфом графа G, якщо
1.    множина V` є підмножиною множини V,
2.    множина Е' складається з ребер (v, w) множини Е таких, що обидві вершини v і w належать V`.
Якщо множина Е' складається зі всіх ребер (v, w) множини Е таких, що обидві вершини v і w належать V`, то в цьому випадку граф G' називається індукованим підграфом графа G.
Приклад 7.1. На мал. 7.1,а показаний граф G = (V, Е) з множиною вершин V = { а, b, c, d) і множиною дуг Е = {(а. b), (а, d), (b, с), (b, d), (с, d)}. Ha мал. 7.1,6 представлений один з його індукованих підграфів, заданий множиною вершин V` = { а, b, c) і який містить всі ребра, не інцидентні вершині d.
Зв'язковою компонентой графа G називається максимальний зв'язний індукований підграф графа G.
Приклад 7.2. Граф, показаний на мал. 7.1,а, є зв'язним графом і має тільки одну зв'язкову компоненту, а саме — самого себе. На мал. 7.2 представлений незв'язний граф, що складається з двох зв'язкових компонент.

Мал. 7.1. Граф і один з його підграфів

Мал. 7.2. Незв’язний граф
Циклом (простим) називається шлях (простий), довжиною не менше 3 від якої-небудь вершини до неї самої. Ми не вважаємо циклами шляхи завдовжки 0, завдовжки 1 (петля від вершини v до неї самої) і завдовжки 2 (шлях виду v, w, v ). Граф називається циклічним, якщо має хоч би один цикл. Зв'язний ациклічний граф, що є "деревом без кореня", називають вільним деревом. На мал. 7.2 показаний граф, що складається з двох зв'язкових компонент, кожна з яких є вільним деревом. Вільне дерево можна зробити "звичайним" деревом, якщо яку-небудь вершину призначити коренем, а всі ребра зорієнтувати в напрям від цього кореня.
Вільні дерева мають дві важливі властивості, які ми використовуватимемо в наступних розділах.
1.    Кожне вільне дерево з числом вершин n, n ≥1, має в точності п - 1 ребро.
2.    Якщо у вільне дерево додати нове ребро, то обов'язково вийде цикл.
Ми доведемо перше твердження методом індукції по п. Очевидно, що твердження справедливо для п = 1, оскільки в цьому випадку маємо тільки одну вершину і не маємо ребер. Нехай твердження 1 справедливо для вільного дерева з п - 1 вершиною. Розглянемо дерево G з n  вершинами.
Спочатку покажемо, що у вільному дереві існують вершини, що мають одне інцидентне ребро. Відмітимо, що G не містить ізольованих вершин (тобто вершин, що не мають інцидентних ребер), інакше граф G не був би зв'язним. Тепер створимо шлях від деякої вершини v1, слідуючи по довільному ребру, інцидентному вершині v1. На кожному кроці побудови цього шляху, досягнувши якої-небудь вершини, вибираємо інцидентне їй ребро, яке веде до вершини, що ще не брала участь у формуванні шляху. Нехай у такий спосіб побудований шлях v1, v2, ..., vx. Вершина vx буде суміжною або з однією вершиною vx-1, або ще з якою-небудь, що не входить в побудований шлях (інакше вийде цикл). У першому випадку одержуємо, що вершина vx, має тільки одне інцидентне їй ребро, і означає, наше твердження про те, що у вільному дереві існують вершини, що мають одне інцидентне ребро, буде доведено. У другому випадку позначимо через vx+1 вершину, суміжну з вершиною vx, і будуємо шлях v1, v2, ..., vx, , vx+1 . У цьому шляху всі вершини різні (інакше знову вийде цикл). Оскільки кількість вершин скінчена, то цей процес закінчиться за скінчене число кроків і ми знайдемо вершину, що має одне інцидентне ребро. Позначимо таку вершину через v, а інцидентне їй ребро — (v , w).
Тепер розглянемо граф G', одержаний в результаті видалення з графа G вершини v і ребра (v, w). Граф G' має п - 1 вершину, для нього виконується твердження 1 і тому він має п - 2 ребра. Але граф G має на одну вершину і на одне ребро більше, ніж граф G', тому для нього також виконується твердження 1. Отже, твердження 1 доведене.
Тепер ми легко доведемо твердження 2 про те, що додавання ребра у вільне дерево формує цикл. Застосуємо доказ від супротивного, тобто припустимо, що додавання ребра у вільне дерево не формує цикл. Отже, після додавання нового ребра ми одержали граф з п вершинами і п ребрами. Цей граф залишився зв'язним і, після нашого припущенню, ациклічним. Отже, цей граф — вільне дерево. Але у такому разі одержуємо суперечність з твердженням 1. Звідси витікає справедливість твердження 2.
Представлення неорієнтованих графів
Для представлення неорієнтованих графів можна застосовувати ті ж методи, що і для представлення орієнтованих графів, якщо неорієнтоване ребро між вершинами v і w розглядати як дві орієнтовані дуги від вершини v до вершини w і від вершини w до вершини v.
Приклад 7.3. На мал. 7.3 показані матриця суміжності і списки суміжності, що представляють граф з мал. 7.1,a.


а. Матриця суміжності

б. Списки суміжності
Мал. 7.3. Представлення неорієнтованого графа
Очевидно, що матриця суміжності для неорієнтованого графа симетрична. Відзначимо, що у разі представлення графа за допомогою списків суміжності для існуючого ребра (і, j) в списку суміжності вершини і присутня вершина  j, а в списку суміжності вершини  j — вершина і.
7.2. Остовні дерева мінімальної вартості
Нехай G = (V, Е) — зв'язний граф, в якому кожне ребро (v, w) помічене числом с(v, w), яке називається вартістю ребра. Остовним деревом графа G називається вільне дерево, що містить всі вершини V графа G. Вартість остовного дерева обчислюється як сума вартостей всіх ребер, що входять в це дерево. У цьому розділі ми розглянемо методи знаходження остовних дерев мінімальної вартості.
Приклад 7.4. На мал. 7.4 показані граф з поміченими ребрами і його остовне дерево мінімальної вартості.

Мал. 7.4. Граф і його остовне дерево
Типове застосування остовних дерев мінімальної вартості можна знайти при розробці комунікаційних мереж. Тут вершини графа представляють міста, ребра — можливі комунікаційні лінії між містами, а вартість ребер відповідає вартості комунікаційних ліній. В цьому випадку остовне дерево мінімальної вартості представляє комунікаційну мережу, яка об'єднує всі міста комунікаційними лініями мінімальної вартості.
Властивість остовних дерев мінімальної вартості
Існують різні методи побудови остовних дерев мінімальної вартості. Багато з них грунтуються на наступній властивості остовних дерев мінімальної вартості, яку скорочено називатимемо властивістю ОДМС. Нехай G = (V, Е) — зв'язний граф із заданою функцією вартості, визначеної на множині ребер. Позначимо через U підмножину множини вершин V. Якщо (и,v) — таке ребро найменшої вартості, що и є U і v є V \ U, тоді для графа G існує остовне дерево мінімальної вартості, що містить ребро (и, v).
Довести цю властивість неважко. Припустимо супротивне: існує остовне дерево для графа G, позначимо його Т = (V,Е'), що містить множину U і що не містить ребро (u,v), вартість якого менша за будь-яке остовне дерево для G, що містить ребро (и, v).
Оскільки дерево Т — вільне дерево, то з другої властивості вільних дерев виходить, що додавання ребра (и, v) до цього дерева приведе до утворення циклу. Цей цикл містить ребро (и, v) і міститиме інше ребро (и', v') таке, що и' є U і v' є  V\ U, як показано на мал. 7.5. Видалення ребра (и', v') приведе до розриву циклу і утворення остовного дерева, чия вартість буде не вища за вартість дерева Т, оскільки с(и, v)≤ с(u', v'). Ми дійшли суперечності з припущенням, що остовне дерево Т — це дерево мінімальної вартості.

Мал. 7.5. Цикл в остовному дереві
Алгоритм Пріма
Існують два популярні методи побудови остовного дерева мінімальної вартості для поміченого графа G = (V, Е), засновані на властивості ОДМС. Один такий метод відомий як алгоритм Пріма (Prim). У цьому алгоритмі будується множина вершин U, з якої "зростає" остовне дерево. Нехай V = {1, 2, ..., п}. Спочатку U = {1}. На кожному кроці алгоритму знаходиться ребро найменшої вартості (и, v) таке, що и є U і v є V \U, потім вершина v переноситься з множини V\U у множину U. Цей процес продовжується до тих пір, поки множина U не стане рівною множині V. Ескіз алгоритму показаний в лістингу 7.1, а процес побудови остовного дерева для графа з мал. 7.4,а — на мал. 7.6.
Лістинг 7.1. Алгоритм Пріма
procedure  Prim   (   G:   граф;  var  Т:  множина ребер   );
var
U:   множина  вершин;
и,   v:   вершина;
begin
Т:=  Ø;
U:={l};
while  U ≠V do begin
знаходження ребра   ( и,   v)   найменшої вартості і такого,
що и є U і v є   V\U;
Т:=   ТỤ  { (u,   v) };
U:=   U Ụ {v}
end
end;    {   Prim  }
Якщо ввести два масиви, то можна порівняно просто організувати на кожному кроці алгоритму вибір ребра з найменшою вартістю, що сполучає множину U і V \ U. Масив CLOSEST[i] для кожної вершини і з множини V\U містить вершину з U, з якою він сполучений ребром мінімальної вартості (це ребро вибирається серед ребер, інцидентних вершині і, і які ведуть в множину U. Інший масив LOWCOST[i] зберігає значення вартості ребра (i, CLOSEST[i]).
На кожному кроці алгоритму є видимим масив LOWCOST, знаходиться мінімальне значення LOWCOST[k]. Вершина до належить множині V \ U і сполучена ребром з вершиною з множини U. Потім виводиться на друк ребро (к, CLOSESТ[к]). Оскільки вершина k приєднується до множини U, то внаслідок цього змінюються масиви LOWCOST і CLOSEST. Програма на мові Pascal, реалізовуюча алгоритм Пріма, представлена в лістингу 7.2. На вхід програми поступає масив С розміру п х п, чиї елементи C[i, j] рівні вартості ребер (і, j). Якщо ребра (i, j) не існують, то елемент C[i, j] вважається рівним деякому достатньо великому числу.
Після знаходження чергової вершини k остовного дерева LOWCOST[k] лягає рівним infinity (нескінченність), дуже великому числу, такому, щоб ця вершина вже надалі не розглядалася. Значення числа infinity повинне бути більше вартості будь-якого ребра графа.

Мал. 7.6. Послідовність побудови остовного дерева за допомогою Пріма
Лістинг 7.2. Програма виконання алгоритму Пріма
procedure  Prim   (   С:   array[l..n,   l..n]   of real  );
{ Prim друкує ребра остовного дерева мінімальної вартості
для  графа з вершинами   {1,   ...,   п}  і матрицею вартості С}
var
LOWCOST:   аггау[1..п]   of  real;
CLOSEST:   array[1.. п ]   of  integer;
і,   j,   к,   miп:    integer;
{ і і j —  індекси. При перегляді масиву LOWCOST
к —  номер знайденої вершини, min  = LOWCOST[k]   }
begin
(1)    for і:= 2 to n do begin
{ спочатку в множині U  тільки вершина 1 }
(2)    LOWCOSTli]:=  C[1   і];
(3)    CLOSESTli]:=  1
end;
(4)        for i:=  2 to п do begin
{ пошук поза множиною U якнайкращої вершини к,   що має
інцидентне ребро, що закінчується в множині U }
(5)    min:=  L0WC0ST12];
(6)    к: =  2;
(7)    for j:=  3   to  n do
(8)    if LOWCOSTlj]   < min then begin
(9)    min:=  L0WCOSTlj];
(10)    k:=  j
end;
(11)    writeln (k,   CLOSESTik]);   { виведення ребра на друк  }
(12)    LONCOSTlk] :=  infinity;   {   к додається в множину U }
(13)    for j:= 2 to n do  {   коректування вартостей в U }
(14)         if   (C[к,  j)   < LOWCOSTlj])   and
( LOWCOSTlj]  < infinity)  then begin
(15)        L0NC0ST[j]:=   C[к, j];
(16)    CLOSEST[j]:= к
end
end
end;   {   Prim )
Час виконання алгоритму Пріма має порядок 0(п2), оскільки виконується п - 1 ітерація зовнішнього циклу рядків (4) - (16), а кожна ітерація цього циклу вимагає часу порядку О(п) для виконання внутрішніх циклів в рядках (7) - (10) і (13) - (16). Якщо значення п достатньо велике, то використання цього алгоритму не раціонально. Далі ми розглянемо алгоритм Крускала знаходження остовного дерева мінімальної вартості, який виконується за час порядку 0(е loge), де е — кількість ребер в даному графі. Якщо е значно менше за п, то алгоритм Крускала переважно, але якщо є близько до п2, рекомендується застосовувати алгоритм Пріма.
Алгоритм Крускала
Знову припустимо, що є зв'язний граф G = (V, Е) з множиною вершин V = {1, 2, ..., п} і функцією вартості с, визначеної на множині ребер Е. У алгоритмі Крускала (Kruskal) побудова остовного дерева мінімальної вартості для графа G починається з графа Т = (V,Ø), що складається тільки з п вершин графа G і що не має ребер. Таким чином, кожна вершина є зв'язною (з самою собою) компонентою. В процесі виконання алгоритму ми маємо набір зв'язних компонент, поступово об'єднуючи які формуємо остовне дерево.
При побудові зв'язних, що поступово зростають компонент по черзі перевіряються ребра з множини Е у порядку зростання їх вартості. Якщо чергове ребро зв'язує дві вершини з різних компонент, тоді воно додається в граф Т. Якщо це ребро зв'язує дві вершини з однієї компоненти, то воно відкидається, оскільки його додавання в зв'язну компоненту, що є вільним деревом, приведе до утворення циклу. Коли всі вершини графа G належатимуть одній компоненті, побудова остовного дерева мінімальної вартості Т для цього графа закінчується.
Приклад 7.5. Розглянемо помічений граф, представлений на мал. 7.4,а. Послідовності додавання ребер в дерево Т, що формується, показана на мал. 7.7. Ребра вартістю 1, 2, 3 і 4 розглянуті першими і всі включено в Т, оскільки їх додавання не приводить до циклів. Ребра (1, 4) і (3, 4) вартістю 5 не можна включити в Т, оскільки вони сполучають вершини однієї і тієї ж компоненти (мал. 7.7,г) і тому замикають цикл. Але ребро (2, 3), що залишилося, також вартістю 5 не створює цикл. Після включення цього ребра в Т формування остовного дерева завершується.

Мал.7.7. Послідовність формування остовного дерева мінімальної вартості за допомогою алгоритму Крускала
Цей алгоритм можна реалізувати, грунтуючись на множинах (для вершин і ребер) і операторах, розглянутих в розділах 4 і 5. Перш за все, необхідна множина ребер Е, до якої можна було б послідовно застосовувати оператора DELETEMIN для відбору ребер у порядку зростання їх вартості. Тому множину ребер доцільно представити у вигляді черги з пріоритетами і використовувати для неї частково впорядковане дерево в якості структури даних.
Необхідно також підтримувати набір С зв'язних компонент, для чого можна використовувати наступні оператори.
1.    Оператор MERGE(A, В, С) об'єднує компоненти А і В з набору С і результат об'єднання поміщає або в А, або у В.1
2.    Функція FIND(v, С) повертає ім'я тієї компоненти з набору С, яка містить вершину v.
3.    Оператор INITIAL(А, v, С) створює в наборі С нову компоненту з ім'ям А, що містить тільки одну вершину v.
Нагадаємо, що в розділі 5.5 для множин, що підтримують операторів MERGE і FIND, ми ввели абстрактний тип даних, який назвали MFSET. В ескізі програми (лістинг 7.3), що реалізує алгоритм Крускала, використовується цей тип даних.
Лістинг 7.3. Програма, що реалізує алгоритм Крускала    ;-
procedure Kruskal   ( V:   SET; Е:   SET; var Г: SET );
{ V -  множина вершин, Е і Т - множина дуг }
var
псотр:   integer; { поточна кількість компонент }
edges:   PRIORITYQUEUE;
{множина дуг, реалізована як черга з пріоритетами)
components:   MFSET;
{ множина V,   згруповане в множину компонент }
и,   v:   вершина;
е: ребро;
nextcomp:   integer; { ім'я (номер) нової компоненти }
исотр,   vcomp:   integer; { імена (номери) компонент }
begin
MAKENULL(Т) ; MAKENULL(edges) ;
nextcomp:=  0;
псотр:=  число елементів множини V;
for v є V do begin { ініціалізація компонент, що містять по одній вершині з V }
nextcomp:=  nextcomp  + 1;
INITIAL(nextcomp, v, components)
end;
for е є E do { ініціалізація черги з пріоритетами, що містить ребра } INSERT(e, edges);
while псотр  > 1 do begin ( розглядається наступне ребро }
е:=   DELETEMIN(edges);
нехай  е =   (u,   v);
ucomp:=  FIND(u,   components);
vcomp:=  FIND (v,   components);
if  uсоmр <>   vcomp then begin
{  ребро е сполучає дві різні компоненти }
MERGE(ucomp,   vcomp,   components);
ncomp:=  ncomp  -   1;
INSERT (e,   Т)
end
end
end;    {   Kruskal   }
Для реалізації операторів, використовуваних в цій програмі, можна застосувати методи, описані в розділі 5.5. Час виконання цієї програми залежить від двох чинників. Якщо в початковому графі G всього е ребер, то для вставки їх в чергу з пріоритетами буде потрібно час близько 0(е loge).1 Кожна ітерація циклу while для знаходження ребра з найменшою вартістю в черзі edges вимагає часу порядку O(loge). Тому виконання всього цього циклу в найгіршому випадку зажадає часу 0(е loge). Другим чинником, що впливає на час виконання програми, є загальний час виконання операторів MERGE і FIND, яке залежить від методу реалізації АТД MFSET. Як показано в розділі 5.5, існують методи, що вимагають часу і 0{ е loge), і 0(е α(е)). У будь-якому випадку алгоритм Крускала може бути виконаний за час 0(е loge).
7.3. Обхід неорієнтованих графів
У багатьох завданнях, пов'язаних з графами, потрібно організувати систематичний обхід всіх вершин графа. Існують два найбільш часто використовувані методи обходу графів: пошук в глибину і пошук в ширину , про яких мова піде в цьому розділі. Обидва ці методи можна ефективно використовувати для пошуку вершин, суміжних з даною вершиною.
Пошук в глибину
Нагадаємо, що в розділі 6.5 ми побудували алгоритм dfs для обходу вершин орієнтованого графа. Цей же алгоритм можна використовувати для обходу вершин і неорієнтованих графів, оскільки неорієнтоване ребро (v, w) можна представити у вигляді пари орієнтованих дуг v     и  і  w      v.
Фактично побудувати глибинний остовний ліс для неорієнтованого графа (тобто зробити обхід його вершин) навіть простіше, ніж для орієнтованого. По-перше, відмітимо, що кожне дерево остовного лісу відповідає одній зв'язній компоненті початкового графа, тому, якщо граф зв'язний, його глибинний остовний ліс складатиметься тільки з одного дерева. По-друге, при побудові остовного лісу для орграфа ми розрізняли чотири типи дуг: дуги дерева, передні, зворотні і поперечні дуги, а для неорієнтованого графа в цій ситуації виділяють тільки два типу ребер: ребра дерева і зворотні ребра. Оскільки для неорієнтованого графа не існує напряму ребер, то, природно, прямі і зворотні ребра тут не розрізняються і об'єднані загальною назвою зворотні ребра. Аналогічно, оскільки в остовному дереві для неорієнтованого графа вершини не діляться на нащадків і предків, то немає і перехресних ребер. Дійсно, нехай є ребро (v. w) і припустимо, що при обході графа вершина v досягнута раніше, ніж вершина w. Тоді процедура dfs(v) не може закінчитися раніше, ніж буде розглянута вершина w. Тому в остовному дереві вершину w можна вважати нащадком вершини v. Але так само, якщо спочатку викликається dfs(w), вершина v стає нащадком вершини w.
Отже, при обході вершин неорієнтованого графа методом пошуку в глибину всі ребра діляться на наступні групи.
1.    Ребра дерева — це такі ребра (v, w), що при обході графа процедура dfs{v) викликається безпосередньо перед процедурою dfs{w) або, навпаки, спочатку викликається процедура dfs(w), а потім відразу процедура dfs(v).
2.    Зворотні ребра — такі ребра (v, w), що ні процедура dfs (w) не слідує безпосередньо за процедурою dfs(v), ні процедура dfs(v) не слідує безпосередньо за процедурою dfs(w) (тобто між викликами цих процедур слідують виклики декількох інших процедур dfs(x)) .
Приклад 7.6. Розглянемо зв'язний граф G на мал. 7.8,а. Остовне дерево для цього графа, одержане методом пошуку в глибину, показано на мал. 7.8,6. Пошук був початий з вершини а, і ми дотримувалися угоди зображати ребра дерева суцільними лініями, а зворотні ребра — пунктирними. Зображення остовного дерева почате від кореня, і сини кожної вершини малювалися зліва направо в тому порядку, в якому вони вперше відвідувалися в процедурі dfs.
Опишемо декілька кроків пошуку в глибину для даного графа. Процедура dfs(a) додає ребро (а, b) в остовне дерево Т, оскільки вершина b раніше не відвідувалася, і викликає процедуру dfs(b). Процедура dfs(b) додає ребро (b, d) в остовне дерево T і в свою чергу викликає процедуру dfs(d). Далі процедура dfs(d) додає в остовне дерево ребро (d, е) і викликає dfs(e). З вершиною е суміжні вершини а, b і d, але вони помічені як відвідані вершини. Тому процедура dfs(e) закінчується без додавання ребер в дерево Т. Процедура dfs(d) також знаходить серед вершин, суміжних з вершиною d, тільки вершини, помічені як "відвідані". Процедура dfs(d) завершується без додавання нових ребер в остовне дерево. Процедура dfs(b) перевіряє суміжні вершини, що залишилися, а і е (до цього була перевірена тільки вершина d). Ці вершини відвідувалися раніше, тому процедура dfs(b) закінчується без додавання нових ребер в дерево Т. Процедура dfs(a), продовжуючи роботу, знаходить нові вершини, які раніше не відвідувалися. Це вершини c,  f  і g.

Мал.7.8. Граф і остовне дерево, одержані при обході його вершин методом пошуку в глибину
Пошук в ширину
Інший метод систематичного обходу вершин графа називається пошуком в ширину. Він одержав свою назву через те, що при досягненні під час обходу будь-якої вершини v далі розглядаються всі вершини, суміжні з вершиною v, тобто здійснюється проглядання вершин "в ширину". Цей метод також можна застосувати і до орієнтованих графів.
Так само, як і при застосуванні пошуку у глибину, за допомогою методу пошуку в ширину при обході графа створюється остовний ліс. Якщо після досягнення вершини х при розгляді ребра (х. у) вершина у не відвідувалася раніше, то це ребро вважається ребром дерева. Якщо ж вершина у вже відвідувалася раніше, то ребро (х, у) буде поперечним ребром, оскільки воно сполучає вершини, не зв'язані спадкоємством один одного.
В ескізі процедури bfs (лістинг 7.4), що реалізує алгоритм пошуку в ширину, ребра дерева поміщаються в спочатку порожній масив Т, що формує остовний ліс. Відвідані вершини графа заносяться в чергу Q. Масив mark (мітка) відстежує стан вершин: якщо вершина v пройдена, то елемент mark[v] приймає значення visited (відвідувалася), спочатку всі елементи цього масиву мають значення unvisited (не відвідувалася). Відзначимо, що в цьому алгоритмі, щоб уникнути повторного поміщення вершини в чергу, пройдена вершина позначається як visited до поміщення її в чергу. Процедура bfs працює на одній зв'язній компоненті, якщо граф не однозв'язний, то ця процедура повинна викликатися для вершин кожної зв'язної компоненти.
Лістинг 7.4. Алгоритм пошуку в ширину
procedure  bfs   (   v  ) ;
{ bfs обходить всі вершини,   досяжні із вершини v }
var
Q:   QUEUE   {   черга  для  вершин   }
х,  у:   вершина;
begin
mark[v]:=  visited;
ENQUEUE(v,   Q);
while not EMPTY(Q)   do begin
x: = FRONT(Q);
DEQUEUE(Q);
for для кожної вершини у,   суміжної із вершиною х do
if mark[у]   =  unvisited then begin
mark[y]:=  visited;
ENQUEUE(у,   Q);
INSERT((x,  у),   T)
End
end
end;   { bfs }
Приклад 7.7. Остовне дерево для графа з мал. 7.8,а, побудоване методом пошуку в ширину, показане на мал. 7.9. Тут обхід графа початий з вершини а. Як і раніше, ребра дерева показані суцільними лініями, а інші ребра — пунктирними. Відзначимо також, що дерево намальоване від кореня, а всі сини будь-якої вершини розташовуються зліва направо у порядку відвідин їх.

Мал. 7.9. Остовне дерево для графа із мал.7.8,а, одержане методом пошуку в ширину
Час виконання алгоритму пошуку в ширину такий ж, як і для алгоритму пошуку в глибину. Кожна пройдена вершина поміщається в чергу тільки один раз, тому кількість виконань циклу while співпадає з кількістю переглянутих вершин. Кожне ребро (х, у) є видимим двічі, один раз для вершини х і один раз для вершини у. Тому, якщо граф має п вершин і е ребер, а також якщо для представлення ребер використовуються списки суміжності, загальний час обходу такого графа складе 0(mах(n, е)). Оскільки звичайно е ≥ п, то одержуємо час виконання алгоритму пошуку в ширину порядку О(е), тобто таке ж, як і для алгоритму пошуку в глибину.
Методи пошуків в глибину і в ширину часто використовуються як основа при розробці різних ефективних алгоритмів роботи з графами. Наприклад, обидва ці методи можна застосувати для знаходження зв'язних компонент графа, оскільки зв'язні компоненти, які  представлені окремими деревами в остовному лісі графа.
Метод пошуку в ширину можна використовувати для виявлення циклів в довільному графі, причому за час 0(п) (п — кількість вершин графа), яке не залежить від кількості ребер. Як показано в розділі 7.1, граф з п вершинами і з п або більшою кількістю ребер обов'язково має цикл. Проте якщо в графі п - 1 або менше ребер, то цикл може бути тільки у тому випадку, коли граф складається з двох або більше зв'язних компонент. Один із способів знаходження циклів полягає в побудові остовного лісу методом пошуку в ширину. Тоді кожне поперечне ребро (v, w) замикає простий цикл, що складається з ребер дерева, ведучих до вершин v і w від загального предка цих вершин, як показано на мал. 7.10.

Мал.7.10. Цикл, знайдений методом пошуку в ширину
7.4. Точки зчленовування і двозв’язні компоненти
Точкою зчленовування графа називається така вершина v, коли при видаленні цієї вершини і всіх ребер, інцидентних вершині v, зв'язна компонента графа розбивається на дві або декілька частин. Наприклад, точками зчленовування для графа з мал. 7.8,а є вершини а і с. Якщо видалити вершину а, то граф, який є однією зв'язною компонентою, розбивається на два "трикутники" {b, d, e} і { c, f, g}. Якщо видалити вершину, то граф розчленовується на підграфи {а, b, d, e} і {f,g}. Але якщо видалити яку-небудь іншу вершину, то в цьому випадку не вдасться розбити зв'язну компоненту на декілька частин. Зв'язний граф, що не має точок зчленовування, називається двозв’язним. Для знаходження двозв’язних компонент графа часто використовується метод пошуку в глибину.
Метод знаходження точок зчленовування часто застосовується для вирішення важливої проблеми, що стосується к-зв’язності графів. Граф називається к-зв’язним, якщо видалення будь-яких к - 1 вершин не приведе до розчленовування графа. Зокрема, граф має зв'язність 2 або вище тоді і тільки тоді, коли він не має точок зчленовування, тобто тільки тоді, коли він є двозв’язним. Чим вища зв'язність графа, тим більше можна видалити вершин з цього графа, не порушуючи його цілісності, тобто не розбиваючи його на окремі компоненти.
Опишемо простий алгоритм знаходження всіх точок зчленовування зв'язного графа, заснований на методі пошуку в глибину. За відсутності цих точок граф, природно, буде двозв’язним, тобто цей алгоритм можна розглядати так само, як тест на двозв'язність неорієнтованого графа.
1.    Виконується обхід графа методом пошуку в глибину, при цьому для всіх вершин v обчислюються числа dfnumber[v], введені в розділі 6.5. По суті, ці числа фіксують послідовність обходу вершин в прямому порядку вершин глибинного остовного дерева.
2.    Для кожної вершини v обчислюється число low[v], рівне мінімуму чисел dfnumber нащадків вершини v, включаючи і саму вершину v, і предків w вершини v, для яких існує зворотне ребро (х, w), де х — нащадок вершини v. Числа low[v] для всіх вершин v обчислюються при обході остовного дерева в зворотному порядку, тому при обчисленні low[v] для вершини v вже підраховані числа low[x] для всіх нащадків х вершини v. Отже, low[v] обчислюється як мінімум наступних чисел:
а)    dfnumber[v];
б)    dfnuntber[z] всіх вершин z, для яких існує зворотне ребро (v, z);
в)    low{x] всіх нащадків х вершини v.
3.    Тепер точки зчленовування визначаються таким чином:
а)    корінь остовного дерева буде точкою зчленовування тоді і тільки тоді, коли він має два або більше синів. Оскільки в остовном дереві, яке одержане методом пошуку в глибину, немає поперечних ребер, то видалення такого кореня розчленує остовне дерево на окремі піддерева з корінням, які є синами кореня побудованого остовного дерева;
б)    вершина v, відмінна від кореня, буде точкою зчленовування тоді і тільки тоді, коли має такого сина w, що low[w]≥ dfnumber[v]. В цьому випадку видалення вершини v (і, звичайно, всіх інцидентних їй ребер) відокремить вершину w і всіх її нащадків від решти частини графа. Якщо ж low[w]< dfnumber[v], то існує шлях по ребрах дерева до нащадків вершини w і зворотне ребро від якого-небудь з цих нащадків до дійсного предка вершини v (саме значенню dfnumber для цього предка рівне low[w]). Тому в даному випадку видалення вершини v не відокремить від графа піддерево з коренем w.
Приклад 7.8. Числа dfnumber і low, підраховані для вершин графа з мал. 7.8,а, показані на мал. 7.11. В даному прикладі обчислення чисел low почате в зворотному порядку з вершини е. З цієї вершини виходять зворотні ребра (е, а) і (е, b), тому low[e] = min(dfnumber[e], dfnumber[a], dfnumber[b]) = 1. Потім розглядається вершина d, для неї low[d] знаходиться як мінімум чисел dfnumber[d], tow[e] і dfnumber[a]. Тут число low[e] бере участь тому, що вершина е є сином вершини d, а число dfnumber[a] — через те, що існує зворотне ребро (d, а).
Для визначення точок зчленовування після обчислення всіх чисел low є видимою кожна вершина остовного дерева. Корінь а є точкою зчленовування, оскільки має двох синів. Вершина c також є точкою зчленовування — для її сина, вершини f, виконується нерівність low[f] ≥ dfnumber[c]. Інші вершини не є точками зчленовування.   
Час виконання описаного алгоритму на графі з п вершинами і е ребрами має порядок 0(e). Читач легко перевірить, що час, що витрачається на виконання кожного етапу алгоритму, залежить або від кількості відвідуваних вершин, або від кількості ребер, інцидентних цим вершинам, тобто у будь-якому випадку час виконання, з точністю до константи пропорційності, є функцією як кількості вершин, так і кількості ребер. Тому загальний час виконання алгоритму має порядок 0( п + е) або O(е), що те ж саме при п ≤ е.


Мал. 7.11. Числа dfnumber і low, підраховані для графа з мал.7.8,а       
7.5. Попарне сполучення графів
У цьому розділі ми опишемо алгоритм рішення "задачі про парне сполучення" графів. Простим прикладом, що приводить до такого завдання, може служити ситуація розподілу викладачів по множині учбових курсів. Треба призначити на читання кожного курсу викладача певної кваліфікації так, щоб ні на який курс не було призначено більше одного викладача. З іншого боку, бажано використовувати максимально можливу кількість викладачів з їх складу.

Мал.7.12. Дводольний граф
Описану ситуацію можна представити у вигляді графа, показаного на мал. 7.12, де всі вершини розбиті на дві множини V1 і V2 так, що вершини з множини V1 відповідають викладачам, а вершини з множини V2 — учбовим курсам. Той факт, що викладач v може вести курс w, відображається за допомогою ребра (v, w). Граф, у якого множина вершин розпадається на дві непересічні підмножини V1 і V2 таких, що кожне ребро графа має один кінець з V1, а інший — з V2, називається дводольним.. Таким чином, завдання розподілу викладачів по учбових курсах зводиться до завдання вибору певних ребер в дводольному графі, що має множину вершин-викладачів і множину вершин-учбових курсів.
Завдання попарного сполучення можна сформулювати таким чином. Є граф G = (V, Е). Підмножина його ребер, така що ніякі два ребра з цієї підмножини не інцидентні якій-небудь одній вершині з V, називається попарним сполученням. Завдання визначення максимальної підмножини таких ребер називається завданням знаходження максимального попарного сполучення. Ребра, виділені товстими лініями на мал. 7.12, складають одне можливе максимальне попарне сполучення для цього графа. Повним попарним сполученням називається попарне сполучення, в якому беруть (як кінці ребер) участь всі вершини графа. Очевидно, що будь-яке повне попарне сполучення є також максимальним попарним сполученням.
Існують прямі способи знаходження максимальних попарних сполучень. Наприклад, можна послідовно генерувати всі можливі попарні сполучення, а потім вибрати те, яке містить максимальну кількість ребер. Але такий підхід має істотний недолік — час його виконання є експоненціальною функцією від числа вершин.



а. Попарне сполучення

б. Ланцюг, що чергується
Мал.7.13. Попарне сполучення і повторюваний ланцюг
В даний час розроблені ефективніші алгоритми знаходження максимальних попарних сполучень. Ці алгоритми використовують в основному метод, відомий як ланцюги, що "чергуються". Нехай М — попарне сполучення в графі G. Вершину і називатимемо парною, якщо вона є кінцем одного з ребер попарного сполучення М. Шлях, що сполучає дві непарні вершини, в якому чергуються ребра, що входять і що не входять в множину М, називається ланцюгом, що чергується (аугментальним), відносно М. Очевидно, що ланцюг, що чергується, повинен бути непарної довжини, починатися і закінчуватися ребрами, що не входять в множину М. Також зрозуміло, що, маючи ланцюг Р, що чергується, ми можемо збільшити попарне сполучення М, видаливши з нього ті ребра, які входять в ланцюг Р, і замість видалених ребер додати ребра з ланцюга Р, які спочатку не входили в попарне сполучення М. Це нове попарне сполучення можна визначити як M ∆ P, де ∆ позначає симетричну різницю множини М і Р, тобто до нової множини попарних сполучень увійдуть ті ребра, які входять або в множину М, або в множину Р, але не в обидві відразу.
Приклад 7.9. На мал. 7.13,а показані граф і попарне сполучення М, що складається з ребер (на малюнку вони виділені товстими лініями) (1, 6), (3, 7) і (4, 8). На мал. 7.13,6 представлений ланцюг щодо М, що чергується, який складається з вершин 2, 6, 1, 8, 4, 9. На мал. 7.14 зображене попарне сполучення (1, 8), (2, 6), (3, 7), (4, 9), яке одержане видаленням з попарних сполучень М ребер, що входять в цей ланцюг, що чергується, і додаванням нових ребер, що також входять в цей ланцюг.

Мал.7.14. Збільшене попарне сполучення
Попарне сполучення М буде максимальним тоді і тільки тоді, коли не існуватиме ланцюгу, що чергується, відносно М. Це ключова властивість максимальних попарних сполучень буде основою наступного алгоритму знаходження максимального попарного сполучення.
Нехай М і N — попарні сполучення в графі G, причому | М| < |N| (тут | М| позначає кількість елементів множини М). Для того, щоб показати, що M ∆ N містить ланцюг, що чергується, щодо М, розглянемо граф G* = (V*, М ∆ N), де V — множина кінцевих вершин ребер, що входять в М ∆ N. Неважко відмітити, що кожна зв'язна компонента графа G* формує простий шлях (можливо, цикл), в якому чергуються ребра з М і N. Кожен цикл має рівне число ребер, належних М і N, а кожен шлях, що не є циклом, є ланцюгом, що чергується, відносно або М, або N, залежно від того, ребер якого попарного сполучення більше в цьому ланцюзі. Оскільки | М| < |N|, та множина M ∆ N містить більше ребер з попарного сполучення N, чим М, і, отже, існує хоч би один ланцюг, що чергується, відносно М.
Тепер можна описати алгоритм знаходження максимального попарного сполучення М для графа G = (V, Е).
1.    Спочатку покладемо М = Ø.
2.    Далі шукаємо ланцюг Р, що чергується, щодо М, і множина М замінюється на множину М ∆ Р.
3.    Крок 2 повторюється до тих пір, поки існують ланцюги, що чергуються, щодо М, Якщо таких ланцюгів більше немає, то М — максимальне попарне сполучення.
Нам залишилося показати спосіб побудови ланцюгів, що чергуються, відносно попарних сполучень М. Розглянемо простіший випадок, коли граф G є дводольним графом з множиною вершин, розбитим на дві підмножини V1 і V2. Ми будуватимемо граф ланцюга, що чергується, по рівнях і = 0, 1, 2, ... , використовуючи процес, подібний пошуку в ширину. Граф ланцюга, що чергується, рівня 0 містить всі непарні вершини з множини V1. На рівні з непарним номером і додаються нові вершини, суміжні з вершинами рівня і - 1 і сполучені ребром, що не входить в попарне сполучення (це ребро теж додається в граф, що будується). На рівні з парним номером і також додаються нові вершини, суміжні з вершинами рівня і - 1, але які сполучені ребром, що входить в попарне сполучення (це ребро теж додається в граф ланцюга, що чергується).
Процес побудови продовжується до тих пір, поки до графа ланцюга, що чергується, можна приєднувати нові вершини. Відзначимо, що непарні вершини приєднуються до цього графа тільки на непарному рівні. У побудованому графі шлях від будь-якої вершини непарного рівня до будь-якої вершини рівня 0 є ланцюгом, що чергується відносно М.
Приклад 7.10. На мал. 7.15 зображений граф ланцюга, що чергується, побудований для графа з мал. 7.13,а щодо попарного сполучення, показаного на мал. 7.14. На рівні 0 маємо одну непарну вершину 5. На рівні 1 додане ребро (5, 6), що не входить в попарне сполучення. На рівні 2 додане ребро (6, 2), що входить в попарне сполучення. На рівні 3 можна додати або ребро (2, 9), або ребро (2, 10), що не входить в попарне сполучення. Оскільки вершини 9 і 10 поки в цьому графі непарні, можна зупинити процес побудови графа ланцюга, що чергується, додавши в нього одну або іншу вершину. Обидва шляхи 9, 2, 6, 5 і 10, 2, 6, 5 є ланцюгами, що чергуються, щодо попарного сполучення з мал. 7.14.

Мал.7.15. Граф ланцюга, що чергується
Нехай граф G має п вершин і е ребер. Якщо використовуються списки суміжності для представлення ребер, то на побудову графа ланцюга, що чергується, буде потрібно часу близько О(e). Для знаходження максимального попарного сполучення треба побудувати не більше п/2 ланцюгів, що чергуються, оскільки кожний такий ланцюг збільшує поточне попарне сполучення не менше, ніж на одне ребро. Тому максимальне попарне сполучення для дводольного графа можна знайти за час порядку О(пе).
Вправи
7.1.    Опишіть алгоритм вставки і видалення ребер неорієнтованого графа, представленого списками суміжності. Пам'ятайте, що кожне ребро (i, j) з'являється в списку суміжності вершини і та вершини  j.
7.2.    Змініть представлення неорієнтованого графа за допомогою списків суміжності так, щоб перше ребро в списку суміжності будь-якої вершини можна було б видалити за фіксований час. Напишіть процедуру видалення перших ребер, інцидентних вершинам, використовуючи нове представлення списків суміжності. Підказка: як зробити так, щоб два осередки, відповідні ребру (і, j), могли швидко знаходити один одного?
7.3.     Для графа, показаного на мал. 7.16, побудуйте
а)    остовне дерево мінімальної вартості за допомогою алгоритму Пріма;
б)    остовне дерево мінімальної вартості за допомогою алгоритму Крускала;
в)    остовне дерево методом пошуку в глибину, починаючи з вершин a та d;
г)    остовне дерево методом пошуку в ширину, починаючи з вершин а і d.

Мал.7.16. Граф
7.4.  Нехай Т — глибинне остовне дерево і В — множина зворотних ребер для зв'язного    неорієнтованого графа G = (V, Е).
*а) Покажіть, що додавання в остовне дерево Т будь-якого зворотного ребра з множини В приводить до утворення в Т одного циклу. Назвемо такий цикл базовим.
**б) Лінійною комбінацією циклів С1, С2, ... , Сп називається структура С1 ∆ С2 ∆ …∆ Сп . Доведіть, що лінійна комбінація двох різних пересічних циклів є циклом.
**с) Покажіть, що будь-який цикл в графі G можна представити як лінійну комбінацію базових циклів.
*7.5.    Нехай G = (V, Е) — довільний граф. Позначимо через R таке відношення на множині вершин V, що сRv виконується тоді і тільки тоді, коли вершини u і v належать одному загальному (не обов'язково простому) циклу. Доведіть, що відношення R є відношенням еквівалентності на множині V.
7.6.    Реалізуйте алгоритми Пріма і Крускала. Порівняйте час виконання ваших програм на множині "випадкових" графів.
7.7.    Напишіть програму знаходження всіх зв'язних компонент графа.
7.8.    Напишіть програму з часом виконання 0(п), щоб визначити, чи є в графі з п вершинами цикл.
7.9.    Напишіть програму перерахунку всіх простих циклів в графі. Скільки може бути таких циклів? Яка тимчасова складність (час виконання) такої програми?
7.10.    Доведіть, що при обході вершин графа методом пошуку в ширину кожне ребро може бути або ребром дерева, або зворотним ребром.
7.11.    Реалізуйте алгоритм знаходження точок зчленовування, описаний в розділі 7.4.
*7.12.    Нехай G = {V, Е) — повний граф, тобто такий, що для будь-якої пари різних
вершин існує ребро, що їх сполучає. Нехай G' = (V, Е') — орієнтований граф, в якому множина дуг Е' одержана шляхом випадкової орієнтації ребер з множині Е. Покажіть, що орграф G' має шлях, який проходить через всі вершини графа точно один раз.
*7.13.    Покажіть, що повний граф з п вершина має пп-2 остовних дерев.
7.14.    Знайдіть всі максимальні попарні сполучення для графа, зображеного на мал. 7.12.
7.15.    Напишіть програму знаходження максимального попарного сполучення для дводольного графа.
7.16.    Нехай М — попарне сполучення і т — число ребер в максимальному попарному   сполученні. Доведіть, що
а)    існують    ланцюги, що чергується    щодо    М,    чия    довжина    рівна 2(|М||/(m - |М|)) + 1 або менше;
б)    якщо Р — найкоротший ланцюг, що чергується, щодо М, а Р' — ланцюг, що чергується, щодо M ∆ P, тоді | Р' | ≥ | Р| +| Р ∩ Р' |
*7.17.    Доведіть, що граф буде дводольним тоді і тільки тоді, коли він не має циклів непарної довжини. Приведіть приклад недводольного графа, для якого спосіб побудови графа ланцюга, що чергується, викладений в розділі 7.5, не працює.
7.18.    Нехай М і N — попарні сполучення в дводольному графі, причому | М| < |N|. Доведіть, що М ∆ N має принаймні |N| - | М| вершин, що не входять в ланцюги, що чергуються, відносно М.