Пример. Пусть множество треугольников. Определим на S бинарное ~ отношение. Будем считать, что для треугольников Да, Ab е 5выполняется отношение Да ~ Ab, если их площади равны. Данное отношение является отношением эквивалентности.

6.5. Связные компоненты

Пусть псевдограф Г= (X, U, Ф) является неориентированным. Две вершины хь х2 е X называются связанными, если существует маршрут изХу вх2. Определим на множестве вершин ЛГбинарное ~ отношение. Для xlt х2& X отношение ~ будет выполняться, т.е. Ху ~ х2, если эти вершины связанные. Введенное отношение является отношением эквивалентности. Действительно, если вершина Ху связана с х2, а вершина х2 связана с х3, то очевидно, что вершинах! связана с х3. Следовательно, существует такое разложение множества вершин

X=[JXt

на попарно непересекающиеся подмножества, что все вершины в каждом Д связаны, а вершины из различных Дне связаны. Тогда можно записать разложение

r=\jruc„uit0)

графа Г= (X, U, Ф) на непересекающиеся связные подграфы Г= (Xit Uj, Ф). Вследствие попарного непересечения подграфов, разложение называется прямым, а сами подграфы называются компонентами связности графа Г. Таким образом, справедливо следующее утверждение.

• Утверждение 6.5.1. Каждый неориентированный граф распадается единственным образом в прямую сумму своих компонент связности.

Количество компонент связности находится в определенном отношении с основными параметрами графа — числом его вершин и ребер.

- Утверждение 65.2. ПустьГ= (X, U, Ф) является простым графом с п вершинами и £ компонентами связности. Число ребер в таком графе не может превосходить величины Cf k+l =

= (n-k + l)(n-k)/2.

Доказательство. Рассмотрим прямое разложение

к

Г= ]Г(Хри1гФ) исходного графа на компоненты связности.

Если положить, что число вершин в компоненте связности рав-

к ,

но л„ то число ребер в таком графе не превосходитДанная

величина достигается в том случае, когда каждая из компонент связности является полным подграфом. Допустим, что среди компонент связности Г(Хп Ur Ф) найдутся хотя бы две, которые имеют более одной вершины, например щгщ > 1. Перенесем одну вершину из /\ в Г2. Легко видеть, что это увеличивает число ребер в модифицируемом полном графе, с к компонентами связности. Отсюда следует, что максимальное число ребер должен иметь граф, состоящий из к — 1 изолированной вершины и одного полного подграфа с п — к + 1 вершинами.

• Следствие. Граф с п вершинами и числом ребер, большим чем связен.

6.6. Выделение компонент связности

Рассмотрим алгоритм нахождения числа компонент связности, а также выделения этих компонент на неориентированном графе. Подобным образом решается задача и для ориентированного графа. В основу рассматриваемого алгоритма 6.3 выделения компонент связности положена описанная ранее техника поиска в глубину на графе Г(Х, U, Ф). Структура алгоритма 6.3 является модификацией в сторону упрощения основного алгоритма 6.1 поиска в глубину. Работа алгоритма 6.3 направлена на формирование вектораметок вершин х е X графа. Элементу Магк[х] присваивается общий номер той компоненты, которой принадлежит вершинах е X. Сложность алгоритма 6.3, как и алгоритма 6.1, составляет + \U\).

Алгоритм 6.3. Выделение связных компонент неориентированного графа

for v е Xdo Mark[v]= 0; {Начальнаяустановка} count = 0; {Счетчик числа компонент) for v & Xdo ifMark[vb 0 then begin count = count + 1; Component, count); end;

Procedure Component(x, count): Mark[x] = count;

for v е Adj[x] do if Mark{vY 0 then Component, count);

end;

Программная реализация выделения компонент связности представлена в алгоритме 6.4, который близко соотносится с соответствующим множественным описанием алгоритма 6.3. Рассмотрим пример расчета по программе алгоритма 6.4 выделения компонент связности графа, представленного на рис. 6.14.

Рис. 6.14. Пример выделения компонент связности графа

Для программы алгоритма 6.4 исходные данные структуры смежностиграфа на рис. задаются в текстовом файле

Connect.in. Структура (правило) заполнения файла одинакова с той, которая описана в рассмотренном примере поиска в глубину при расчете по программе алгоритма 6.2.

Данные файла Connect.in для примера на рис. 6.14:

11

Результаты расчетов сохраняются в выходном файле Соп-

nect.out со следующей структурой:

1 2 9 8 12 14 з 4 7 15 21 — номера вершин графа;

номера компонент связности.