NGƯỜI ĐƯA THƯ NÊN ĐI ĐƯỜNG NÀO?
Một người đưa thư phải phát báo, đưa thư tới các gia đình trong khu tập thể gần bưu điện (xem sơ đồ của đoạn đường người này đi ở H1). Hàng ngày, anh ta xuất phát từ vị trí 0 ( bưu điện) đi qua tất cả các hang cùng ngõ hẻm để làm hết phận sự của mình. Nhưng, đoạn đường anh ta đi sẽ ngắn hơn nhiều nếu anh ta biết cách không lặp lại những con đường cũ. Đó chính là một bài toán thuộc ''1 nét vẽ'' với điểm xuất phát và điểm đích là 0 (bưu điện). Dựa vào điều kiện hình một nét vẽ mà chúng ta đã nghiên cứu ở trên muốn không bị lặp lại đường đi, số điểm lẻ chỉ có thể là 2. Nhưng ở hình bên có những 4 điểm lẻ: A, C, E, G. Như vậy không đi trùng đường là việc không thể làm được. Như vậy, làm cách nào để số lần lặp lại đường đi nhỏ nhất? Chúng ta có hai cách đi như sau:
Cách đi thứ nhất: Chúng ta thêm một số đường mới như nếu như tính cả các đường mới thêm này thì mỗi điểm trong sơ đồ trên đều trở thành điểm chẵn. Do vậy có thể vẽ được bằng một nét không lặp lại. Cách đi sẽ là: 0 -> A -> B -> C- > G-> A-> B -> C -> D -> E - > F -> O. Nhưng nếu đi theo đường này thì lại cần phải vẽ thêm đường tức là vẫn lặp đường. Cách đi này không phải là tối ưu. Ta thấy trong hình ABCG, độ dài của các đường vẽ thêm lớn hơn một số các đường không vẽ thêm.
Cách đi thứ hai: Chúng ta xóa tất cả các đường mới thêm ở bên cạnh BC, GC, CA mà thêm vào bên cạnh AG một đường mới. Như vậy ta vẫn có thể vẽ hình bằng một nét không lặp lại nhưng đã rút bớt các đường mới thêm. Lúc này, cách đi sẽ là O -> A -> B-> C - > D -> E - > G-> A -> C -> D -> E- > F -> O.
Cách đi thứ hai này ngắn hơn cách đi thứ nhất và đây cũng là cách đi có số đường trùng lặp ít nhất. Bởi mỗi một phần được thêm đều không vượt quá chiều dài của những phần không được thêm.
