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ị. Mời các bạn cùng tham khảo.
Nội dung trích xuất từ tài liệu:
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 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. PGS.TSKH. Vũ Đình Hòa 2. GS.TS. 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 trên nhiều khía cạnh, trong đó tập trung chủ yếu tới bậc của đỉnh; ngoài ra còn nghiên cứu trên các đồ thị 1-tough, đồ thị path-tough, đồ thị có tập láng giềng lớn, đồ thị phẳng, đồ thị ngẫu nhiên, đồ thị lưỡng phân và chu trình dài nhất, chu trình Dominating... Tại Việt Nam, một số tác giả cũng đã tập trung nghiên cứu về chu trình Hamilton trên các lớp đồ thị khác nhau, chẳng hạn như Ngô Đắc Tân nghiên cứu trên lớp đồ thị split và cubic, Vũ Đình Hòa nghiên cứu trên lớp đồ thị 1-tough có tổng bậc lớn… Chu trình Hamilton có nhiều ứng dụng trong thực tế, ví dụ như trong bài toán người bán hàng, lập kế hoạch, hay trong thiết kế vi mạch, thiết kế đường truyền trong mạng… Bài toán (xác định sự tồn tại của chu trình Hamilton trong đồ thị) được biết là bài toán [23] nên trong trường hợp tổng quát sẽ không có thuật toán tốt (thời gian đa thức) để giải nó. Do đó, việc tìm ra được các trường hợp thuộc lớp của bài toán cũng như việc thiết kế được thuật toán thời gian đa thức để xác định được chu trình Hamilton có ý nghĩa hết sức quan trọng. Các nghiên cứu hiện nay hầu hết là dựa trên những lớp đồ thị đặc biệt và tập trung vào việc chỉ ra sự tồn tại của chu trình Hamilton trong những lớp đồ thị đó. Có rất nhiều lớp đồ thị được xét tới, trong đó phần lớn các lớp đồ thị này được xác định theo điều kiện tổng bậc (của đỉnh) đủ lớn [15], [17], [18], [20], [22], [29], [30], [31], [36]... Một số tác giả nghiên cứu độ phức tạp của bài toán [3], [15], [23], [34], [37], hoặc đánh giá số lượng chu trình Hamilton [14]… Một số khác nghiên cứu đến việc thiết kế các thuật toán để xác định chu trình Hamilton, trong đó có các thuật toán Backtrack, Heuristic và các thuật toán thời gian đa thức áp dụng cho những lớp đồ thị đặc biệt [5], [12], [22], [28], [38], [44]… Trong [15] (Định lý 16), các tác giả đã đánh giá độ phức tạp của bài toán đồ thị thỏa mãn vẫn còn là bài toán với mọi với lớp . Có thể nói rằng kết quả này là tiền đề cho nghiên cứu về chu trình Hamilton của tác giả trong luận án. Thêm vào đó, một số kết quả trong [11], [17], [32], [36] đã khẳng định sự tồn tại của chu trình Hamilton trong các lớp đồ thị được xác định theo điều kiện của tổng bậc và đủ lớn, tuy nhiên các lớp đồ thị được xác định theo điều kiện và là chưa có thuật toán xác định chu trình Hamilton. 3 Cùng với chu trình Hamilton, chu trình dài nhất trong đồ thị cũng được tập trung nghiên cứu tới và có nhiều kết quả đối với chu trình dài được áp dụng cho việc chứng minh sự tồn tại cũng như thiết kế thuật toán để xác định chu trình Hamilton. Trong một bài báo của các tác giả D. Bauer, G. Fan, H. J. Veldman [8] đã đưa ra một Giả thuyết đánh giá độ dài chu trình dài nhất theo giá trị mà cho tới nay vẫn chưa có chứng minh thỏa đáng nào cho Giả thuyết này. Mục tiêu nghiên cứu của luận án là:  Nghiên cứu bài toán trung vào trường hợp trên các lớp đồ thị có tổng bậc và lớn, trong đó tập .  Đánh giá độ phức tạp của bài toán chuyển từ lớp sang lớp . theo một tham số . Xác định để bài toán  Xây dựng thuật toán thời gian đa thức để xác định chu trình Hamilton trong một số 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ị 1-tough với . Kết cấu của luận án gồm: phần mở đầu, 4 chương và phần kết luận. Chƣơng 1: Tổng quan về chu trình trong đồ thị. Giới thiệu một số vấn đề cơ bản của lý thuyết đồ thị, các khái niệm, các quy ước và ký hiệu sử dụng trong luận án. Tiếp đến, giới thiệu tổng quan về vấn đề chu trình trong đồ thị, trọng tâm là chu trình Hamilton. Ngoài ra, tác giả đưa ra một số kết quả nghiên cứu về bao đóng của đồ thị để sử dụng trong một số chứng minh của luận án. Chƣơng 2: Một số lớp đa thức của bài toán . Chương này nghiên cứu về chu trình Hamilton theo hai bài toán nguyên dương, số th ...