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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук
Граф з трьома компонентами зв'язності

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

Відношення еквівалентності[ред.ред. код]

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

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

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

Посилання[ред.ред. код]