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

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

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

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

Например, граф G на рис. 13 не связен. Его четыре компоненты G1, G2, G3, G4 имеют множества вершин {v1, v2, v3}, {v4, v5}, {v6, v7, v8}, {v9} соответственно.

Рисунок 13

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

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

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

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

< Предыдущая		Следующая >