Luận văn Thạc sĩ Toán học: Một số bài toán tối ưu trên đồ thị và ứng dụng

Một số bài toán tối ưu tổ hợp có thể được mô hình hóa (và giải) một cách rất tự nhiên bằng ngôn ngữ đồ thị. Luận văn này sẽ tập trung vào một lớp bài toán tiêu biểu trong số đó. Tác giả cũng trình bày mô hình toán học và phương pháp giải, sau đó minh họa bằng một ứng dụng thực tiễn.
Nội dung trích xuất từ tài liệu:
Luận văn Thạc sĩ Toán học: Một số bài toán tối ưu trên đồ thị và ứng dụng BỘ GIÁO DỤC VIỆN HÀN LÂM KHOA HỌC VÀ ĐÀO TẠO VÀ CÔNG NGHỆ VIỆT NAM HỌC VIỆN KHOA HỌC VÀ CÔNG NGHỆ ----------------------------- Lê Thị Phương LoanMỘT SỐ BÀI TOÁN TỐI ƯU TRÊN ĐỒ THỊ VÀ ỨNG DỤNG LUẬN VĂN THẠC SĨ: TOÁN HỌC Hà Nội - 2019 BỘ GIÁO DỤC VIỆN HÀN LÂM KHOA HỌC VÀ ĐÀO TẠO VÀ CÔNG NGHỆ VIỆT NAM HỌC VIỆN KHOA HỌC VÀ CÔNG NGHỆ ----------------------------- Lê Thị Phương LoanMỘT SỐ BÀI TOÁN TỐI ƯU TRÊN ĐỒ THỊ VÀ ỨNG DỤNG Chuyên ngành: Toán ứng dụng Mã số: 8 46 01 12 LUẬN VĂN THẠC SĨ: TOÁN HỌC NGƯỜI HƯỚNG DẪN KHOA HỌC: TS Nguyễn Hoàng Thạch Hà Nội - 2019 LỜI CAM ĐOAN Tôi xin cam đoan những nội dung trong luận văn là do sự tìm hiểu, nghiêncứu của bản thân và sự hướng dẫn tận tình của thầy Nguyễn Hoàng Thạch. Cáckết quả nghiên cứu cũng như ý tưởng của tác giả khác, nếu có đều được tríchdẫn cụ thể. Đề tài luận văn này cho đến nay chưa được bảo vệ tại bất kỳ một hộiđồng bảo vệ luận văn thạc sĩ nào và cũng chưa được công bố trên bất kỳ mộtphương tiện nào.Tôi xin chịu trách nhiệm về những lời cam đoan trên. Hà Nội, ngày 30 tháng 10 năm 2019 Người cam đoan Lê Thị Phương Loan LỜI CẢM ƠN Luận văn này được hoàn thành dưới sự hướng dẫn tận tình của TS NguyễnHoàng Thạch. Nhân dịp này em xin bày tỏ lòng biết ơn thầy về sự hướng dẫnhiệu quả cùng những kinh nghiệm trong suốt quá trình học tập, nghiên cứu vàhoàn thành luận văn.Tôi xin trân trọng cảm ơn sự giúp đỡ và tạo điều kiện thuận lợi của Học việnKhoa học và Công nghệ, Viện Hàn lâm Khoa học và Công nghệ Việt Nam trongquá trình tôi thực hiện luận văn.Tôi xin chân thành cảm ơn Viện Toán học và các thầy cô anh chị trong phòngCơ sở Toán học của Tin học đã tạo điều kiện thuận lợi cho tôi trong quá trìnhhọc tập và nghiên cứu.Xin cảm ơn các bạn học viên chuyên ngành Toán ứng dụng khoá 2017- 2019 đãgiúp đỡ, động viên tôi trong quá trình thực hiện luận văn.Cuối cùng, luận văn chắc chắn sẽ không tránh khỏi những khiếm khuyết. Vì vậytôi rất mong nhận được sự đóng góp ý kiến của các thầy cô giáo và các bạn họcviên để luận văn này được hoàn chỉnh hơn. 1 MỤC LỤCLời cam đoanLời cảm ơnMục lục 1Lời nói đầu 3Danh sách bảng 5Danh sách hình vẽ 61 KIẾN THỨC CHUẨN BỊ 7 1.1 CÁC KHÁI NIỆM CƠ BẢN VỀ ĐỒ THỊ . . . . . . . . . . . . . 7 1.1.1 Các định nghĩa và thí dụ . . . . . . . . . . . . . . . . . . . 7 1.1.2 Biểu diễn đồ thị . . . . . . . . . . . . . . . . . . . . . . . 11 1.2 ĐƯỜNG ĐI VÀ TÍNH LIÊN THÔNG . . . . . . . . . . . . . . 15 1.2.1 Đường đi và chu trình . . . . . . . . . . . . . . . . . . . . 15 1.2.2 Tính liên thông . . . . . . . . . . . . . . . . . . . . . . . . 172 BÀI TOÁN TÌM ĐƯỜNG ĐI NGẮN NHẤT TRÊN ĐỒ THỊ 19 2.1 BÀI TOÁN TÌM ĐƯỜNG ĐI NGẮN NHẤT . . . . . . . . . . . 20 2.2 THUẬT TOÁN DIJKSTRA . . . . . . . . . . . . . . . . . . . . 21 2.2.1 Mô tả thuật toán . . . . . . . . . . . . . . . . . . . . . . . 21 2.2.2 Chứng minh tính đúng đắn của thuật toán . . . . . . . . . . 23 2.2.3 Độ phức tạp của thuật toán . . . . . . . . . . . . . . . . . 27 2 2.2.4 Ví dụ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 2.3 THUẬT TOÁN BELLMAN-FORD . . . . . . . . . . . . . . . . 28 2.3.1 Mô tả thuật toán . . . . . . . . . . . . . . . . . . . . . . . 28 2.3.2 Chứng minh tính đúng đắn của thuật toán . . . . . . . . . . 30 2.3.3 Độ phức tạp của thuật toán . . . . . . . . . . . . . . . . . 31 2.3.4 Ví dụ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 2.4 SO SÁNH . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 333 ỨNG DỤNG: BÀI TOÁN LẬP KẾ HOẠCH 34 3.1 MÔ TẢ BÀI TOÁN . . . . . . . . . . . . . . . . . . . . . . . . 35 3.2 MÔ HÌNH ĐỒ THỊ . . . . . . . . . . . . . . . . . ...