Khi giới thiệu đường đi và chu trình Euler trong đồ thị, thầy Hoàng Chúng trong quyển “Graph và giải toán phổ thông” có đưa ra một bài toán khá thú vị như sau:
Một ông vua đã xây dựng một lâu đài với nhiều phòng để cất giấu một báu vật. Người ta tìm thấy sơ đồ của lâu đài với lời dặn: muốn tìm thấy báu vật, chỉ cần từ một trong các phòng ngoài cùng (như phòng 1, 2, 6, 10 …) đi qua tất cả các cửa phòng, mỗi cửa chỉ một lần. Báu vật được giấu sau cánh cửa cuối cùng. Hãy tìm nơi giấu báu vật.
Nếu ta xem mỗi phòng trong lâu đài là một đỉnh và cửa nối hai phòng với nhau là cạnh nối hai đỉnh thì ta được một đồ thị liên thông. Bài toán đơn giản là tìm một đường đi Euler có đỉnh bắt đầu là một trong các đỉnh tương ứng với phòng nằm bên ngoài và đỉnh kết thúc chính là căn phòng chứa kho báu. Đến đây, theo định lý về điều kiện cần và đủ để tồn tại đường đi Euler trong đồ thị, ta chỉ cần tìm hai đỉnh bậc lẻ là hoàn tất. Với các đỉnh nằm bên ngoài, chỉ có đỉnh 6 có bậc lẻ (bậc 3). Với các đỉnh còn lại, ta thấy chỉ còn đỉnh 18 có bậc lẻ (bậc 3). Do đó, đồ thị có đường đi Euler và đường đi này xuất phát ở đỉnh 6, kết thúc ở đỉnh 18. Nơi giấu kho báu chính là căn phòng 18.
Rõ ràng, nếu chưa biết về Lý thuyết đồ thị và đường đi Euler thì bài toán tương đối phức tạp vì số phòng và số cửa là khá lớn. Làm theo cách “thử và sai” sẽ mất nhiều thời gian và hiển nhiên là lựa chọn chưa hợp lý. Nói về các trò chơi liên quan đến đường đi và chu trình Euler, ngoài trò chơi về mê cung, ta còn một trò chơi quen thuộc hơn đã được giới thiệu trong bài 2 của bài giảng E – learning, đó là trò chơi vẽ hình bằng một nét bút liền. Thông qua các trò chơi nói trên, ta thấy được nhiều ứng dụng gần gũi của Lý thuyết đồ thị trong thực tế.
Không có nhận xét nào:
Đăng nhận xét