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<br /> <br /> VIỆN HÀN LÂM<br /> KHOA HỌC VÀ CÔNG NGHỆ VN<br /> <br /> HỌC VIỆN KHOA HỌC VÀ CÔNG NGHỆ<br /> <br /> Nguyễn Hữu Xuân Trƣờng<br /> <br /> CHU TRÌNH HAMILTON VÀ CHU TRÌNH DÀI NHẤT<br /> TRONG MỘT SỐ LỚP ĐỒ THỊ CÓ TỔNG BẬC LỚN<br /> <br /> Chuyên ngành: Cơ sở toán học cho tin học<br /> Mã số: 62 46 01 10<br /> <br /> LUẬN ÁN TIẾN SĨ TOÁN HỌC<br /> <br /> Hà Nội – 2016<br /> <br /> 1<br /> 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<br /> 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.<br /> <br /> Ngƣời hƣớng dẫn khoa học: 1. PGS.TSKH. Vũ Đình Hòa<br /> 2. GS.TS. Vũ Đức Thi<br /> <br /> Phản biện 1:…………………………………………………………….………..<br /> ……………………………………………………………………………………<br /> Phản biện 2:…………………………………………………………….………..<br /> ……………………………………………………………………………………<br /> Phản biện 3:…………………………………………………………….………..<br /> ……………………………………………………………………………………<br /> <br /> 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:<br /> …………………………………………………………….…………….<br /> …………………………………………………………………………………….<br /> Vào hồi<br /> giờ<br /> ngày<br /> tháng<br /> năm<br /> <br /> Có thể tìm hiểu luận án tại thư viện: …………………………………….….<br /> <br /> 2<br /> <br /> MỞ ĐẦU<br /> 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<br /> 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<br /> 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<br /> 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<br /> 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<br /> 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<br /> 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<br /> học khác.<br /> 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<br /> 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<br /> 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<br /> 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<br /> 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<br /> 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, đồ<br /> thị phẳng, đồ thị ngẫu nhiên, đồ thị lưỡng phân và chu trình dài nhất, chu trình<br /> 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<br /> 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 đồ<br /> 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…<br /> Chu trình Hamilton có nhiều ứng dụng trong thực tế, ví dụ như trong bài toán người<br /> 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<br /> toán<br /> (xác định sự tồn tại của chu trình Hamilton trong đồ thị) được biết là bài toán<br /> [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<br /> nó. Do đó, việc tìm ra được các trường hợp thuộc lớp của bài toán<br /> cũng như việc thiết<br /> 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<br /> quan trọng.<br /> 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<br /> 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 đồ<br /> 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<br /> (của đỉnh) đủ lớn [15], [17], [18], [20], [22], [29], [30], [31], [36]... Một số tác giả nghiên<br /> cứu độ phức tạp của bài toán<br /> [3], [15], [23], [34], [37], hoặc đánh giá số lượng chu trình<br /> 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<br /> trình Hamilton, trong đó có các thuật toán Backtrack, Heuristic và các thuật toán thời gian<br /> đa thức áp dụng cho những lớp đồ thị đặc biệt [5], [12], [22], [28], [38], [44]…<br /> Trong [15] (Định lý 16), các tác giả đã đánh giá độ phức tạp của bài toán<br /> đồ thị thỏa mãn<br /> <br /> vẫn còn là bài toán<br /> <br /> với mọi<br /> <br /> với lớp<br /> <br /> . Có thể nói rằng kết<br /> <br /> 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<br /> 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<br /> Hamilton trong các lớp đồ thị được xác định theo điều kiện của tổng bậc<br /> và<br /> đủ<br /> lớn, tuy nhiên các lớp đồ thị được xác định theo điều kiện và<br /> là chưa có thuật toán xác<br /> định chu trình Hamilton.<br /> <br /> 3<br /> Cùng với chu trình Hamilton, chu trình dài nhất trong đồ thị cũng được tập trung<br /> 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<br /> 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<br /> của các tác giả D. Bauer, G. Fan, H. J. Veldman [8] đã đưa ra một Giả thuyết đánh giá độ<br /> dài chu trình dài nhất theo giá trị<br /> mà cho tới nay vẫn chưa có chứng minh thỏa đáng<br /> nào cho Giả thuyết này.<br /> Mục tiêu nghiên cứu của luận án là:<br />  Nghiên cứu bài toán<br /> trung vào trường hợp<br /> <br /> trên các lớp đồ thị có tổng bậc<br /> <br /> và<br /> <br /> lớn, trong đó tập<br /> <br /> .<br /> <br />  Đánh giá độ phức tạp của bài toán<br /> chuyển từ lớp<br /> sang lớp .<br /> <br /> theo một tham số . Xác định<br /> <br /> để bài toán<br /> <br />  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ố<br /> lớp đồ thị đã khảo sát.<br />  Đá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<br /> nghiệm trên các đồ thị lớn.<br />  Đánh giá độ dài của chu trình dài nhất trong lớp đồ thị 1-tough với<br /> <br /> .<br /> <br /> 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.<br /> Chƣơng 1: Tổng quan về chu trình trong đồ thị.<br /> 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ý<br /> 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ị,<br /> 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<br /> đóng của đồ thị để sử dụng trong một số chứng minh của luận án.<br /> Chƣơng 2: Một số lớp đa thức của bài toán<br /> <br /> .<br /> <br /> Chương này nghiên cứu về chu trình Hamilton theo hai bài toán<br /> nguyên dương, số thực là tham số) như sau:<br /> <br /> Instance: Đồ thị<br /> Question:<br /> <br /> (với<br /> <br /> .<br /> <br /> có là đồ thị Hamilton?<br /> <br /> Instance: Đồ thị<br /> Question:<br /> <br /> thỏa mãn<br /> <br /> và<br /> <br /> thỏa mãn<br /> <br /> .<br /> <br /> có là đồ thị Hamilton?<br /> <br /> Tác giả tập trung vào việc đánh giá độ phức tạp của bài toán theo tham số<br /> các lớp đa thức của bài toán<br /> .<br /> <br /> để tìm ra<br /> <br /> Chƣơng 3: Thuật toán đa thức xác định chu trình Hamilton trong đồ thị<br /> và<br /> <br /> .<br /> <br /> 4<br /> Chương này sẽ thiết kế thuật toán đa thức xác định chu trình Hamilton cho các lớp đồ<br /> thị<br /> <br /> và<br /> <br /> , sau đó tác giả tiến hành thực nghiệm trên các đồ thị lớn (hàng<br /> <br /> nghìn đỉnh) để cho thấy tính hiệu quả và khả thi thực hiện của các thuật toán. Thêm vào đó,<br /> tác giả đưa ra một số đề xuất mới để làm tăng hiệu năng thực hiện của thuật toán.<br /> Chƣơng 4: Đánh giá độ dài chu trình dài nhất trong đồ thị 1-tough với<br /> <br /> .<br /> <br /> Chương này của luận án sẽ đưa ra một chứng minh cho Giả thuyết của các tác giả<br /> Bauer, Fan, Veldman [8] về cận dưới của độ dài chu trình dài nhất rằng:<br /> Nếu<br /> <br /> là đồ thị 1-tough và<br /> <br /> thì<br /> <br /> .<br /> <br /> Giả thuyết trên cũng đã được một số tác giả khác quan tâm và tìm cách chứng minh,<br /> tuy nhiên các chứng minh đưa ra đều chưa thỏa đáng. Cho đến nay vẫn chưa có chứng minh<br /> đúng nào cho Giả thuyết này và đây vẫn là vấn đề mở.<br /> <br /> CHƢƠNG 1. TỔNG QUAN VỀ CHU TRÌNH TRONG ĐỒ THỊ<br /> 1.1. Một số khái niệm và quy ƣớc<br /> Trong luận án chỉ xét tới các đồ thị hữu hạn, đơn, vô hướng và không có trọng số.<br /> Khái niệm đường đi và chu trình trong luận án là đơn, nghĩa là chúng chỉ đi qua các<br /> đỉnh không quá một lần. Một đường đi (đơn)<br /> là một đồ thị con không<br /> rỗng có cấu trúc:<br /> và<br /> , trong đó,<br /> với mọi<br /> . Các đỉnh<br /> được nối bởi , và gọi là các đỉnh cuối; các đỉnh<br /> gọi là các đỉnh trong của .<br /> Nếu<br /> là một đường đi và<br /> một chu trình, khi đó chu trình được viết như sau:<br /> chu trình gọi là độ dài của nó, ký hiệu là<br /> .<br /> <br /> được gọi là<br /> . Số cạnh của<br /> <br /> thì<br /> <br /> Các ký hiệu khi viết không kèm theo đồ thị tường minh thì hiểu mặc định là đồ thị .<br /> Ví dụ, viết<br /> tương ứng thay cho<br /> .<br /> Giả sử<br /> có thể xem<br /> <br /> là một đường đi và là một chu trình của đồ thị . Trong luận án, đôi khi ta<br /> như là một tập đỉnh con của (tương ứng thay cho<br /> ).<br /> <br /> Một đường đi là mở rộng (theo tập đỉnh) của đường đi<br /> tự, một chu trình là mở rộng của chu trình nếu<br /> <br /> nếu<br /> .<br /> <br /> Với<br /> , ta ký hiệu<br /> là đoạn đường chạy dọc theo từ đỉnh<br /> vậy, nếu<br /> là các đỉnh cuối của thì<br /> cũng chính là . Ngoài ra, |<br /> đỉnh nằm trên đoạn đường con này.<br /> <br /> . Tương<br /> tới đỉnh . Như<br /> | quy ước là số<br /> <br /> Giả sử chu trình<br /> . Ta quy định một chiều quay ⃗⃗⃗ theo<br /> thứ tự chỉ số các đỉnh (chỉ số được lấy theo<br /> ). Với đỉnh<br /> , ký hiệu<br /> lần<br /> lượt là đỉnh liền trước và liền sau của<br /> theo chiều quay đã định. Với tập đỉnh<br /> thì<br /> ,<br /> . Với số nguyên dương<br /> , ký hiệu<br /> <br />