2. BÀI TOÁN NGƯỜI ĐƯA THƯ
Luyện tập: Giải bài toán người đưa thư đối với đồ thị có trọng số trên Hình 2.32.
Bài Làm:
Đồ thị chỉ có 2 đỉnh bậc lẻ là A và D nên ta có thể tìm được một đường đi Euler từ đến D.
Một đường đi Euler từ A đến D là AEFABEDBCD và tổng độ dài của nó là: 7 + 9 + 10 + 2 + 8 + 16 + 15 + 3 + 4 = 74.
Để quay trở lại điểm xuất phát và có đường đi ngắn nhất, ta cần tìm một đường đi ngắn nhất từ D đến A theo thuật toán đã mô tả ở Mục 1.
Đường đi ngắn nhất từ D đến A là DCBA và có độ dài là 4 + 3 + 2 = 9.
Vậy chu trình cần tìm là AEFABEDBCDCBA và có độ dài là 74 + 9 = 83.
