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