ОПРЕДЕЛЕНИЕ. Компонентами связности графа G называются максимальные связные подграфы этого графа

Компонентами связности графа G называются максимальные связные подграфы этого графа.

Здесь максимальность понимается как максимальность числа вершин и ребер, входящих в компоненты связности.

То есть связный подграф G ₁=(V ₁, U ₁) графа G =(V, U) называется компонентой связности этого графа, если он содержит все ребра из U, начала и концы которых лежат в V _1, и множество V ₁ не может быть расширено так чтобы, G ₁ остался связным.

Пример. Граф, изображенный на рис. 5.14, имеет три компоненты связности.

Рис. 5.14