Bưu tá viên phải đi theo đường nào?
Người bưu tá ở một bưu cục thường phải phát thư từ, bưu kiện, báo chí đến các địa phương lân cận một trạm bưu điện nào đó, ví dụ như trình bày ở hình 1. Hằng ngày, ông xuất phát từ trạm bưu điện đặt tại điểm O, đi qua hết các đoạn đường lớn, đường ngang ngõ tắt để phân phát tới các bưu điện.
Để giảm bớt việc đi lặp lại nhiều lần trên cùng một đoạn đường, người bưu tá phải nghĩ cách tìm ra con đường ngắn nhất. Trên thực tế, đó chính là vấn đề vẽ một nét. Điểm khởi đầu và điểm kết thúc đều là trạm bưu điện, tức điểm O. Dựa vào nguyên lý giải bài toán vẽ một nét, nếu muốn không đi lặp lại đường nhiều lần thì trên hình vẽ này tối đa chỉ được có 2 điểm lẻ.
Nhưng trên hình vẽ lại có bốn điểm A, C, E, G là các điểm lẻ, nên không thể có lộ trình nào đi qua tất cả các đoạn đường mà không lặp lại đoạn nào. Tuy vậy, vẫn có thể chọn một cách đi sao cho phần lặp lại là ít nhất.
Cách thứ nhất: theo hình 1, ta vẽ tuyến đường đi như hình 2. Nếu ta vẽ thêm một vài đoạn mới vào hình, thì khi tính cả các đoạn mới ấy, mỗi điểm lẻ trên hình sẽ trở thành điểm chẵn, do đó có thể vẽ bằng một nét. Cách đi là: O → B → C → G → A → B → C → D → E → F → O. Theo cách này, những đoạn được vẽ thêm chính là các đoạn đường phải đi lặp lại. Nhưng cách đi này đã tốt nhất chưa? Chưa, vì trong ABCGA, độ dài các đoạn trùng lặp còn dài hơn các đoạn khác.
Cách đi thứ hai: ta xóa các đoạn AB, BC, CG ở hình 2, nhưng lại vẽ thêm A, G như hình 3. Tuy hình này vẫn không thể tránh hoàn toàn việc đi trùng lặp, nhưng đoạn vẽ thêm, nghĩa là đoạn đi lặp lại, ngắn hơn. Khi đó, cách đi sẽ là O → A → C → D → E → G → A → G → C → D → E → F → O.
Rõ ràng, so với cách thứ nhất, cách thứ hai giảm bớt độ dài các đoạn trùng lặp. Đây là cách đi có phần đường lặp lại ngắn nhất, tức trong lộ trình, phần trùng lặp không vượt quá phần không trùng lặp.
