TAILIEUCHUNG - 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 .

• Toán học
• Chu trình Hamilton
• thuật toán
• đồ thị
• ứng dụng cây
• hàm trên đồ thị
• Lý thuyết đồ thị
• Đường đi Hamilton
• Đồ thị Hamilton
• Định nghĩa về chu trình Hamilton
• Định nghĩa về đường đi Hamilton
• Đường Hamilton
• bài toán mã đi tuần
• chu trình vô hướng hamilton
• Luận án Tiến sĩ Toán học
• Luận án Tiến sĩ
• Cơ sở toán học cho tin học
• Thuật toán đa thức xác định chu trình Hamilton
• Bài giảng Lý thuyết đồ thị
• Đồ thị Euler
• Kiểm tra đồ thị Hamilton
• Bài toán người du lịch
• Bài toán tối ưu tổ hợp
• Đường Hamilton
• Thuật toán nhánh cận giải TSP
• Bài toán người du lịch và thuật toán nhánh cận
• Bài toán tối ưu liên quan đến đường Hamilton
• Đồ thị tách cực
• Đồ thị tách cực phi Hamilton tối đại
• Bậc cực tiểu
• Chu trình euler
• thuật toán tìm chu trình
• đồ thị liên thông
• Bài toán lý thuyết đồ thị
• Bài toán luông
• toán rời rạc
• bài tập học phần
• Đường đi đồ thị
• Đồ thị phẳng
• Bài toán tô màu đồ thị
• Tài liệu Thực hành
• Đồ thị Chu trình
• Lý thuyết đồ thị chu trình
• Đường đi Euler
• Đồ thị ơ2= N
• Đồ thị đơn
• Bài toán HC
• Thuật toán đa thức
• Xây dựng thuật toán đa thức
• Đồ thị 2 phần
• Đồ thị đầy đủ
• Đồ thị rỗng
• tài liệu toán học
• phép toán hedetniemi
• bài giảng toán học
• các bài toán về đường đi
• Bài giảng Toán rời rạc
• Thuật toán Dijkstra
• giáo trình đồ thị
• tài liệu về đồ thị
• ứng dụng của đồ thị
• Đường đi trên đồ thị
• Bài toán đường đi tốt nhất
• Bài giảng Cấu trúc rời rạc
• Cấu trúc rời rạc
• Chu trình và đường đi Euler
• Chu trình và đường đi Hamilton