Tiểu Luận Bài toán người du lịch Lý thuyết đồ thị và ứng dụng

MỤC LỤCMỤC LỤC 1
MỞ ĐẦU 2
Chương 1: CƠ SỞ LÝ THUYẾT 3
1.1 CÁC KHÁI NIỆM CƠ BẢN 3
1.1.1. Đồ thị, đỉnh, cạnh, cung. 3
1.1.2. Đường đi, chu trình, tính liên thông. 4
1.2. BIỂU DIỄN ĐỒ THỊ. 5
1.2.1. Ma trận kề. 5
1.2.1.1. Đồ thị vô hướng. 5
1.2.1.2. Đồ thị có hướng. 6
1.2.2. Ma trận liên thuộc. 6
1.2.2.1. Đồ thị vô hướng. 6
1.2.2.2.Đồ thị có hướng. 7
1.2. ĐƯỜNG ĐI VÀ ĐỒ THỊ HAMILTON 7
1.2.1. Định nghĩa 1.2.9. 7
1.2.2. Điều kiện cần. 7
1.2.3. Điều kiện đủ. 7
1.2.4. Đồ thị có hướng. 9
Chương 2 : BÀI TOÁN NGƯỜI DU LỊCH 9
2.1. PHÁT BIỂU BÀI TOÁN 9
2.2. GIẢI QUYẾT BÀI TOÁN 9
2.2.1. Một số phương pháp giải 9
2.2.2.Phương pháp nhánh cận. 10
2.2.2.1.Phương pháp. 10
2.2.2.2. Cơ sở lý luận của phép toán. 10
2.2.2.3. Ma trận rút gọn. 11
2.2.2.4. Mệnh đề. 12
2.2.2.5. Thủ tục phân nhánh. 12
2.2.2.6 Thủ tục chọn cạnh phân nhánh. 14
2.2.2.7. Chọn 2 cạnh cuối cùng. 17
2.2.2.8. Tính chất tối ưu. 20
2.3.CÀI ĐẶT CHƯƠNG TRÌNH 20
2.3.1. Đầu vào. 20
2.3.2. Đầu ra. 21
2.3.3. Chương trình cài đặt thuật toán nhánh cận cho Bài toán người du lịch theo ngôn ngữ lập trình Pascal 21
KẾT LUẬN 30

MỞ ĐẦU
Lý thuyết đồ thị là ngành khoa học phát triển từ lâu đời 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. Ngày nay, lý thuyết đồ thị đã phát triển thành Toán học có vị trí đăc biệt quan trọng về mặt lý thuyết cũng như ứng dụng, đặc biệt là ứng dụng vào giải các bài toán tối ưu.
Bài toán Người du lịch (Travelling Salesman Problem) là một trong những bài toán kinh điển và khó trong tin học. Có rất nhiều cách tiếp cận giải bài toán này ngay từ khi nó mới ra đời, như sử dụng quy hoạch tuyến tính, nhánh và cận, nhưng mới chỉ dừng lại ở các bộ dữ liệu nhỏ, không tìm được cách giải tối ưu và vẫn đang được tiếp tục nghiên cứu và phát triển.
Với mong muốn bước đầu nghiên cứu về những bài toán tối ưu và cách giải một số bài toán tối ưu cũng như tìm kiếm những phương pháp có thể giải tốt những bài toán tối ưu, nhóm 5 chúng tôi đã chọn: “Bài toán người du lịch” (Traveling salesman problem) cho đề tài nghiên cứu của môn học “Lý thuyết đồ thị và ứng dụng”.
Đề tài gồm 2 chương xoay quanh nguyên lý bù trừ. Chương 1 nêu đại cương về cơ sở lý thuyết của lý thuyết đồ thị, chương 2 nghiên cứu sâu về bài toán người du lịch .