Зв’язність графа
Для
довільного неорієнтованого графа
розглянемо відношення Q
між вершинами — “бути зв’язаним
ланцюгом”. Рефлексивність цього
відношення випливає з того, що ланцюг
нульової довжини містить одну вершину
v,
і тому можна стверджувати, що вершина
v
зв’язана ланцюгом сама з собою, тобто
.
Якщо
,
тобто вершина
зв’язана ланцюгом з вершиною
,
і, оскільки в ланцюгу напрямок не
враховується, то вершина
теж зв’язана ланцюгом з вершиною
;
отже,
— тобто відношення Q
симетричне. Якщо
і
,
тобто вершина
зв’язана ланцюгом з вершиною
і вершина
зв’язана ланцюгом з вершиною
,
то і вершина
зв’язана ланцюгом з вершиною
,
тобто
і відношення Q
є транзитивним.
Оскільки відношення між вершинами “бути зв’язаним ланцюгом” є рефлексивним, симетричним і транзитивним, то воно є відношенням еквівалентності. Тому вершини графа можна однозначно розбити на класи еквівалентності — максимально зв’язні підграфи. Підграфи, носіями яких є такі класи вершин, називаються компонентами зв’язності графа (ще кажуть: зв’язними компонентами). При цьому будь-які дві вершини із будь-якої зв’язної компоненти зв’язані хоч би одним ланцюгом, а вершини з різних компонент ланцюгом не зв’язані.
Якщо в скінченному неорієнтованому графі рівно дві вершини мають непарний степінь, то ці вершини зв’язані ланцюгом.
Граф називається зв’язним, якщо він має рівно одну компоненту зв’язності, тобто будь-які дві його вершини можна з’єднати ланцюгом.
У будь-якому графі його компоненти зв’язності є максимальними зв’язними підграфами даного графа.
Зауважимо, що незв’язні графи є ациклічними.
При розв’язуванні більшості практичних задач досить розглядати тільки зв’язні графи.
Орієнтований
граф називається сильно
зв’язним,
якщо для будь-яких двох вершин
і
при
існує шлях із вершини
у вершину
,
а також шлях із вершини
у вершину
(ці шляхи не обов’язково мають проходити
через ті самі проміжні вершини).
Орієнтований граф називається зв’язним
(ще кажуть: слабо зв’язним), якщо із
вершини
у вершину
існує ланцюг у співвіднесеному
неорієнтованому графі, тобто, якщо його
співвіднесений граф зв’язний. Орієнтований
граф називається однобічно
зв’язним,
якщо існує шлях із вершини
у вершину
,
але шляху із вершини
у вершину
немає.
Сильно зв’язний граф є зв’язним, але зворотне твердження не правильне.
Сильна зв’язність важлива, наприклад, у комунікаційних мережах, щоб кожен користувач міг передати інформацію іншому користувачеві безпосередньо чи через посередників.
Граф
можна характеризувати за допомогою
матриці
досяжності
.
Рядки і стовпчики цієї матриці, як і
матриці суміжності, позначають елементами
множини вершин V.
При цьому
;
,
якщо в графі існує ланцюг (шлях) із
вершини
у вершину
;
,
якщо в графі не існує ланцюга (шляху) із
вершини
у вершину
.
У неорієнтованого зв’язного і
орієнтованого сильно зв’язного графа
матриця досяжності містить тільки
одиниці.
Приклад. Для поданих нижче орієнтованих графів А, В і С
відповідні матриці досяжності мають вигляд:
Для неорієнтованих графів Х і Y
матриці досяжності будуть симетричними:
◄
Теорема. У будь-якому графі без кратних ребер і без петель матриця досяжності D визначається матрицею суміжності B за формулою:
,
де Е — одинична матриця.
Якщо
незв’язний граф має n
вершин, m
ребер і k
компонент зв’язності, то число
називають цикломатичним
числом графа.
Якщо граф зв’язний, тобто має одну
компоненту зв’язності, то його
цикломатичним числом буде
.
Цикломатичне число зв’язного графа
дорівнює найбільшій кількості
незалежних??????? циклів у графі. Наприклад,
при розрахункові електричних ланцюгів
цикломатичне число використовується
для визначення незалежних контурів.
Зв’язністю
графа
називають мінімальну кількість c
його вершин, вилучення яких разом з
інцидентними їм ребрами робить граф
незв’язним. Це означає, що вилучення
будь-яких (
)
вершини не порушує зв’язності графа,
але існують с
вершин, вилучення яких порушує зв’язність
графа. При цьому граф називають с-зв’язним.
Приклад. Визначити зв’язність графа:
Розв’язання. Цей граф має зв’язність 1, бо вилучення однієї з вершин b, c чи d приведе до його незв’язності.