Связность.

Определение 10.5. Говорят, что две вершины связаны, если существует соединяющая их простая цепь.

Определение 10.6. Граф, в котором все вершины связаны – называют связным.

Отношение связанности вершин является эквивалентностью. Классы эквивалентности по отношению связанности называют компонентами связности графов. Число компонентов графа G обозначают k(G). Граф G является связным тогда и только тогда, когда k(G) = 1. Если k(G) > 1, то G – несвязный граф. Граф, состоящий только из изолированных вершин, в котором k(G) = p(G) и r(G) = 0 называют вполне несвязным графом.