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

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

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

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

Це незавершена стаття про алгоритми. Ви можете допомогти проєкту, виправивши або дописавши її.