Впродовж даного уроку розглядатимемо лише неорієнтовані та ненавантажені графи.
Означення.
Граф називається зв'язним, якщо існує хоча б один маршрут між будь-якими двома його вершинами.
Вважаємо, що маршрут, що веде від деякої вершини в ту саму вершину, завжди існує, навіть коли ця вершина ізольована (в такому випадку маршрут не містить жодного ребра). Тому граф, що містить єдину вершину, зв'язний. Граф, у якому більше одної вершини і який має хоча б одну ізольовану вершину, не є зв'язним.
Означення.
Дві вершини, між якими існує хоча б один маршрут, називаються досяжними.
Властивості досяжності.
1. Кожна вершина графа досяжна з самої себе.
2. Якщо вершина a досяжна з вершини b, то вершина b досяжна з вершини a.
3. Якщо вершина a досяжна з вершини b і вершина b досяжна з вершини c, то вершина a досяжна з вершини c.
Приклади.
Малюнок 1
Малюнок 2
Граф, зображений на малюнку 1, зв'язний, а на малюнку 2 - не є, тому що не існує шляху, наприклад, з вершини 1 до вершини 7.
Як перевірити, чи є заданий граф зв'язним? Якщо скористатись означенням, необхідно перевірити всі пари вершин, чи є шлях між ними. Але виявляється, що можна перевіряти не всі пари. Справедливе таке твердження.
Граф зв'язний тоді і тільки тоді, коли існують шляхи від довільної вершини до всіх інших.
Доведемо це твердження. Виберемо вершину k. Дійсно, якщо граф є зв'язним, існують маршрути між будь-якими двома вершинами, а значить, існує і маршрут від вершини k до будь-якої вершини графа. Доведемо, що якщо існує маршрут від вершини k до будь-якої вершини графа i, то граф зв'язний. Дійсно, якщо існує маршрут від k до i, існує також маршрут від i до k. Якщо існує маршрут від k до j, існує також маршрут від j до k. Маршрут від i до j складаємо з двох частин - спочатку від i до k, потім додаємо маршрут від k до j. Отже, від i до j маршрут існує, а тому граф зв'язний.
Постановку задачі перевірки графа запишемо у вигляді функції логічного типу. Граф задається матрицею суміжності.
ЛогАлг зв'язність(ціл n, цілтаб a[1..n, 1..n])
Арг n,a
Для перевірки графа достатньо вибрати довільну вершину і перевірити, чи існує шлях від неї до будь-якої іншої. Діятимемо таким чином. Спочатку виберемо довільну вершину (наприклад, першу). Складемо список вершин, до яких існує маршрут довжиною 1від вибраної (тобто суміжних з вибраною). Для кожної з отриманих вершин створимо список вершин, суміжних з нею. Так ми отримаємо вершини, до яких існує маршрут довжиною 1 або 2. Повторюватимемо цей процес далі. Максимальна довжина маршруту дорівнює n-1 ребер (див. малюнок). Зауважимо, що для зберігання вершин доцільно використовувати множинний тип, тому що порядок вершин не є важливим. Отримаємо такий алгоритм
ЛогАлг зв'язність1(ціл n, цілтаб a[1..n, 1..n])
Арг n,a
Поч
Множ s
Ціл i {довжина шляху}, j, k
s:=[1] {початкова вершина}
Для i від 2 до n
пц
Для всіх елементів j, що належать s
Отримати всі вершини k такі, що j та k суміжні
Додати k до s
кц
Знач:=s=[1..n]
Кін
Завдання.
Деталізуйте цей алгоритм, перекладіть його мовою Паскаль і перевірте в on-line.
Цей алгоритм не є досконалим. Розглянемо такий граф:
0
1
1
1
1
1
1
1
1
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
Виконаємо алгоритм "зв'язність1" для цього графа. Коли починається виконання циклу по і, у списку відвіданих вершин міститиметься єдина вершина - перша.
Отже, при i>2 для даного прикладу шукати вершини, до яких існує шлях від першої, немає сенсу - вже зрозуміло, що граф зв'язний. Модифікуємо алгоритм зв'язність1 таким чином. Якщо при черговій перевірці до множини додано вершини, необхідно продовжити роботу, а якщо жодної вершини додано не було, очевидно, і не буде додано, і алгоритм повинен завершити свою роботу.
ЛогАлг зв'язність2(ціл n, цілтаб a[1..n, 1..n])
Арг n,a
Поч
Множ s
Ціл j, k
Лог f
s:=[1] {початкова вершина}
f:=Так
Поки f
пц
f:=Ні
Для всіх елементів j, що належать s
Отримати всі вершини k такі, що j та k суміжні
Якщо k не належить s
то f:=Так
Додати k до s
все
кц
Знач:=s=[1..n]
Кін
Алгоритм зв'язність2 можна покращити, якщо на кожному кроці шукати нову вершину не серед усіх, а тільки серед тих, які ще не відвідувались. Також доцільно шукати вершину, суміжну з новою, не серед усіх відвіданих раніше, а тільки з тих, що було додано на останньому кроці. Пропонується модифікувати алгоритм зв'язність2 самостійно.
Розглянемо дещо інший підхід до перевірки графа. Нехай деяка вершина графа a є початковою. Якщо для всіх вершин ця вершина досяжна, граф зв'язний. Нехай b - вершина графа, досяжна з вершини a.
Отже, якщо дві різні вершини a і b досяжні одна з одної, виконується хоча б одна з двох умов:
1) ці вершини суміжні;
2) існує така вершина c, щоa і c досяжні одна з одної, а c і b суміжні.
Наприклад, якщо вершини графа - аеропорти, а ребра - авіарейси, то звязність такого графа означає можливість дістатись запропонованими рейсами від будь-якого аеропорту до будь-якого іншого. Суміжність вершин - це не що інше як існування прямого рейсу між аеропортами. Нехай ми знаходимось у аеропорту Бориспіль і хочемо потрапити у Хітроу. Отже, Бориспіль - це вершина графа a, а Хітроу - це вершина b. Якщо прямий рейс існує, Бориспіль і Хітроу є суміжними, а значить, і досяжними.
Отже, якщо з Борисполя до Хітроу прямого рейсу немає, але з пересадками долетіти можна (наприклад, існують рейси Бориспіль-Франкфурт, Франкфурт-Мадрид і Мадрид-Хітроу), то вершини графа будуть досяжними, але не суміжними. В такому випадку перша умова не виконується, а друга виконується.
Нехай а - початкова вершина. Назвемо вершину графа, в якій ми знаходимось, поточною. Нехай це вершина b. Додамо її до списку відвіданих. Спробуємо знайти вершини, які ще не відвідувались і які суміжні з поточною. Для кожної такої вершини c відомо, що a і b досяжні (інакше вершина b не стала б поточною), b і c суміжні, тому a і c досяжні. Переходимо до вершини c і виконуємо аналогічні дії для неї.
Запишемо описаний вище процес алгоритмічною мовою:
Алг Обхід (Ціл k)
Поч
Додати k до списка відвіданих вершин
Для всіх вершин i
пц
Якщо вершина і не відвідана та вершини i та k суміжні
тоОбхід(i)
все
кц
Кін
Як бачимо, отримано рекурсивний допоміжний алгоритм Обхід.
Деталізуємо цей допоміжний алгоритм і побудуємо головний.
ЛогАлг зв'язність3(ціл n, цілтаб a[1..n, 1..n])
Арг n,a
Поч
Множ s
s:=[]
Обхід(1)
Знач:=s=[1..n]
Кін
Алг Обхід (Ціл k)
Поч
Ціл i
s:=s+[k]
Для i від 1 до n
пц
Якщо і не належить s та a[i,k]>0
тоОбхід(i)
все
кц
Кін
Означення.
Нехай V - множина вершин деякого графа. Підмножина U є компонентою зв'язності графа, якщо кожна пара вершин з множини U є досяжною з будь-якої вершини і не є досяжною з будь-якої іншої.
Приклад
Граф, зображений на малюнку 2, має 2 компоненти зв'язності - [1..5] та [6..9].
Підрахуємо для заданого графа кількість компонент зв'язності. Граф задаватимемо матрицею суміжності.
Алг Компоненти( Ціл n, ЦілТаб a[1..n,1..n], Ціл s)