Компонента зв'язності графа

Граф з трьома компонентами зв'язності

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

Відношення еквівалентності

Ще одним шляхом визначення компонент зв'язності залучає класи еквівалентності вершин графа.

В неорієнтованому графі, вершина v досяжна з вершини u, якщо існує шлях з u до v. В цьому визначенні, окрема вершина приймається як шлях нульової довжини, і одна і та сама вершина може зустрічатись більш ніж раз уздовж шляху. Досяжність це відношення еквівалентності, бо виконуються правила:

• рефлексивність: Існує тривіальний шлях нульової довжини від вершини до самої себе.
• симетричність: Якщо існує шлях від u до v, тоді ті самі ребра утворюють шлях від v до u.
• транзитивність: Якщо існує шлях від u до v і шлях від v до w, обидва шляхи можуть бути об'єднані в шлях від u до w.

Тоді компоненти зв'язності це підграфи утворені класами еквівалентності цього відношення.

Див. також

• Фактор-граф

Посилання

• Connected components [Архівовано 23 Лютого 2011 у Wayback Machine.], Steven Skiena, The Stony Brook Algorithm Repository