Đề tài nghiên cứu nhằm xây dựng thuật toán tìm đường đi trong mê cung thông qua lý thuyết đồ thị; xây dựng lại các thuật toán đã biết về tìm đường đi trong mê cung; tuyển chọn và xây dựng hệ thống các trò chơi tìm đường đi trong mê cung; tuyển chọn và mở rộng hệ thống các bài toán (đố vui) ứng dụng tìm đường đi trong mê cung. | 1 BỘ GIÁO DỤC VÀ ĐÀO TẠO ĐẠI HỌC ĐÀ NẴNG ĐÀO QUANG HÒA ĐƯỜNG ĐI TRONG MÊ CUNG VÀ ỨNG DỤNG Chuyên ngành: Phương pháp Toán sơ cấp Mã số: TÓM TẮT LUẬN VĂN THẠC SĨ KHOA HỌC Đà Nẵng - Năm 2011 2 Công trình ñược hoàn thành tại ĐẠI HỌC ĐÀ NẴNG Người hướng dẫn khoa học: . TRẦN QUỐC CHIẾN Phản biện 1: TS. NGUYỄN NGỌC CHÂU Phản biện 2: TS. HOÀNG QUANG TUYẾN Luận văn ñược bảo vệ trước hội ñồng chấm Luận văn tốt nghiệp thạc sĩ khoa học họp tại Đại học Đà Nẵng vào ngày 17 tháng 8 năm 2011. Có thể tìm hiểu luận văn tại: - Trung tâm thông tin- Học liệu, Đại học Đà Nẵng - Thư viện trường Đại học sư phạm, Đại học Đà Nẵng 3 MỞ ĐẦU 1. Lý do chọn ñề tài: 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 về chàng dũng sĩ Theseus ñi cứu công chúa Ariadne: Ở Crete, Nữ hoàng Pasiphae ngủ với một con bò và ñã sinh ra Minotaur, một sinh vật nửa người ñàn ông - một nửa con bò. Vua Minos rất bối rối, nhưng không muốn giết Minotaur, nên ông ñã nhốt con quái vật ñầu bò, mình người trong mê cung tại cung ñiện Minoan của Knossos ñược xây dựng bởi kiến trúc sư nổi tiếng tên là Daedalus. 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
