Tiểu Luận đường đi trong mê cung và ứng dụng

MỤC LỤC

1_ Lời nói đầu Trang 02
2_Các thành viên trong nhóm Trang 04
3_Phần nội dung Trang 05
4_Chương I: Đại cương về đồ thị Trang 05
5_Chương II: Các bài toán tìm đường đi trong mê cung Trang 08
6_Chương III: Các bài toán ứng dụng . Trang 17
7_Kết luận Trang 24
8_Tài liệu tham khảo . Trang 25










LỜI NÓI ĐẦU


Lý thuyết đồ thị là ngành học được phát triển từ lâu nhưng lại có nhiều ứng dụng hiện đại. Những ý tưởng cơ bản của nó đã được nhà toán học Thụy sĩ vĩ đại Leonhard Euler đưa ra từ thế kỷ 18.
Đồ thị là một cấu trúc rời rạc gồm các đỉnh và các cạnh nối các đỉnh đó. Đây là công cụ hữu hiệu để mô hình hóa và giải quyết các bài toán trong nhiều lĩnh vực khoa học, kỹ thuật, kinh tế, xã hội, .
Môn lý thuyết đồ thị là môn học hấp dẫn, mang tính thực tế cao. Những vấn đề trong môn học như: các bài toán về đường đi, cây, mạng và các bài toán tô màu đã và đang được nhiều người quan tâm, nghiên cứu. Trong những vấn đề đó thì bài toán tìm đường đi, đặc biệt là bài toán tìm đường đi trong mê cung là một chủ đề khá thú vị, là chủ đề mang tính chất của một trò chơi nhưng lại có nhiều ứng dụng trong cuộc sống,ví dụ về một mẫu chuyện thần thoại Hi Lạp:
Ở đảo Crete có một quái vật đầu bò, mình người tên là Minotaus, chuyên ăn thịt người và súc vật. Nhà vua sai kiến trúc sư nổi tiếng Daedalus xây dựng một cung điện lớn, gồm rất nhiều hành lang và lối đi ngoắt ngéo mà bên trong khó có thể đi theo các hành lang để ra ngoài được để nhốt Minotaus ở đó. Hằng năm các nước chư hầu phải đưa người đến nộp cho quái vật ăn. Chàng dũng sĩ Theseus muốn tiêu diệt quái vật trừ họa cho muôn dân. Trước khi vào cung điện, chàng được gặp công chúa Ariadne. Công chúa đem lòng yêu Theseus nên đã tìm đến Daedalus hỏi kế giúp chàng khỏi lạc đường trong cung điện. Theo lời Daedalus, Ariadne đưa cho Theseus một cuộn chỉ. Nhờ vậy mà sau khi giết được Minotaur, Theseus đã ra khỏi cung điện mà không lạc đường.