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