tailieunhanh - Giáo trình lý thuyết đồ thị - Bài 19

Tham khảo tài liệu 'giáo trình lý thuyết đồ thị - bài 19', khoa học tự nhiên, toán học phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả | BÀI 19 . Một số ứng dụng của cây bao trùm 1 Kiểm tra tính liên thông của một đồ thị Đồ thị là liên thông khi và chỉ khi nó có cây bao trùm. 2 Xây dựng hệ cơ sở của các chu trình. Trước hết giả thiết rằng đồ thị liên thông G V E có n đỉnh và m cạnh. Trong trường hợp đồ thị không liên thông thì ta xét từng thành phần liên thông. Để xây dựng hệ cơ sở các chu trình thuộc G ta tiến hành hai bước sau đây 1. Xây dựng cây bao trùm T của G. Giả sử trong quá trình xây dựng cây bao trùm T ta đã bỏ đi các cạnh e1 e2 em-n 1 2. Xây dựng hệ chu trình cơ sở Lần lượt thêm vào cây T các cạnh Cị 1 i m- n 1 nghĩa là khôi phục lại cạnh Cị trong G khi đó sẽ xuất hiện chu trình ai - đây cũng là chu trình của đồ thị G. Sau đó lại xoá cạnh ei và thêm cạnh ei 1 vào. Ta nhận được các chu trình tương ứng a1 a2 Om-n b Hệ chu trình này độc lập vì V i j thì a chứa ei nhưng không chứa Cj còn a chứa Cj nhưng không chứa ei. Hơn nữa số các chu trình này là m - n 1 m - n p chu số của G số các chu trình độc lập cực đại. Vậy hệ chu trình tìm được là một cơ sở của các chu trình trong đồ thị G. Ví dụ Xét đồ thị vô hướng sau đây e Hình . Đồ thị và các cạnh bỏ đi n 5 m 8 p 1 Vậy c G 4 Một cây bao trùm T của G là Hình . Một cây bao trùm của đồ thị trên Ta nhận được một hệ chu trình cơ sở a1 a b d 2 a b e d a a b c d a4 a b c e d . Cây bao trùm nhỏ nhất Bây giờ ta xét bài toán tổng quát tìm cây bao trùm. . Bài toán cây bao trùm nhỏ nhất Cho đồ thị vô hướng G với tập cạnh E và hàm trọng số c E N. Hãy tìm cây bao trùm T của G sao cho tổng trọng số của các cạnh của T đạt giá trị nhỏ nhất. Chẳng hạn như xây dựng một hệ thống đường dây tải điện từ trạm phát điện đến các nơi tiêu thụ nối các máy tính trong một mạng . sao cho dây điện sử dụng là ít nhất. . Các thuật toán tìm cây bao trùm nhỏ nhất Giả sử G là một đồ thị vô hướng liên thông và có trọng số. Khi đó đồ thị G có cây bao trùm và sẽ có cây bao trùm nhỏ nhất. Ta có thể dùng các thuật toán sau đây để tìm cây bao trùm nhỏ nhất .