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 ta 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 một đoạn đường, người bưu tá phải nghĩ cách để tìm ra đườ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 (điểm O). Dựa vào nguyên lí giải bài toán vẽ một nét, không đi lặp lại con đường nhiều lần, thì trên hình vẽ này tối đa chỉ phải có 2 điểm lẻ.

Nhưng trên hình vẽ này lại có bốn điểm A, C, E, G là các điểm lẻ nên để trên lộ trình không đi lặp lại một đoạn đường nào là không thể được. Thế nhưng cũng có thể chọn cách đi nào đó mà sự lặp lại là ít nhất.

Cách thứ nhất: Theo hình 1 ta sẽ 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 vẽ trên. Nếu tính cả những đoạn mới vẽ thì mỗi điểm lẻ trên hình vẽ trở thành điểm chẵn, do đó có thể vẽ bằng một nét. Cách vẽ là: O → B → C → G → A → B → C → D → E → F → O. Theo cách vẽ này ở những đoạn có vẽ thêm là đoạn đường phải lặp lại. Nhưng cách đi này đã là tốt nhất chưa? Chưa, vì trong ABCGA độ dài các đoạn trùng lặp lại dài hơn các đoạn khác.

Cách đi thứ hai: Ta xoá 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 không thể không có sự trùng lặp bằng một nét, nhưng đoạn vẽ thêm nghĩa là đoạn đi trùng lặp lại ngắn hơn. Bây giờ 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 số đoạn trùng lặp, đây là cách đi trùng lặp có đoạn đường đi ngắn nhất. Đây là cách đi mà trong lộ trình phần trùng lặp không vượt quá phần không trùng lặp.

Vì sao phải nghiên cứu vẫn thạch và các hố vẫn thạch?

Đối với các nhà khoa học, vẫn thạch quả thực là "Tiêu bản thiên thể" khó tìm được. Do đó các nhà khoa học rất coi trọng nghiên cứu những "tặng vật" từ...

Tại sao có đoàn tàu trên không chạy ở hai bên dầm thép?

Bạn đã bao giờ thấy loại tàu điện trên không mà đoàn tàu lại chạy ở hai bên đầm thép chưa? Hiện nay, ở Mỹ đang khai phá và thử nghiệm loại phương tiện...

Thế nào là hạt cơ bản?

Vào đầu thế kỷ XX, người ta tìm thấy nguyên tử là do điện tử và hạt nhân nguyên tử tạo nên. Nguyên tử đã bé nhưng hạt nhân nguyên tử lại còn bé hơn...

Sao Hải vương được phát hiện nhờ toán học như thế nào?

Có chín hành tinh lớn trong hệ Mặt Trời. Hầu như việc phát hiện mỗi hành tinh đều gợi sự chú ý đặc biệt của mọi người.

Có phải nam thông minh hơn nữ?

Chuyện này quả là khó nói. Về tổng thể, trí thông minh của nam và nữ tương đương nhau, tuy nhiên, mang các sắc thái khác nhau.

Đế quốc Ôt-tôman ra đời như thế nào?

Giữa thế kỷ XIII, Tiểu Á rơi vào tình trạng hỗn loạn. Đế quốc Đông La Mã hùng bá Tiểu Á mấy thế kỷ lúc này đang lấy Ni-xê làm cứ điểm đấu tranh giành...

Con người có "mắt thứ ba" không?

Trong Tây Du Kí có thần Nhị Lang võ thuật rất cao cường, đấu ngang ngửa với Tôn hành giả. Trước trán Nhị Lang có con "mắt thứ ba".

Vì sao năng lượng điện hạt nhân lại có tương lai phát triển?

Hiện nay, rất nhiều quốc gia có nhà máy điện hạt nhân. Số quốc gia đang gia nhập vào danh sách này ngày càng nhiều...

Tại sao camera khi quay không cần lấy tiêu cự cũng không cần xem xét độ sáng?

Hiện nay máy quay camera (đây là pickup camera không phải máy ảnh, tức camera thông thường - chú thích của người dịch) vẫn chưa phải là phổ biến, vẫn...