Bài 2.17 trang 49 Chuyên đề học tập Toán 11 Kết nối tri thức
Giải Chuyên đề Toán 11 Bài 10: Bài toán tìm đường tối ưu trong một vài trường hợp đơn giản - Kết nối tri thức
Bài 2.17 trang 49 Chuyên đề Toán 11: Giải bài toán người đưa thư đối với đồ thị có trọng số trên Hình 2.35.
Lời giải:
Vì đồ thị Hình 2.35 là liên thông và các đỉnh đều có bậc chẵn (ở đây chỉ có đỉnh A và đỉnh F có bậc là 2, các đỉnh còn lại đều có bậc 4) nên đồ thị này có chu trình Euler.
Một chu trình Euler xuất phát từ đỉnh A là ABCDBEDFECA và tổng độ dài của nó là
3 + 5 + 8 + 6 + 4 + 2 + 3 + 9 + 7 + 4 = 51.
Vậy một chu trình cần tìm là ABCDBEDFECA và có độ dài là 51.
Lời giải bài tập Chuyên đề Toán 11 Bài 10: Bài toán tìm đường tối ưu trong một vài trường hợp đơn giản hay, chi tiết khác:
