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.

Làm thế nào để tính số lượt trận đấu cho thể thức thi đấu loại trực tiếp?

Giả sử ở trường bạn đang tổ chức một cuộc thi đấu cờ theo thể lệ đấu loại trực tiếp, ví dụ số người ghi tên thi đấu là 50, bạn có thể tính được số...

Tại sao tàu điện ngầm ngày càng trở nên quan trọng trong giao thông thành phố?

Theo dự tính, đến đầu thế kỷ XXI, số thành phố có trên một triệu dân trên toàn thế giới sẽ tăng lên hơn 400, các phương tiện giao thông truyền thống...

Đa số động vật đều ngủ đông, tại sao hải sâm lại phải ngủ hè?

Mỗi khi mùa đông đến, không ít những động vật do nguồn thức ăn khan hiếm liền chui vào những nơi như hốc cây, lòng đất, hang động..., để ngủ đông.

Các nhà máy nên bố trí bao nhiêu công nhân sửa chữa bảo dưỡng thì hợp lí?

Ở các nhà máy ngoài các bộ phận quản lí, sản xuất, tiêu thụ sản phẩm còn có bộ phận chuyên việc bảo dưỡng sửa chữa máy móc thiết bị, để có thể kịp...

Vì sao thợ hàn phải che mặt nạ?

Khi đi qua chỗ hàn điện hoặc hàn hơi, bạn sẽ nhìn thấy ánh sáng lóe lên, tàn lửa bắn ra tung tóe. Chỉ cần đứng ở đó nhìn chăm chú trong 1-2 phút thì...

Vì sao hệ thống miễn dịch của cơ thể có thể tiêu diệt được vi khuẩn?

Trong cơ thể người bình thường, hệ thống miễn dịch rất hoàn chỉnh. Khi cơ thể bị vi khuẩn gây bệnh tấn công, hệ thống miễn dịch sẽ được kích hoạt và...

Tại sao cà phê và chè có tác dụng làm tỉnh táo đầu óc?

Cà phê, chè và ca cao vốn được coi là ba loại đồ uống nổi tiếng trên thế giới. Cà phê là do quả cà phê thuộc thực vật họ khiếm thảo gia công thành,...

Tại sao trong phòng ngủ của trẻ nhỏ không nên lắp đèn huỳnh quang?

Một nhà khoa học người Mỹ đã phát minh ra bóng đèn trắng. Đây không chỉ là một kỳ tích trong lịch sử khoa học kỹ thuật mang lại cho cuộc sống loài người những tiện ích lớn lao.

Tại sao các công trình sư có thể "nhìn thấy" ứng suất ở bên trong vật liệu?

Các ngoại lực mà kết cấu công trình phải chống chịu trong quá trình sử dụng, thường bao gồm trọng lượng bản thân kết cấu, phụ tải do hoạt động của con...