Giáo trình Đồ thị và các thuật toán - Chương 5: Bài toán Euler và bài toán Hamilton

5.2 Bài toán người đưa thư Trung Hoa Xét đồ thị vô hướng liên thông G:= (V, E) có trọng số (tức là mỗi cạnh e € E ta gán một số tt(e) gọi là trọng lượng của cạnh e). Bài toán người đưa thư Trung Hoa (không được định hướng phát biểu rằng tìm một dây chuyền giữa hai đinh cho triớc a, b GV sử dụng mỗi cạnh của G ít nhất một lần và có độ dài nhỏ nhất (xem [44]). Nhiều bài toán về hành trình (người đưa thư, người giao sữa, người chào hàng, vv) có thể phát biểu ở dạng này. Trong trường hợp đồ thị có hướng, trong đó mỗi cung của G cần được sử dụng ít nhất một lần, bài toán có thể đưa về bài toán luồng với chi phí nhỏ nhất (bài tập). Từ đây về sau chúng ta chỉ xét đồ thị vô hướng. Không mất tính tổng quát có thể giả thiết đỉnh xuất phát a và định kết thúc b trên dây chuyền là trùng nhau. Trong trường hợp ngược lại, ta chỉ cần thêm một cạnh (a, b) với độ