Компоненти зв’язності

Нагадаємо, що граф називають зв’язним, якщо у ньому існує шлях між кожною парою вершин.

Позначимо множину, що складається з даної вершини і всіх тих вершин графа, що можуть бути з’єднані з нею ланцюгом.

Означення 2.3.1. Компонента зв’язності чи просто компонента – це підграф, породжений множиною типу або вершинно породжений підграф .