2.28. Giải bài toán người đưa thư đối với đồ thị có trọng số trên Hình 2.42.
Bài Làm:
Đồ thị có hai đỉnh bậc lẻ là D và E nên ta có thể tìm được một đường đi Euler từ D và E (đường đi này đi qua mỗi cạnh đúng một lần).
Một đường đi Euler từ D đến E là DBACBECDE và tổng độ dài của nó là: 2 + 4 + 4 + 5 + 3 + 1 + 2 + 6 = 27.
Để 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ừ E đến D theo thuật toán đã mô tả ở Mục 1.
Đường đi ngắn nhất từ E đến D là ECD và có độ dài là 1 + 2 = 3.
Vậy một chu trình cần tìm là DBACBECDECD và có độ dài là 27 + 3 = 30.
