Tiểu Luận Đường đi Hamilton và ứng dụng

mỤC LỤc
lời mở đầu 2
Nội dung 3
1. Đồ thị Hamilton 3
1.1 Khái niệm đường đi, chu trình Hamilton 3
1.2 Các định lí 3
2. Thuật toán nhánh cận giải bài toán người du lịch 72.1 Thuật toán nhánh cận 7
2.2 Bài toán Người du lịch 7
2.3 Cách giải 7
2.4 Mô hình kĩ thuật nhánh cận 103. Ứng dụng của bài toán người du lịch 124. Cài đặt chương trình và minh họa kết quả 134.1 Cấu trúc dữ liệu 134.2 Cài đặt chương trình 15
4.3 Minh họa kết quả 18Kết luận 20Tài liệu tham khảo 21
LỜI MỞ ĐẦU
Lý thuyết đồ thị là một ngà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ó nhiều bài toán liên quan tới một tập các đối tượng và những mối liên hệ giữa chúng, đòi hỏi toán học phải đặt ra một mô hình biểu diễn một cách chặt chẽ và tổng quát bằng ngôn ngữ ký hiệu, đó là đồ thị. Những ý tưởng cơ bản của nó được đưa ra từ thế kỷ thứ XVIII bởi nhà toán học Thụy Sỹ Leonhard Euler, ông đã dùng mô hình đồ thị để giải bài toán về những cây cầu Konigsberg nổi tiếng. Các bài toán về đường đi, trong đó đồ thị Hamilton là nội dung quan trọng của Lý thuyết đồ thị.
Bài toán “Người du lịch” cũng là một vấn đề thú vị cho các nhà kinh doanh cũng như ứng dụng vào đời sống. Sử dụng lý thuyết đồ thị để giải bài toán người du lịch không chỉ là toán học thuần túy mà còn mở ra cho chúng ta nhiều phạm trù ứng dụng phong phú. Mối liên hệ giữa bài toán “Người du lịch” với đồ thị Hamilton và những ứng dụng của nó là một vấn đề mở, thu hút bất kỳ ai quan tâm đến nội dung này. Vì vậy, nhóm chúng tôi chọn đề tài: “Đường đi Hamilton và ứng dụng” để nghiên cứu.
Mặc dù các thành viên trong nhóm đã có nhiều cố gắng nhưng trong quá trình thực hiện bài tiểu luận sẽ có nhiều thiếu sót, nhóm chúng tôi rất mong nhận được sự góp ý của thầy và các bạn.