Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ
Tải xuống
Định nghĩa: Trong đồ thị liên thông G, nếu ta loại bỏ cạnh nằm trên chu trình nào đó thì ta sẽ được đồ thị vẫn là liên thông. Nếu cứ loại bỏ các cạnh ở các chu trình khác cho đến khi nào đồ thị không còn chu trình (vẫn liên thông) thì ta thu được một cây nối các đỉnh của G. Cây đó gọi là cây khung hay cây bao trùm của đồ thị G. Tổng quát, nếu G là đồ thị có n đỉnh, m cạnh và k thành phần liên thông thì áp dụng thủ. | TOÁN RỜI RẠC - CÂY - PHẦN 2 CÂY KHUNG VÀ BÀI TOÁN TÌM CÂY KHUNG NHỎ NHẤT. 6.2.1. Định nghĩa Trong đồ thị liên thông G nếu ta loại bỏ cạnh nằm trên chu trình nào đó thì ta sẽ được đồ thị vẫn là liên thông. Nếu cứ loại bỏ các cạnh ở các chu trình khác cho đến khi nào đồ thị không còn chu trình vẫn liên thông thì ta thu được một cây nối các đỉnh của G. Cây đó gọi là cây khung hay cây bao trùm của đồ thị G. Tổng quát nếu G là đồ thị có n đỉnh m cạnh và k thành phần liên thông thì áp dụng thủ tục vừa mô tả đối với mỗi thành phần liên thông của G ta thu được đồ thị gọi là rừng khung của G. Số cạnh bị loại bỏ trong thủ tục này bằng m-n k số này ký hiệu là v G và gọi là chu số của đồ thị G. 6.2.2. Bài toán tìm cây khung nhỏ nhất Bài toán tìm cây khung nhỏ nhất của đồ thị là một trong số những bài toán tối ưu trên đồ thị tìm được ứng dụng trong nhiều lĩnh vực khác nhau của đời sống. Trong phần này ta sẽ có hai thuật toán cơ bản để giải bài toán này. Trước hết nội dung của bài toán được phát biểu như sau. Cho G V E là đồ thị vô hướng liên thông có trọng số mỗi cạnh eeE có trọng số m e 0. Giả sử T Vt Et là cây khung của đồ thị G VT V . Ta gọi độ dài m T của cây khung T là tổng trọng số của các cạnh của nó m T m e . ee Et Bài toán đặt ra là trong số tất cả các cây khung của đồ thị G hãy tìm cây khung có độ dài nhỏ nhất. Cây khung như vậy được gọi là cây khung nhỏ nhất của đồ thị và bài toán đặt ra được gọi là bài toán tìm cây khung nhỏ nhất. Để minh hoạ cho những ứng dụng của bài toán cây khung nhỏ nhất dưới đây là hai mô hình thực tế tiêu biểu cho nó. Bài toán xây dựng hệ thống đường sắt Giả sử ta muốn xây dựng một hệ thống đường sắt nối n thành phố sao cho hành khách có thể đi từ bất cứ một thành phố nào đến bất kỳ một trong số các thành phố còn lại. Mặt khác trên quan điểm kinh tế đòi hỏi là chi phí về xây dựng hệ thống đường phải là nhỏ nhất. Rõ ràng là đồ thị mà đỉnh là các thành phố còn các cạnh là các tuyến đường sắt nối các thành phố tương ứng với phương án xây dựng .
