Связность

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

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

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