Bài 8: Một số bài toán tối ưu trên đ
thị trọng s
v1.0 173
BÀI 8: MỘT SỐ BÀI TOÁN TỐI ƯU TRÊN ĐỒ THỊ TRỌNG SỐ
Nội dung
Định nghĩa đồ thị có trọng số
Bài toán tìm cây khung nhỏ nhất
Bài toán tìm đường đi ngắn nhất
Giới thiệu Mục tiêu
Một trong những ứng dụng quan trọng của
lý thuyết đồ thị là nó cung cấp một số mô
hình tối ưu có nhiều ý nghĩa thực tế. Trên
những mô hình này, người ta đã nghiên cứu
khá nhiều những thuật toán hiệu quả và cài
đặt thuận tiện, được ứng dụng trong nhiều
lĩnh vực hiện đại.
Do thời lượng có hạn, trong bài này, chúng
tôi chỉ giới thiệu được hai mô hình tối ưu
tiêu biểu của lý thuyết đồ thị là bài toán tìm
cây khung nhỏ nhất và bài toán tìm đường đi
ngắn nhất. Một số mô hình tối ưu nổi tiếng
khác như bài toán ghép cặp, bài toán luồng
cực đại, ..., chúng tôi hy vọng sẽ được giới
thiệu trong những dịp thuận tiện hơn
Thời lượng học
6 tiết
Sau khi học bài này, các bạn có thể:
Hiểu rõ thế nào là đồ thị có trọng số.
Biểu diễn được đồ thị có trọng số trên máy
tính.
Sử dụng được thuật toán Kruskal, thuật
toán Prim để tìm cây khung nhỏ nhất.
Sử dụng được thuật toán Dijkstra để tìm
đường đi ngắn nhất.