Mục tiêu của đề tài là trình bày hệ thống lý thuyết đồ thị; trình bày hệ thống lý thuyết về đường đi ngắn nhất và các thuật toán tìm đường đi ngắn nhất; các ứng dụng của bài toán tìm đường đi ngắn nhất. . | 1 BỘ GIÁO DỤC VÀ ĐÀO TẠO ĐẠI HỌC ĐÀ NẴNG - - HỒ TRUNG CANG BÀI TOÁN TÌM ĐƯỜNG ĐI NGẮN NHẤT VÀ ỨNG DỤNG CHUYÊN NGÀNH: PHƯƠNG PHÁP TOÁN SƠ CẤP MÃ SỐ: 60. 46. 40 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: PGS-TSKH Tr n Qu c Chi n Phản biện 1: TS. CAO VĂN NUÔI 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 08 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 khoa học ñược phát triển từ lâu nhưng lại có nhiều ứng dụng hiện ñại, nó là kiến thức cơ sở cho nhiều ngành khoa học kỹ thuật khác nhau như Điện tử, Hóa học, Ngôn ngữ học, Kinh tế học, Máy tính, Nhiều khái niệm của lý thuyết ñồ thị ñược sinh ra từ các vấn ñề thực tiễn như: ñường ñi, chu trình, tập ổn ñịnh, chu số, sắc số, duyệt ñồ thị, ñường ñi Hamilton, tâm ñồ thị, luồng vận tải, ñồ thị phẳng, cây bao trùm, cây biểu thức, cây mã tiền tố tối ưu,. vì vậy lý thuyết ñồ thị ñã gắn kết nhiều ngành khoa học lại với nhau. Các thuật toán ngắn gọn và lí thú của lý thuyết ñồ thị ñã giúp chúng ta giải quyết rất nhiều bài toán phức tạp trong thực tế, trong ñó vấn ñề tìm ñường ñi ngắn nhất giúp chúng ta giải quyết ñược rất nhiều bài toán trong thực tế. Vì vậy, tôi ñã chọn ñề tài: “Bài toán tìm ñường ñi ngắn nhất và ứng dụng” ñể nghiên cứu. 2. Mục ñích và nhiệm vụ nghiên cứu: Trình bày hệ thống lý thuyết ñồ thị. Trình bày hệ thống lý thuyết về ñường ñi ngắn nhất và các thuật toán tìm ñường ñi ngắn nhất. Các ứng dụng của bài toán tìm ñường ñi ngắn nhất. 3. Đối tượng và phạm vi nghiên cứu: . Đối tượng nghiên cứu: Đối tượng nghiên cứu của ñề tài là bài toán ñường ñi ngắn nhất và một số ứng dụng của nó. 4 . Phạm vi nghiên cứu: Các thuật toán tìm ñường ñi ngắn nhất và .
