Giải bài toán người đưa thư đối với đồ thị có trọng số trên Hình 2.35

Giải Chuyên đề Toán 11 Kết nối tri thức 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

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.