2.5 Связность и компоненты графа

Важным понятием в теории графов является связность. Две вершины v_i и v_j называются связанными в графе G, если в нем существует путь v_i - v_j. Вершина связана сама с собой.

Граф G называется связным, если в нем существует путь между каждой парой вершин. Например, граф, представленный на рис. 12, связный.

Рассмотрим несвязный граф G = (V, Е). Тогда множество вершин V графа G можно разбить на такие подмножества V₁, V₂, … ,V_p, что вершинно-порожденные подграфы <V_i>, i= 1, 2, . . р, связны, и никакая вершина подмножества V_i не связана ни с какой вершиной подмножества V_j, j ≠ i. Подграфы <V_i>, i=l, 2, ..., p, называются компонентами графа G. Легко видеть, что компонентой графа G является максимально связный подграф графа G, т. е. компонента графа G не является собственным подграфом любого другого связного подграфа графа G.

Например, граф G на рис. 13 не связен. Его четыре компоненты G₁, G₂, G₃, G₄ имеют множества вершин {v₁, v₂, v₃}, {v₄, v₅}, {v₆, v₇, v₈}, {v₉} соответственно.

Рисунок 13

Отметим, что изолированную вершину также следует рассматривать как компоненту, поскольку по определению вершина связана сама с собой. Кроме того, следует отметить, что если граф G связен, то он имеет только одну компоненту, которая является графом G.

Теперь рассмотрим некоторые свойства связных графов.

Теорема. В связном графе любые два пути максимальной длины имеютобщую вершину.

Теорема. Если граф G= (V, Е) связен, то граф G'= (V, Е - е), получающийся после удаления циклического ребра е, тоже связен.