TAILIEUCHUNG - BÀI 19: Một số ứng dụng của cây bao trùm

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. | 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 ei 1 i m- n 1 nghĩa là khôi phục lại cạnh ei trong G khi đó sẽ xuất hiện chu trình a - đâ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 Zj thì Xi chứa eị nhưng không chứa ej còn Xj chứa ej 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 3 a b c d Ơ I 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 .

• Toán học
• lý thuyết đồ thị
• ứng dụng của cây bao trùm
• đồ thị vô hướng
• tính liên thông của đồ thị
• cây bao trùm
• Bài giảng Lý thuyết đồ thị
• Giới thiệu Lý thuyết đồ thị
• Môn học Lý thuyết đồ thị
• Đại cương Lý thuyết đồ thị
• Hình thức thi Lý thuyết đồ thị
• tài liệu về lý thuyết đồ thị
• học lý thuyết đồ thị tốt
• phương pháp học lý thuyết đồ thị
• hàm trên đồ thị
• Đại cương về đồ thị
• Các mô hình đồ thị
• Thuật ngữ cơ bản của đồ thị
• Đường đi của đồ thị
• Sự liên thông đồ thị
• Biểu diễn đồ thị trên máy tính
• Sự đẳng cấu của đồ thị
• Phương pháp biểu diễn đồ thị
• Biểu diễn đồ thị bằng ma trận kề
• Đồ thị Euler
• Đồ thị Hamilton
• Chu trình Hamilton
• Kiểm tra đồ thị Hamilton
• Đơn đồ thị đặc biệt
• Đồ thị bánh xe
• Đồ thị con
• Mô hình đồ thị