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

BỘ GIÁO DỤC VÀ ĐÀO TẠO ĐẠI HỌC ĐÀ NẴNG ---v--- TIỂU LUẬN ĐƯỜNG ĐI TRONG MÊ CUNG VÀ ỨNG DỤNG Giáo viên hướng dẫn: PGS.TSKH.Trần Quốc Chiến Học viên thực hiện: 1.Lê Châu Vân ( nhóm 1) 2.Đào Quang Hòa 3.Mai Xuân Kiên 4.Phạm Bình Nguyên 5.Lê Thị Bích Huy Lớp: Phương pháp Toán Sơ Cấp Khoá: 2009 - 2011 Kon Tum, tháng 03 năm 2010. 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. Trong thực tế, vẫn có nhiều mê cung còn tồn tại đến ngày hôm nay: chẳng hạn như mê cung bằng cây xanh ở Mỹ , do các hội viên giáo hội Tin Lành gốc Đức ở thành phố Garomonkia tạo ra; hoặc là mê cung trên đồng tiền đào được ở đảo Colito( Hy Lạp)… Mê cung Davis’ Mega (Mỹ) Mê cung, gắn với những câu chuyện thần thoại hay thực tế đã hấp dẫn rất nhiều nhà toán học.Ngày nay, mê cung được phổ biến thông qua hình thức toán học “ giải trí”_ là loại mê cung vẽ trên giấy để bạn đọc tự tìm lối ra, để độc giả từ một trò chơi mà mở mang trí lực. Qua đó, nhóm chúng em thấy việc nghiên cứu bài toán tìm đường đi trong mê cung là hết sức cần thiết vì nó có thể giải quyết được nhiều vấn đề khó khăn, phức tạp nảy sinh từ thực tế cuộc sống. Vì lí do đó, và theo sự phân công của thầy PGS.TSKH.Trần Quốc Chiến, nhóm em ( nhóm 1) chọn đề tài: '' Đường đi trong mê cung và ứng dụng '' để viết bài tiểu luận này. Các thành viên trong nhóm STT Họ tên học viên Công việc (Theo mục ) Ghi chú Nhận xét của Giáo Viên 1 Lê Thị Bích Huy Lời mở đầu Danh sách nhóm Chương I 2 Lê Châu Vân Chương I Chương II 3 Đào Quang Hoà Chương II Chương III 4 Phạm Bình Nguyên Chương II Chương III 5 Mai Xuân Kiên Chương III Kết luận Tài liệu tham khảo PHẦN NỘI DUNG CHƯƠNG I. ĐẠI CƯƠNG VỀ ĐỒ THỊ. I. Các khái niệm cơ bản. 1. Đồ thị vô hướng. v e w a. Định nghĩa: Đồ thị vô hướng G = (V, E) gồm một tập V các đỉnh và tập E các cạnh. Mỗi cạnh e E được liên kết với một cặp đỉnh v, w (không kể thứ tự). b. Ví dụ: Hình 1 Hình 2 H1: Đồ thị có 4 đỉnh, 7 cạnh H2: Đồ thị có 10 đỉnh, 10 cạnh 2. Đồ thị có hướng. w e v a. Định nghĩa: Đồ thị có hướng G = (V , E) gồm một tập V các đỉnh và tập E các cạnh có hướng gọi là cung . Mỗi cung e E được liên kết với một cặp đỉnh (v, w) có thứ tự. b. Ví dụ: H3: Đồ thị có 6 đỉnh, 8 cung * Ghi chú: Đồ thị vô hướng có thể coi là đồ thị có hướng trong đó mỗi cạnh e=(v,w) tương ứng với hai cung (v,w) và (w,v) * Cho đồ thị G = ( V,E ). Nếu cạnh e liên kết các đỉnh v, w thì ta nói cạnh e liên thuộc đỉnh v,w và ngược lại. 3. Mê cung. a Định nghĩa: Mê cung là một hệ thống gồm nhiều hành lang nối với nhau. Bài toán tìm đường đi trong mê cung là đứng từ vị trí s ( bên trong mê cung hoặc cửa vào ) tìm đường đi đến vị trí e ( cửa ra hoặc bên trong mê cung). B A Nếu biểu diễn mê cung bằng đồ thị, trong đó các hành lang là các cạnh, còn các giao điểm của chúng là các đỉnh thì ta có bài toán tìm đường đi trong đồ thị. Lưu ý rằng ta không biết trước sơ đồ của mê cung. b Ví dụ: Bài toán đặt ra là: Hãy vào bằng cửa A và tìm đường ra ở cửa B? II. Một số thuật toán tìm đường đi trong mê cung. Cho đồ thị G = (V,E) và đỉnh s,eV. Tìm đường đi từ s đến e a. Thuật toán Wiener. Xuất phát từ đỉnh s đi theo cạnh đồ thị theo nguyên tắc sau: Tại mỗi đỉnh chọn cạnh chưa đi qua trước đó . Nếu tại đỉnh nào đó mọi cạnh liên thuộc nó đã đi qua thì quay ngược lại cho đến khi gặp đỉnh có cạnh chưa qua. Bằng cánh này ta có thể đi qua tất cả các cạnh của đồ thị. Tuy nhiên để có thể thực hiện thuật toán này ta cần phải nhớ thứ tự các cạnh đã đi qua. b. Thuật toán Tarri. Xuất phát từ đỉnh s đi theo cạnh của đồ thị theo các nguyên tắc sau: Đánh dấu hướng đã đi qua của cạnh. Với mỗi đỉnh bậc lớn hơn hoặc bằng 3 của đồ thị, cạnh dẫn đến nó lần đầu tiên được đánh dấu đặc biệt. Tại mỗi đỉnh chọn cạnh chưa đi qua trước đó. Trường hợp các cạnh đã đi qua thì chọn cạnh đi theo hướng ngược lại. Cạnh đánh dấu đặc biệt là phương án cuối cùng nếu không còn cách nào khác. Bằng cách này ta đi qua tất cả các cạnh của đồ thị. Như vậy nếu đồ thị liên thông thì lúc nào đó ta sẽ đến đỉnh e. * Qua hai thuật toán, ta thấy để thực hiện được thuật toán viener thì cần phải nhứ thứ tự các cạnh đã đi qua, phải có phương tiện nhớ như "cuộn chỉ Ariadne" còn thuật toán của Tarri thì chỉ cần đánh dấu nên hiệu quả hơn: A B CHƯƠNG II. CÁC BÀI TOÁN TÌM ĐƯỜNG ĐI TRONG MÊ CUNG. - Bài toán 1: Cho mê cung như hình bên Bài toán đặt ra là tìm đường đi từ vị trí A đến vị trí B? Ta xây dựng đồ thị G từ mê cung trên bằng cách đặt các hành lang là các cạnh, các giao điểm của chúng là các đỉnh. Z Y X A B Ta có G = (V, E), trong đó V = . Ta xây dựng đồ thị G: Áp dụng thuật toán Wiener: Xuất phát từ A, ta cần đi đến B. Từ A ta có thể đi qua X hoặc Y. Giả sử ta rẽ phải qua X. Đây là ngõ cụt. Ta buộc phải quay lại cho đến khi gặp đỉnh có cạnh chưa đi qua là A. Tại A, ta không thể đi qua X được nữa. Do vậy ta chỉ có thể sang trái qua Y. Tại Y có 3 cạnh để đi. Giả sử từ Y ta đi tới Z. Đây là ngõ cụt. Theo thuật toán Wiener phải quay lại Y. Từ Y ta đi đến B. Vậy ta có thể đi từ A đến B theo đường: A→Y→B. B A -Bài toán 2: Cho mê cung như hình bên Bài toán đặt ra là: Hãy vào bằng cửa A và tìm đường ra ở cửa B? X3 X2 X1 X4 X7 X6 B A X5 X9 X10 X8 Tương tự như trên, ta xây dựng đồ thị G từ mê cung trên bằng cách đặt các hành lang là các cạnh, các giao điểm của chúng là các đỉnh. Ta có G = (V, E), trong đó V = . Ta xây dựng đồ thị G: A X2 X1 X9 X10 X8 B X3 X5 X7 X4 X6 dụng thuật toán Wiener: Xuất phát từ A, ta cần đi đến B. Từ A ta có thể đi qua X hoặc Y. Giả sử ta rẽ phải qua X. Đây là ngõ cụt. Ta buộc phải quay lại cho đến khi gặp đỉnh có cạnh chưa đi qua là A. Tại A, ta không thể đi qua X được nữa. Do vậy ta chỉ có thể sang trái qua Y. Tại Y có 3 cạnh để đi. Giả sử từ Y ta đi tới Z. Đây là ngõ cụt. Theo thuật toán Wiener phải quay lại Y. Từ Y ta đi đến B. Vậy ta có thể đi từ A đến B theo đường: A→Y→B. Áp dụng thuật toán Wiener: Xuất phát từ A, ta cần đi đến B. - Từ A ta đến X1 - Từ X1 ta có thể đi qua X2 hoặc X3. Giả sử ta rẽ trái qua X2. Đây là ngõ cụt. Ta buộc phải quay lại cho đến khi gặp đỉnh có cạnh chưa đi qua là X1. - Tại X1, ta không thể đi qua X2 được nữa. Do vậy ta chỉ có thể sang X3. - Từ X3 ta có thể đi qua X4 hoặc X5. Giả sử ta rẽ phải qua X4. Đây là ngõ cụt. Ta buộc phải quay lại cho đến khi gặp đỉnh có cạnh chưa đi qua là X3. - Từ X3 ta chỉ còn một cạnh chưa đi là qua X5 - Từ X5 ta có thể đi qua X6, X7 hoặc X8. Giả sử ta rẽ phải qua X6. Đây là ngõ cụt. Ta buộc phải quay lại cho đến khi gặp đỉnh có cạnh chưa đi qua là X5. Tại X5 còn 2 cạnh là qua X7 hoặc X8, qua X7 gặp ngõ cụt nên phải quay lại và qua X8 Tại X8 có 3 cạnh để đi. Giả sử ta rẽ phải thì gặp B. Đây là cửa ra. Vậy ta có thể đi từ A đến B theo đường: A→X1→X3→X5→X8→B. A B -Bài toán 3: Cho mê cung A X1 X2 X3 X4 X5 X9 B X12 X8 X6 X10 X7 X11 X13 Tìm đường đi từ A đến B ?. Tương tự như trên, ta đặt các hành lang là các cạnh, các giao điểm của chúng là các đỉnh. Ta xây dựng đồ thị G = (V, E) từ mê cung trên với V = {A, X1, X2, X3, X4, X5, X6, X7, X8, X9, X10, X11, X12, X13,B}. A X1 X2 X7 X10 X12 X11 X13 X9 B X3 X4 X5 X8 X6 Áp dụng thuật toán Tarri: Xuất phát từ đỉnh A, ta cần đi tới B. Từ A có thể đi lên X1 hoặc xuống X2. Giả sử ta đi lên X1, đây là ngõ cụt nên phải quay lại A. Tại A ta chỉ có một con đường đi là tới X2. Do X2 là đỉnh bặc 3 nên cạnh AX2 phải được đánh dấu đặc biệt Tại X2 ta có thể đi lên X3 hoặc xuống X4. Giả sử ta đi lên X3, đây là ngõ cụt nên phải quay lại X2. Tại X2 có thể đi đến X4 hoặc về A. Theo thuật toán Tarri cạnh đánh dấu đặc biệt AX2 phải là phương án chọn cuối cùng. Như vậy ta phải đi đến X4 và đánh dấu đặc biệt ở X2X4 (vì X4 là đỉnh bậc 3) Tại X4 ta có thể đi lên X6 hoặc xuống X5. Giả sử ta đi xuống X5, đây là ngõ cụt nên phải quay lại X4. Tại X4 có thể đi đến X6 hoặc về X2. Theo thuật toán Tarri cạnh đánh dấu đặc biệt X2X4 phải là phương án chọn cuối cùng. Như vậy ta phải đi đến X6 và đánh dấu đặc biệt ở X4X6 (vì X6 là đỉnh bậc 3) Tại X6 ta có thể đi lên X7 hoặc xuống X8. Giả sử ta đi xuống X8, đây là ngõ cụt nên phải quay lại X6. Tại X6 có thể đi đến X7 hoặc về X4. Theo thuật toán Tarri cạnh đánh dấu đặc biệt X4X6 phải là phương án chọn cuối cùng. Như vậy ta phải đi đến X8 và đánh dấu đặc biệt ở X6X8 (vì X8 là đỉnh bậc 3) Cứ thực hiện như thế ta sẽ đi đến đỉnh cuối cùng là B. Như vậy sau khi đi qua tất cả các cạnh của đồ thị ta có thể tìm được đường đi từ A đến B như sau: A→X2→X4→X6→X7→X11→X13→B. A X1 X2 X7 X10 X12 X11 X13 X9 B X3 X4 X5 X8 X6 Ta minh hoạ đường đi như sau: -Bài toán 4: Cho mê cung Hãy tìm đường đi từ A đến M?. Tương tự, ta đặt giao điểm của các cạnh là các đỉnh, các hành lang nối các đỉnh là các cạnh. Ta có đồ thị G: Áp dụng thuật toán Tarri: xuất phát từ A đi đến M. Từ A ta có thể đi đến B hoặc C. Giả sử ta chọn đi đến B. Do B là ngõ cụt nên ta phải quay lại A. Khi đó tại A ta chỉ có thể đi đến C. Do C là đỉnh bậc 3 (ứng với mê cung thì C là ngõ giao của 3 hành lang) nên theo thuật toán Tarri ta phải đánh dấu đặc biệt cạnh đầu tiên dẫn tới đỉnh C là cạnh AC . Từ C ta có thể đi đến E hoặc D. Giả sử ta đi đến D, gặp ngõ cụt như vậy ta phải quay lại C. Tại C ta có thể đi đến E hoặc đi ngược về A. Nhưng theo thuật toán Tarri thì cạnh đánh dấu đặc biệt AC là phương án cuối cùng được chọn, nên từ C ta phải đi đến E. Do E là đỉnh bậc 3 nên cạnh dẫn đến E đầu tiên phải đánh dấu đặc biệt, cạnh CE được đánh dấu đặc biệt . Tại E giả sử ta đi đến F và do F là ngõ cụt nên ta phải quay lại E. Tương tự tại E ta phải đi đến G. Cạnh EG cũng được đánh dấu đặc biệt. Từ G có thể đi đến H hoặc I. Giả sử ta đi đến H. Cạnh GH được đánh dấu đặc biệt. Từ H có thể đi đến I hoặc J. Giả sử đi đến I. Cạnh HI được đánh dấu đặc biệt. Từ I đi đến J hoặc G. Giả sử đi đến J, cạnh IJ được đánh dấu đặc biệt. Tương tự tại J có thể đi đến K hoặc H. Giả sử đi đến K, cạnh JK được đánh dấu đặc biệt. Từ K có thể đi đến L hoặc M. Nếu đi đến L, do L là ngõ cụt nên ta phải quay lại K và đi đến M. Như vậy ta có thể đi từ A đến M như sau: A→C→E→G→H→I→ J→K→M. Ta minh họa đường đi trên đồ thị như sau: Ta biểu diễn đường đi trong mê cung trên như sau: Lối vào Lối ra * Bài tập tham khảo Lối ra Lối ra Lối vào CHƯƠNG III. CÁC BÀI TOÁN ỨNG DỤNG "ĐƯỜNG ĐI TRONG MÊ CUNG" 1. Bài toán sói, dê và cải. Bài toán. Một người cần chở sói, dê và cải qua sông bằng một thuyền nhỏ. Mỗi lần người chỉ chở được một thứ, hoặc sói, hoặc dê, hoặc cải và không được để sói đứng với dê hoặc dê đứng với cải mà không có người trông coi. Hãy tìm cách chở. Cách giải. Kí hiệu: n ( người ), s (sói ), d (dê) và c ( cải ). Ta lập đồ thị có hướng biểu diễn khả năng chuyển đổi trạng thái người, sói, dê và cải ở hai bên bờ sông, xuất phát từ bờ sông A và đến bờ sông B. Theo yêu cầu bài toán, mỗi nút trạng thái (ứng với một đỉnh trong đồ thị ) là một tập con của tập (nsdc) trừ các tập (sd), (nc), (dc) và (sn). Như vậy ta có các nút trạng thái là: nsdc, ndc, nsc, nsd, sc, nd, d, s và c. Áp dụng thuật toán Tarri để tìm đường đi từ nút A.nsdc đến nút B.nsdc. Theo l‎ập luận trên thì ta có các nút trạng thái ứng với các đỉnh ở bờ sông A là: A.nsdc, A.ndc , A.nsc , A.nsd, A.sc, A.nd, A.d, A.s, A.c và các nút trạng thái ứng với các đỉnh ở bờ sông B là: B.nsdc, B.ndc, B.nsc, B.nsd, B.sc, B.nd, B.d, B.s, B.c. A.nsdc A.ndc A.nsc A.nsd A.sc A.nd A.d A.s A.c B.nsdc B.ndc B.nsc B.nsd B.sc B.nd B.d B.s B.c Dòng sông Từ đó ta biểu diễn các nút trạng thái ở hai bên bờ sông như sau: Theo yêu cầu bài toán thì ta có các phương án sau: B.nsdc B.ndc B.nsc B.nsd B.sc B.nd B.d B.s B.c A.nsdc A.ndc A.nsc A.nsd A.sc A.nd A.d A.s A.c * Phương án 1: . - Xuất phát từ đỉnh A.nsdc ta đi đến đỉnh B.nd. - Từ đỉnh xuất phát A.nsdc ta đi đến đỉnh B.nd (Bờ sông A còn sc, bờ sông B có nd ). - Từ đỉnh B.nd ta đi đến đỉnh A.nsc (Khi đó bờ sông B còn d, bờ sông A có nsc ). - Từ đỉnh A.nsc ta đi đến đỉnh B.nsd (Khi đó bờ sông A còn c, bờ sông B có nsd ). - Từ đỉnh B.nsd ta đi đến đỉnh A.ndc (Khi đó bờ sông B còn s, bờ sông A có ndc). - Từ đỉnh A.ndc ta đi đến đỉnh B.nsc (Khi đó bờ sông A còn d, bờ sông B có nsc). - Từ đỉnh B.nsc ta đi đến đỉnh A.nd (Khi đó đi một mình qua bờ sông A có d). - Từ đỉnh A.nd ta đi đến đỉnh B.nsdc (Từ bờ sông A chở d sang bờ sông B là nsdc). Với cách chở này, ta có đường đi là: A.nsdc→B.nd→A.nsc→B.nsd→A.ndc→B.nsc→A.nd→B.nsdc. Như vậy trong phương án này, ta đã chở sói, dê và cải qua sông thỏa mãn yêu cầu bài toán. Rõ ràng trong cách chở này, một số đỉnh chúng ta không đi qua. Vì nếu đi qua thì sẽ không thỏa mãn được yêu cầu bài toán. * Phương án 2 B.nsdc B.ndc B.nsc B.nsd B.sc B.nd B.d B.s B.c A.nsdc A.ndc A.nsc A.nsd A.sc A.nd A.d A.s A.c Lập luận tương tự, ta có phương án 2 cũng thỏa mãn yêu cầu bài toán và có đường đi là: A.nsdc→B.nd→A.nsc→B.ndc→A.nsd→B.nsc→A.nd→B.nsdc. A.nsdc B.nd A.nsc B.nsd B.ndc A.ndc A.nsd B.nsc A.nd B.nsdc Tóm lại, các phương án chở thỏa mãn yêu cầu bài toán được thể hiện trong sơ đồ sau: 2. Bài toán ba thầy tu và ba con quỷ. Bài toán. Ba thầy tu và ba con quỷ sang sông bằng một thuyền nhỏ. Mỗi lần thuyền chỉ chở được nhiều nhất 2 người và ai cũng biết bơi thuyền. Hãy tìm phương án sang sông sao cho nếu có cả thầy tu và quỷ trên một bờ sông thì số thầy tu không được ít hơn số quỷ ( ngược lại thầy tu sẽ bị quỷ ăn thịt). Cách giải. Kí hiệu các nút trạng thái bờ sông là (n,m), trong đó n là số thầy tu, m là số quỷ. Cặp (n,m) phải thoả mãn: (0 ≤ n, m ≤ 3 ) và [ (n = 0) hoặc (n ≥ m) ]. Như vậy, ta có các nút trạng thái thỏa mãn yêu cầu bài toán là: (3,3), (3,2), (3,1), (3,0), (2,2), (2,1), (2,0), (1,1), (1,0), (0,3), (0,2), (0,1). Từ đó ta lập đồ thị có hướng biễu diễn khả năng chuyển đổi trạng thái các thầy tu và quỷ ở hai bên bờ sông, xuất phát từ bờ sông A và đến bờ sông B. Áp dụng thuật toán tìm đường đi trong đồ thị để tìm đường đi từ nút A(3,3) đến nút B(3,3). Như vậy ta có các nút trạng thái ứng với các đỉnh ở bờ sông A là: A(3,3), A(3,2), A(3,1), A(3,0), A(2,2), A(2,1), A(2,0), A(1,1), A(1,0), A(0,3), A(0,2), A(0,1) và các nút trạng thái ứng với các đỉnh ở bờ sông B là: B(3,3), B(3,2), B(3,1), B(3,0), B(2,2), B(2,1), B(2,0), B(1,1), B(1,0), B(0,3), B(0,2), B(0,1). A(3,3) A(3,2) A(3,1) A(3,0) A(2,2) A(2,1) A(2,0) A(1,1) A(1,0) A(0,3) A(0,2) A(0,1) B(3,3) B(3,2) B(3,1) B(3,0) B(2,2) B(2,1) B(2,0) B(1,1) B(1,0) B(0,3) B(0,2) B(0,1) Dòng sông Ta biểu diễn các nút trạng thái ở hai bên bờ sông như sau: Theo yêu cầu bài toán thì ta có các phương án chở là: *Phương án 1: - Xuất phát từ đỉnh A(3,3) ta đi đến đỉnh B(1,1)(Bờ sông A còn (2,2),bờ sông B có (1,1)). - Từ đỉnh B(1,1) ta đi đến đỉnh A(3,2) (Bờ sông B còn (0,1), bờ sông A có (3,2)). - Từ đỉnh A(3,2) ta đi đến đỉnh B(0,3) (Bờ sông A còn (3,0), bờ sông B có (0,3)). - Từ đỉnh B(0,3) ta đi đến đỉnh A(3,1) (Bờ sông B còn (0,2), bờ sông A có (3,1)). - Từ đỉnh A(3,1) ta đi đến đỉnh B(2,2) (Bờ sông A còn (1,1), bờ sông B có (2,2)). - Từ đỉnh B(2,2) ta đi đến đỉnh A(2,2) (Bờ sông B còn (1,1), bờ sông A có (2,2)). - Từ đỉnh A(2,2) ta đi đến đỉnh B(3,1) (Bờ sông A còn (0,2), bờ sông B có (3,1)). - Từ đỉnh B(3,1) ta đi đến đỉnh A(0,3) (Bờ sông B còn (3,0), bờ sông có (0,3)). - Từ đỉnh A(0,3) ta đi đến đỉnh B(3,2) (Bờ sông A còn (0,1), bờ sông B có (3,2)). - Từ đỉnh B(3,2) ta đi đến đỉnh A(0,2) (Bờ sông B còn (3,1), bờ sông A có (0,2)). - Từ đỉnh A(0,2) ta đi đến đỉnh B(3,3) (Từ A chở 2 quỷ sang bờ sông B ta được (3,3). Như vậy, ta đã chở ba thầy tu và ba con quỷ sang sông và thỏa mãn yêu cầu bài toán. Trong phương án này, ta có đồ thị: A(3,3) A(3,2) A(3,1) A(2,2) A(0,3) A(0,2) B(3,3) B(3,2) B(3,1) B(2,2) B(0,3) B(1,1) Và đường đi tương ứng với phương án này là: A(3,3)→B(1,1)→A(3,2)→B(0,3)→A(3,1)→B(2,2)→A(2,2)→B(3,1)→A(0,3)→ B(3,2)→A(0,2)→B(3,3). Tương tự như trên, ta có các phương án sau cũng thỏa mãn yêu cầu bài toán: *Phương án 2: A(3,3)→B(0,2)→A(3,2)→B(0,3)→A(3,1)→B(2,2)→A(2,2)→B(3,1)→A(0,3)→ B(3,2)→A(0,2)→B(3,3). *Phương án 3: A(3,3)→B(1,1)→A(3,2)→B(0,3)→A(3,1)→B(2,2)→A(2,2)→B(3,1)→A(0,3)→ B(3,2)→A(1,1)→B(3,3). *Phương án 4: A(3,3)→B(0,2)→A(3,2)→B(0,3)→A(3,1)→B(2,2)→A(2,2)→B(3,1)→A(0,3)→ B(3,2)→A(1,1)→B(3,3). A(3,3) B(0,2) B(1,1) A(3,2) B(0,3) A(3,1) B(2,2) A(2,2) B(3,1) A(0,3) B(3,2) A(0,2) A(1,1) B(3,3) Tóm lại, các phương án chở thỏa mãn yêu cầu bài toán được thể hiện trong sơ đồ sau: * Bài tập tham khảo: ( Bài toán ba ông chồng ghen ) Có 3 cặp vợ chồng qua sông bằng một thuyền nhỏ. Mỗi lần thuyền chỡ được nhiều nhất hai người và ai cũng biết bơi thuyền. Các ông chồng mắc bệnh ghen nặng nên không cho vợ đứng với người đàn ông khác khi không có mình. Hãy tìm phương án chỡ tất cả sang sông KẾT LUẬN Bài toán tìm đường đi trong mê cung là bài toán rất hay, nó khơi dậy khả năng toán học cho người học, đồng thời nó cũng kích thích được óc sáng tạo và tư duy định hướng cho người học. Bài toán này đã cuốn hút được sự quan tâm của nhiều người bởi tính đa dạng và sự ứng dụng của nó. Do vậy, việc học tập, nghiên cứu chủ đề này là rất bổ ích vì nó có thể giải quyết được nhiều vấn đề nảy sinh từ thực tế cuộc sống. Trong đề tài này, mặt dù nhóm em đã dành nhiều thời gian nghiên cứu, thảo luận, và được sự hướng dẫn chu đáo của Thầy PGS.TSKH.Trần Quốc Chiến nhưng do khả năng có hạn nên chắc chắn đề tài không tránh khỏi thiếu sót. Kính mong Thầy và các anh chị trong lớp góp ý, bổ sung, chỉnh sửa để đề tài được hoàn thiện hơn. Thay mặt nhóm, em xin chân thành cảm ơn sự giúp đỡ và hướng dẫn nhiệt tình, tận tuỵ của Thầy PGS.TSKH.Trần Quốc Chiến, cũng như sự động viên, khích lệ của tập thể lớp để nhóm em hoàn thành tốt đề tài này. MỘT SỐ MÊ CUNG ĐẸP TRÊN THẾ GIỚI TÀI LIỆU THAM KHẢO [1] Hoàng Chúng, Graph, Nhà xuất bản Gi