Luận văn trình bày về bài toán Clique Editing, và chứng minh tính NP-đầy đủ của bài toán, sau đó sẽ tìm hiểu lớp bài toán FPT và chứng minh bài toán Clique Editing thuộc lớp FPT. Mời các bạn tham khảo! | 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Ệ - Trần Quang ĐỘ PHỨC TẠP CỦA BÀI TOÁN BIẾN ĐỔI ĐỒ THỊ VỀ ĐỒ THỊ ĐẦY ĐỦ 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Ệ - Trần Quang ĐỘ PHỨC TẠP CỦA BÀI TOÁN BIẾN ĐỔI ĐỒ THỊ VỀ ĐỒ THỊ ĐẦY ĐỦ 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 . Phan Thị Hà Dương Hà Nội - 2019 1 LỜI CAM ĐOAN Tôi xin cam đoan những gì viết trong luận văn là do sự tìm tòi học hỏi của bản thân và sự hướng dẫn tận tình của cô Phan Thị Hà Dương. Mọi kết quả nghiên cứu cũng như ý tưởng của tác giả khác nếu có đều được trích dẫ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 hề được công bố trên bất kỳ một phươ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 1 tháng 12 năm 2018 Người cam đoan Trần Quang 2 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 cô Phan Thị Hà Dương. Tôi xin bày tỏ lòng biết ơn sâu sắc đến cô người đã giúp đỡ và chỉ bảo tôi một cách tận tình trong suốt quá trình thực hiện luận văn. Xin cảm ơn các thầy cô các anh chị trong Seminar Cơ sở Toán-Tin đã góp ý và giúp đỡ tôi trong quá trình làm luận văn. Xin cảm ơn các thầy cô các anh chị ở Học viện Khoa học-Công nghệ nói chung và ở Viện Toán học nói riêng đã tạo điều kiện cho tôi hoàn thành luận văn. Cảm ơn chị Thúy chị Vân Anh đã hết mình tạo điều kiện và sắp xếp cho tôi thời gian bảo vệ luận văn sớm nhất có thể. Đặc biệt tôi xin gửi lời cảm ơn chân thành và biết ơn vô tận đối với cha mẹ tôi những người đã luôn sát cánh và tạo động lực để tôi hoàn thành luận văn này. Trần Quang 3 MỤC LỤC Lời cam đoan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 Lời cảm ơn . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 Mục lục . . . . . . . . . . . . . .
