Đồ án tốt nghiệp được biên soạn với mục tiêu tìm hiểu về cơ sở lý thuyết về đồ thị và độ phức tạp thuật toán; bài toán tìm bộ ghép cực đại trên đồ thị và các thuật toán; ứng dụng bài toán ghép đôi trong thực tế. | ĐẠI HỌC KHOA CÔNG NGHỆ THÔNG TIN ĐỒ ÁN TỐT NGHIỆP ĐẠI HỌC TÊN ĐỀ TÀI XÂY DỰNG BÀI TOÁN GHÉP ĐÔI KHÔNG TRỌNG SỐ Họ và tên Chuyên nghành Công nghệ thông tin Lớp cntt Khoá 2016 2020 Hướng dẫn Tiến sỹ Hà Nội 12 2020 1 LỜI CAM ĐOAN Em xin cam đoan Đồ án tốt nghiệp Xây dựng bài toán ghép đôi không trọng số này là công trình nghiên cứu của cá nhân em được thực hiện trên cơ sở nghiên cứu lý thuyết và ứng dụng dưới sự hướng dẫn khoa học của Tiến sĩ Phạm Minh Hoàn Trường Đại học Kinh tế quốc dân . Em xin chịu trách nhiệm về lời cam đoan này. Hà Nội ngày 12 tháng 12 năm 2020 Tác giả 2 LỜI CÁM ƠN Để hoàn thành bài nghiên cứu này em xin chân thành cám ơn Trường Đại học Kinh tế quốc dân Phòng đào tạo các thầy cô giáo giảng dạy lóp Công nghệ thông tin 58B đã quan tâm tạo điều kiện thuận lợi tận tình giảng dạy và giúp đỡ em trong thời gian theo học tại trường. Đặc biêt em xin bày tỏ lòng biết ơn sâu sắc đến TS. Phạm Minh Hoàn người đã dành nhiều thời gian tam huyết hướng dẫn em trong suốt quá trình nghiên cứu và hoàn thành đồ án . Mặc dù đã cố gắng hết sức hoàn thiện luận văn tuy nhiên chắc chắn vẫn còn nhiều thiếu sót rất mong nhận được sự góp ý quý báu của quý thầy cô và các bạn. Xin trân trọng cám ơn Hà Nội ngày 12 tháng 12 năm 2020 Tác giả 3 MỤC LỤC 4 LỜI NÓI ĐẦU Ngày nay việc giải quyết các bài toán lớn cho hệ thống đòi hỏi sự hợp tác chặt chẽ giữa các chuyên gia trong các lĩnh vực chuyên môn như các chuyên gia Toán Toán ứng dụng và các chuyên gia Tin học kỹ sư lập trình. Việc thiết lập được một mô hình hợp lý phản ánh đƣợc bản chất của bài toán thực tế đồng thời khả thi về phương diện tính toán luôn là điều đáng được quan tâm. Đặc biệt trong các chuyên ngành liên quan thì toán học là chuyên ngành rất được quan tâm một trong số đó là Lý thuyết đồ thị. Đồ thị biểu diễn được rất nhiều cấu trúc nhiều bài toán thực tế có thể được biểu diễn bằng đồ thị. Ví dụ cấu trúc liên kết của một website có thể được biểu diễn bằng một đồ thị có hướng như sau các đỉnh là các trang web hiện .
