Bài toán vẽ 1 nét và Vận trù học

Vẽ 1 nét và Vận trù học

Giới thiệu
Vẽ 1 nét (V1N) là 1 trò chơi có từ lâu, với thách đố dùng bút liên tục không nhấc khỏi giấy vẽ các hình ( từ đơn giản đến phức tạp ).
V1N đã phát triển lý thuyết đồng thời ứng dụng vào thực tế thành nhiều bài toán rất hay. Thí dụ: “Bài toán qua cầu”, “Bài toán đưa thư” ...
Vận trù học là môn học rất rộng, bao hàm cả lý thuyết toán học ( trong đó có ứng dung các “Bài toán V1N”) và nhiều môn học liên quan.
Bài này giới thiệu một vài bài toán đơn giản để mọi người tham khảo.

1/-Bài toán Vẽ1 nét
Hình 1 dưới đây là 1 số bài V1N







Sau khi vẽ thử, bạn sẽ thấy các hình 1a, 1d, 1e đều có thể vẽ băng 1 nét; Còn các hình 1b, 1c không thể vẽ được nếu chỉ 1 nét (Tất nhiên đây là “bài toán nghiêm chỉnh” chứ không phải dùng “mẹo vặt” .
Thí dụ: Bài 1a có đường vẽ như sau

Nhận xét – rút ra “qui tắc của Bài toán V1N”
Gọi số “Đầu mối”- nơi có > 2 đường
Giao nhau – là N trong đó:
Nl là điểm có số lẻ nửa đường thẳng hoặc
Cong đi qua;
Nc là điểm có số chẵn nửa đường thẳng
hoặc cong đi qua;
-Nếu Nl = 0 (thí dụ hình 1d) thì nét vẽ có thể đi bắt đầu từ bất kỳ điểm nào; cuối cùng lại về đểm xuất phát.
- Nếu Nl = 2 (thí dụ hình 1a, 1e) thì nét vẽ có thể đi bắt đầu từ 1 trong 2 đầu mối lẻ, kết thúc tại đầu mối thứ 2.
- Nếu Nl > 2 (thí dụ hình 1b, 1c) thì không thể vẽ được nếu chỉ 1 nét. Bài toán vô nghiệm.



Ngay cả hình phức tạp như hình 3
Vẫn có thể V1N. Bạn hãy thử vẽ



Bài “Toán qua cầu”
Một khách du lịch muốn vào thăm đảo
Và muốn thăm đủ 5 chiêc Cầu (Hình 4)
Nhưng không muốn đi trùng cầu nào 2 lần.
Bạn hãy vẽ đường đi cho khách đó !

Giải:
Sơ đồ hóa 5 chiếc cầu và vùng khách muốn
Đi mhư hình 5. Ta thấy tương tự như
“Bài toán V1N” nêu trên: Lộ trình khách đi
Có 2 đầu mối lẻ (Nếu Nl = 2)
Vậy
- Nếu Khách đi từ vùng A Qua đủ
5 cầu không trùng cầu nào 2 lần
thì Khách phải dừng tại đảo.
- Nếu Khách muốn quay về A thi
Băt buộc phải qua cầu số 2 lần thứ
Hai.
- Nếu Khách muôn sang B, hoặc C
Thì phải lặp lai cầu 1 hoặc cầu 3.

2/-Vận trù học từ trò chơi đến ứng dụng thức tế

* Bài toán “qua cầu” nêu trên là một ứng dụng đã được nhiểu Nhà Toán học (Vận trù học) sử dụng. Bài toán đó phát triển bổ sung thêm câu hỏi :
- Nếu khách quay về A thì đi đường nào ngăn nhất ? Trả lời : đi lại cầu số 2
- Nếu Khách muôn sang B, hoặc C ? rả lời : phải lặp lai cầu 1 hoặc cầu 3 để đường đi ngắn nhất.

* Bài toán “Người đưa thư”;
Giả sử có bản đồ khu phố như hình 6, Người đưa thư từ TT Bưu điện X phải phát thư/ báo đến 8 điểm (1 - 8). Hỏi lộ trình Người đưa thư cần đi như thế nào có lợi nhất (nhanh nhất, quãng đường ngắn nhất ) ?
















Gải:
Sơ đồ hóa đường phố và các điểm cần đến của “Người đưa thư” (Hình 7a); cụm cần đến tập trung nhiều nhất là cụm số 4, 5, 6, 7 và số 8, điểm số 4, 5 và 7 ở vào nút lẻ mà khoảng cach giữa 5 và 6 là ngắn nhất, nên nếu đi trùng 2 lần cũng sẽ lợi nhất. Vậy sơ đồ 7b là lộ trình ngắn nhất có thể cho “Người đưa thư”
Ghi chú :
Thực tế thì “Người đưa thư” còn phải tính đến các yếu tố khác như thời tiết, thời điểm có trục nào hay tắc đường ( Như VN ta) để chọn lộ trình lợi nhất. Nhưng Lộ trinh 7b là ngắn nhất ( về độ dài)
Lộ trình cũng có thể đi thẳng trước ( ngược chiều ) nhưng độ dài không đổi
Đề bài cũng có thể thay là lộ trình của “Xe phun nước”, hoặc “Xe quét rác”.