Mình thấy trên mạng thấy các anh chỉ thế này mà không hiểu.
Mình thấy trên mạng thấy các anh chỉ thế này mà không hiểu.
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