Визначення компоненти зв’язності в графі by lala najafova on prezi

Please log in to add your comment.

Transcript of Визначення компоненти зв'язності в графі

Визначення. Якщо граф не є зв'язковим, то він називається незв'язних.
Незв'язний граф складається з компонент зв'язності.

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

Реалізація
алгоритму
Поняття зв'язності графа
Як визначити, чи є граф зв'язковим? І як визначити кількість компонент зв'язності?
Приклад: на малюнку трохи нижче граф є зв'язковим. Однак, скажімо, якщо видалити ребро між вершинами 4 і 5, то зв'язковим він не буде - з вершини 5 можна буде потрапити ні в яку іншу вершину.

Сильно зв'язний оргаф
Визначення. Граф називається зв'язковим, якщо для будь-яких двох його вершин v, w існує маршрут з v в w
Якщо граф зв'язний і без циклів (тобто це дерево), то видалення будь-якого ребра призведе до втрати зв'язності.

Визначення. Орграф називається односторонньо сильно зв'язковим, якщо для будь-яких його двох вершин, по крайней мере, одна досяжна з іншої.
На малюнку наведено граф з двома компонентами зв'язності.
У незв'язною графа будь-яка компонента зв'язності складається не більше, ніж з n-1 вершин. Якщо відомо, що у графа k компонент зв'язності, то даємо ще більш сувору оцінку: будь-яка компонента зв'язності складається з не більше, ніж з n-k + 1 вершин.

Якщо у незв'язною графа k компонент зв'язності, то для отримання зв'язкового графа потрібно додати в граф як мінімум k-1 ребро.

Вибираємо деяку вершину A і помічаємо її як відвіданих (1), інші відповідно покладаються ще не відвіданих (0):
Визначення компоненти зв'язності графа
A вважаємо поточної вершиною. Далі діємо в такий спосіб. Позначка невідвіданих суміжних вершин: для поточної вершини шукаємо суміжні з нею, ще не невідвіданих, і помічаємо їх як відвідані.

Нехай у нас виявилося k новопомеченних вершин (на малюнку трохи вище їх 3). По черзі вибираємо одну з них поточної і рекурсивно виконуємо позначку невідвіданих суміжних з нею вершин. Для поточної вершини не виконується рекурсія, якщо у даної вершини немає суміжних вершин, які все ще не позначені як відвідані.

Якщо після таких дій все вершини опиняться позначені як відвідані, граф зв'язний, інакше незв'язних.

Висновок: не всі вершини відвідали, граф виявився незв'язним.

Для реалізації трохи зручнішим є обхід в глибину:

int n;
vector g [MAXN];
bool used [MAXN];
vector comp;

void dfs (int v) used [v] = true;
comp.push_back (v);
for (size_t i = 0; i if (! used [to])
dfs (to);
>
>

void find_comps () for (int i = 0; i used [i] = false;
for (int i = 0; i if (! used [i]) comp.clear ();
dfs (i);

cout <<"Component:";
for (size_t j = 0; j cout <<' ' < cout <>
>

алгоритм знаходження
кількості
компонента зв'язності.
Для вирішення можна скористатися як обходом в глибину, так і обходом в ширину.

Фактично, ми будемо виробляти серію обходів: спочатку запустимо обхід з першої вершини, і всі вершини, які він при цьому обійшов - утворюють першу компоненту зв'язності. Потім знайдемо першу з решти вершин, які ще не були відвідані, і запустимо обхід з неї, знайшовши тим самим другу компоненту зв'язності. І так далі, поки всі вершини не стануть поміченими.

Наджафова Лала ТК-31