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

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

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

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

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

В неорієнтованому графі, вершина 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