исходногоPграфа на компоненты связности. Если положить, что число вершин в компоненте связности Xi равно ni, то число ребер в таком графе не превосходит . Данная величина достигается в том случае, когда каждая из компонент связности является полным подграфом. Допустим, что среди компонент связности найдутся хотя бы две,Pкоторые имеют более одной вершины, например n2 n1 > 1. Перенесем одну вершину из . Легко видеть, что это увеличивает число ребер в модифицируемом исходном графе с k компонентами связности. Отсюда следует, что максимальное число ребер должен иметь граф, состоящий из k-1 изолированной вершины и одного полного подграфа с n-k+1 вершинами.
Доказательство. Рассмотрим прямое разложениеPГ=
Утверждение 7.5.2. Пусть Г(X,U,Ф) является простым графом с n вершинами и k компонентами связности. Число ребер в таком графе не может превосходить величины Cbn-k+1=(n-k+1)(n-k)/2.
Количество компонент связности находится в определенном отношении с основными параметрами графа числом вершин и его ребер.
Утверждение 7.5.1. Каждый неориентированный граф распадается единственным образом в прямую сумму своих компонент связности.
x3, то очевидно, что вершина x1 связана с x3. Следовательно, существует такое разложение множества вершинна попарно непересекающиеся подмножества, что все вершины в каждом Xi связаны, а вершины из различных Xi не связаны. Тогда можно записать разложениеграфа Г(X,U,Ф) на непересекающиеся связные подграфы Г(Xi,Ui,Ф). Вследствие попарного непересечения подграфов, разложение называется прямым, а сами подграфы называются компонентами связности графа. ТакимPобразом, справедливо следующее утверждение.
x1, x2 X отношение ~ будет выполняться, т.е. x1 ~ x2, если эти вершины связанные. Введенное отношение является отношением эквивалентности. Действительно, если вершина x1 связана с x2, а вершина x2 связана с
Пусть псевдограф Г(X,U, Ф) является неориентированным. ДвеPвершины x1, x2 X называются связанными, если существует маршрут x1 в x2. Определим на множестве вершин X бинарное (~) отношение. Для
Комментариев нет:
Отправить комментарий