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

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

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

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

ред.

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

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

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

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

Див. також

ред.

Посилання

ред.