Giải luyện tập trang 49 chuyên đề Toán 11 Kết nối

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