May quá vẫn giữ bài này trên blog cá nhân =))))

Tác giả: SNOW ANGEL

Nguồn: VNOI (old :3 )

Bài này công thức là: M – N + K với N là số đỉnh, M là số cạnh và K lá số thành phần liên thông.
Chứng minh:
1) Trường hợp chỉ có 1 thành phần liên thông: Ta xây dựng cây khung, mất N-1 cạnh, còn lại M-N+1 cạnh, thêm 1 cạnh nào vào ta cũng có 1 chu trình cơ sở -> số chu trình cơ sở trong trường hợp này là M-N+1.

2) Trường hợp có K thành phần liên thông. Đồ thị chia thành h đồ thị con liên thông, với số đỉnh, số cạnh của mỗi đồ thị con lần lượt là N[i] và M[i].
Số chu trình cơ sở mỗi đồ thị con là trường hợp 1: M[i]-N[i]+1.
=> số chu trình cơ sở tất cả là: Sum{ M[i] – N[i] + 1) = M – N + K. (*)
trong đó sum{M[i]} = M sum{N[i]} = N và tổng (*) có K phần tử.

hay :3