- Các bài toán cần giải quyết trước khi đến bài này:
+ Tìm và liệt kê cầu của đồ thị bằng tarzan
+ Tìm đường đi dài nhất trên cây bằng 2 lần dfs/bfs (đường kính của cây)
- Đồ thị ban đầu có thể bao gồm nhiều cạnh cầu, nếu các cầu này không tồn tại thì đồ thị sẽ chỉ còn nhiều thành phần liên thông riêng biệt (số tplt = số cạnh cầu + 1), điều này có thể chứng minh bằng định nghĩa của cạnh cầu.
- Bây giờ, nếu ta xem mỗi thành phần liên thông là 1 đỉnh, các cạnh cầu sẽ là cạnh mới thì ta có thể tạo ra đồ thị mới có dạng cây (gồm m đỉnh, m-1 cạnh, không chứa chu trình)
- Dễ thấy nếu ta cắt một cạnh bất kỳ của cây, nó sẽ phân chia thành 2 tplt (giống với bài toán ban đầu)
- Xem xét một đoạn liên tục của cây như sau:
tplt1----tplt2----tplt3----tplt4----tplt5
-> các tplt là đỉnh của cây, các nét gạch nối là cạnh cầu
-> bài toán của chúng ta là thêm vào 1 cạnh để số cạnh cầu giảm tối đa, hãy thử nghĩ xem nên thêm cạnh ở đâu?
-> Trả lời: hãy thêm cạnh giữa tplt1 và tplt5, lúc này các cạnh cầu ở giữa khi mất đi thì đồ thị sẽ không bị chia ra nữa.
-> Như vậy với cây đã tạo, cần chọn ra một đoạn dài nhất, và ta sẽ thêm vào 1 cạnh ở 2 bên đoạn này, đây cũng là bài toán đường kính của cây, số cạnh cầu được giảm bằng đúng với độ dài đường kính này.
lehoang
Created at
5 likes