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

Пусть псевдограф является неориентированным. Две вершины называются связанными, если существует маршрут из в Определим на множестве вершин бинарное отношение. Для отношение будет выполняться, т. е. если эти вершины связанные. Введенное отношение является отношением эквивалентности. Действительно, если вершина связана с а вершина связана с то очевидно, что вершина связана с Следовательно, существует такое разложение множества вершин

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

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

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

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

• Утверждение 6.5.2. Пусть является простым графом с вершинами и к компонентами связности. Число ребер в таком графе не может превосходить величины

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

Если положить, что число вершин в компоненте X] связности равно то число ребер в таком графе не превосходит Данная величина достигается в том случае, когда каждая из компонент связности является полным подграфом. Допустим, что среди компонент связности найдутся хотя бы две, которые имеют более одной вершины, например Перенесем одну вершину из Легко видеть, что это увеличивает число ребер в модифицируемом полном графе с к компонентами связности. Отсюда следует, что максимальное число ребер должен иметь граф, состоящий из изолированной вершины и одного полного подграфа с вершинами.

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