tailieunhanh - Luận án Tiến sĩ Toán học: Chu trình hamilton và chu trình dài nhất trong một số lớp đồ thị có tổng bậc lớn

Luận án nghiên cứu bài toán xác định sự tồn tại của chu trình Hamilton trong đồ thị trên các lớp đồ thị, đánh giá độ phức tạp thời gian đa thức để xác định chu trình Hamilton trong một lớp đồ thị đã khảo sát, đánh giá tính hiệu quả và khả thi của các thuật toán bằng chương trình thực nghiệm trên các đồ thị lớn, đánh giá độ dài của chu trình dài nhất trong lớp đồ thị. . | BỘ GIÁO DỤC VÀ ĐÀO TẠO VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VN HỌC VIỆN KHOA HỌC VÀ CÔNG NGHỆ Nguyễn Hữu Xuân Trƣờng CHU TRÌNH HAMILTON VÀ CHU TRÌNH DÀI NHẤT TRONG MỘT SỐ LỚP ĐỒ THỊ CÓ TỔNG BẬC LỚN Chuyên ngành: Cơ sở toán học cho tin học Mã số: 62 46 01 10 LUẬN ÁN TIẾN SĨ TOÁN HỌC Hà Nội – 2016 1 Công trình đƣợc hoàn thành tại: Học Viện Khoa Học và Công Nghệ - Viện Hàn Lâm Khoa Học và Công Nghệ Việt Nam, số 18 Hoàng Quốc Việt, Cầu Giấy, Hà Nội, Việt Nam. Ngƣời hƣớng dẫn khoa học: 1. . Vũ Đình Hòa 2. . Vũ Đức Thi Phản biện 1: . Phản biện 2: . Phản biện 3: . Luận án sẽ được bảo vệ trước Hội đồng chấm luận án cấp nhà nước họp tại: . . . Vào hồi giờ ngày tháng năm Có thể tìm hiểu luận án tại thư viện: . . 2 MỞ ĐẦU Các vấn đề của lý thuyết đồ thị đã có từ vài trăm năm trước (năm 1736 với bài toán 7 cây cầu ở thành phố Konigsber) nhưng phải tới vài chục năm gần đây, theo cùng sự phát triển của công nghệ thông tin, thì lý thuyết đồ thị mới thực sự phát triển mạnh mẽ không ngừng cả về chiều sâu cũng như chiều rộng. Sự phát triển của lý thuyết đồ thị gắn liền với những tên tuổi các nhà toán học lớn như Euler, Gauss, Hamilton, Erdos. Một trong những lý do khiến lý thuyết đồ thị phát triển mạnh mẽ như vậy là vì lý thuyết đồ thị khá gần gũi với thực tế và có những ứng dụng sâu rộng trong công nghệ thông tin và nhiều ngành khoa học khác. Vấn đề chu trình là một vấn đề trung tâm của lý thuyết đồ thị và đã có rất nhiều công trình nghiên cứu tới vấn đề này, đặc biệt là chu trình Hamilton với khoảng 400 bài báo khoa học được đăng tải trên các tạp chí khoa học quốc tế có uy tín hàng đầu trong vòng 20 năm gần đây [25], [26], [27]. Hiện nay, các nghiên cứu về chu trình nói chung và chu trình Hamilton rộng .