2015-05-20
909
Пусть 
простой граф, 
число вершин, 
число ребер, 
количество связных компонент. Тогда 
. Причем, если в 
нет циклов, тогда 
.
Доказательство. Рассмотрим граф 
, в нем 
связных компонент. Из графа 
добавлением ребер будем получать граф . Добавим первое ребро, число связных компонент уменьшится на 1, добавим еще одно ребро, оно опять свяжет вершины, принадлежащие разным компонентам и их число уменьшится на 1.
Третье ребро можно добавить, как показано на рис. 16, соединяя вершины, принадлежащие одной связной компоненте, в этом случае число связных компонент не уменьшилось. Можно добавить ребро, соединяющее вершины из разных связных компонент, как показано на рис.17, в этом случае число связных компонент вновь уменьшилось на 1.
Рис. 16 Рис. 17
То есть добавление каждого нового ребра или уменьшает число связных компонент на 1, или оставляет его прежним. Добавление 
ребер уменьшит число связных компонент максимум на , поэтому .
Если в графе нет циклов, тогда каждое новое добавленное ребро должно соединять вершины из разных связных компонент, поэтому число их каждый раз уменьшается ровно на 1 и .
|
|
|
