В теорії графів, компонента зв'язності неорієнтованого графа це , в якому будь-які дві вершини зв'язані одна з одною шляхами, і вони не зв'язані з ніякими додатковими вершинами. Наприклад, граф на малюнку праворуч має три компоненти зв'язності. Зв'язний граф має рівно одну компоненту зв'язності, яка містить весь граф.
![image](https://www.wikidata.uk-ua.nina.az/image/aHR0cHM6Ly93d3cud2lraWRhdGEudWstdWEubmluYS5hei9pbWFnZS9hSFIwY0hNNkx5OTFjR3h2WVdRdWQybHJhVzFsWkdsaExtOXlaeTkzYVd0cGNHVmthV0V2WTI5dGJXOXVjeTkwYUhWdFlpODRMemcxTDFCelpYVmtiMlp2Y21WemRDNXpkbWN2TWpRd2NIZ3RVSE5sZFdSdlptOXlaWE4wTG5OMlp5NXdibWM9LnBuZw==.png)
Відношення еквівалентності
Ще одним шляхом визначення компонент зв'язності залучає класи еквівалентності вершин графа.
В неорієнтованому графі, вершина 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
![]() | Це незавершена стаття про алгоритми. Ви можете проєкту, виправивши або дописавши її. |
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет