Tài liệu 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 LUẬN ÁN TIẾN SĨ TOÁN HỌC HÀ NỘI – 2016 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 NGƢỜI HƢỚNG DẪN KHOA HỌC: 1. PGS.TSKH. Vũ Đình Hòa 2. GS.TS. Vũ Đức Thi HÀ NỘI – 2016 i Lời cam đoan Tôi xin cam đoan đây là công trình nghiên cứu của riêng tôi. Các kết quả nêu trong luận án là trung thực và chưa từng được ai công bố trong bất kỳ công trình nào khác. Mọi thông tin tham khảo đều được trích dẫn đầy đủ. Tôi xin chịu hoàn toàn trách nhiệm về cam đoan này. Tác giả Nguyễn Hữu Xuân Trường ii Lời cảm ơn Luận án được hoàn thành dưới sự hướng dẫn tận tâm của PGS.TSKH. Vũ Đình Hòa. Tác giả xin bày tỏ lòng biết ơn sâu sắc đến thầy, người đã thường xuyên động viên, giúp đỡ, định hướng và đóng góp những ý kiến quý báu cho công việc của tác giả trong suốt thời gian học tập và làm nghiên cứu sinh. Tác giả cũng xin bày tỏ lòng biết ơn sâu sắc tới GS.TS. Vũ Đức Thi, người đã giúp đỡ tận tình và hướng dẫn tác giả từ khi làm luận văn Cao học cho đến khi hoàn thành bản luận án này. Tác giả xin trân trọng biết ơn Viện Công Nghệ Thông Tin – Viện Hàn Lâm Khoa Học và Công Nghệ Việt Nam, Học Viện Tài Chính và bộ môn Khoa Học Máy Tính – Đại học Sư Phạm Hà Nội đã có những quan tâm ưu ái và tạo điều kiện tốt cho tác giả trong thời gian làm nghiên cứu sinh. Tác giả cũng xin được tỏ lòng biết ơn sâu sắc tới gia đình, những người luôn động viên và giúp đỡ tác giả cả về tinh thần lẫn vật chất trong suốt thời gian học tập và làm nghiên cứu sinh. Xin cảm ơn các bạn bè đồng nghiệp gần xa đã động viên, giúp đỡ và khích lệ tác giả trong thời gian làm nghiên cứu sinh. iii Mục Lục Lời cam đoan ............................................................................................................. i Lời cảm ơn ................................................................................................................ ii Danh sách các ký hiệu ...............................................................................................v Danh mục hình vẽ................................................................................................... vii Danh mục bảng ........................................................................................................ ix MỞ ĐẦU ....................................................................................................................1 CHƢƠNG 1. TỔNG QUAN VỀ CHU TRÌNH TRONG ĐỒ THỊ .......................4 1.1. Một số khái niệm và quy ước ...........................................................................4 1.1.1. Các khái niệm cơ bản của lý thuyết đồ thị ........................................................... 4 1.1.2. Một số ký hiệu và quy ước ................................................................................... 7 1.2. Chu trình trong đồ thị 2-liên thông ...................................................................8 1.3. Chu trình Hamilton ...........................................................................................9 1.3.1. Độ phức tạp của bài toán ............................................................................. 10 1.3.2. Một số điều kiện cần .......................................................................................... 11 1.3.3. Một số điều kiện đủ đối với bậc của đỉnh .......................................................... 12 1.3.4. Một số thuật toán xác định chu trình Hamilton .................................................. 14 1.4. Bao đóng đồ thị...............................................................................................15 1.5. Chu trình Dominating .....................................................................................18 1.6. Chu trình trong đồ thị có tập láng giềng lớn...................................................20 1.7. Kết luận Chương 1 ..........................................................................................21 CHƢƠNG 2. MỘT SỐ LỚP ĐA THỨC CỦA BÀI TOÁN 2.1. Giới thiệu bài toán và ..........................22 ...................................................................22 2.2. Độ phức tạp của bài toán và 2.3. Độ phức tạp của bài toán ...........................................................24 ................................22 2.3.1. Một số kết quả với ............................................................................ 24 2.3.2. Chứng minh cho Định lý 2.3 .............................................................................. 27 2.3.3. Thuật toán đa thức nhận biết ba dạng đồ thị đặc biệt thỏa mãn 2.4. Bài toán .......... 48 ....................................................................................50 iv 2.5. Kết luận Chương 2 ..........................................................................................51 CHƢƠNG 3. THUẬT TOÁN ĐA THỨC XÁC ĐỊNH CHU TRÌNH HAMILTON TRONG ĐỒ THỊ VÀ ................................53 3.1. Thuật toán cho lớp đồ thị ............................................................53 3.2. Thuật toán cho lớp đồ thị ...............................................................57 3.3. Sử dụng bao đóng cho các lớp đồ thị có tổng bậc lớn ....................................59 3.4. Chương trình thực nghiệm ..............................................................................61 3.4.1. Giới thiệu chương trình ...................................................................................... 62 3.4.2. Bộ dữ liệu đầu vào ............................................................................................. 63 3.4.3. Đánh giá hiệu năng ............................................................................................. 64 3.5. Kết luận Chương 3 ..........................................................................................69 CHƢƠNG 4. ĐÁNH GIÁ ĐỘ DÀI CHU TRÌNH DÀI NHẤT TRONG ĐỒ THỊ 1-TOUGH VỚI ...........................................................................................70 4.1. Giới thiệu Giả thuyết Bauer ............................................................................70 4.2. Các Tính chất và Bổ đề...................................................................................70 4.3. Chứng minh cho các trường hợp ....................................................................79 4.4. Kết luận Chương 4 ..........................................................................................91 KẾT LUẬN ..............................................................................................................92 Những công trình đã công bố liên quan đến luận án ...........................................93 Tài liệu tham khảo ..................................................................................................94 v Danh sách các ký hiệu Đồ thị | | với tập đỉnh và tập cạnh Bậc (hay số đỉnh) của đồ thị Cạnh nối đỉnh và đỉnh Bậc của đỉnh trên đồ thị Bậc tối tiểu của Đồ thị đầy đủ với đỉnh Chỉ số ổn định trong của đồ thị Số thành phần liên thông của đồ thị Chỉ số liên thông của đồ thị Tập láng giềng của đỉnh Đồ thị trên đồ thị là đồ thị con của đồ thị . , với ⋃ ̅ . , với . Đồ thị bù của Đồ thị con thu được từ bằng cách loại bỏ tất cả các đỉnh của , Đồ thị thu được từ bằng cách loại bỏ cạnh , Đồ thị thu được từ bằng cách bổ sung cạnh nối [ ] Đồ thị con sinh của và trên tập đỉnh con Toughness của đồ thị Khoảng cách của hai đỉnh Phép kết nối đồ thị trong đồ thị và Đồ thị lũy thừa Bao đóng của đồ thị [ ] [ ] Nhãn của cạnh và nhãn của cạnh Tổng bậc nhỏ nhất của . đỉnh độc lập Tổng bậc nhỏ nhất của các cặp đỉnh có khoảng cách bằng 2. ⃗⃗⃗ Chu trình theo một chiều quay định hướng. ⃖⃗⃗⃗ Chu trình với chiều quay ngược với chiều của ⃗⃗⃗ theo chiều ⃗⃗⃗ . Đỉnh liền trước và đỉnh liền sau của , với . vi , ⃗⃗⃗ ⃖⃗⃗⃗ Đoạn đường trên Đường đi | || | với từ . theo chiều quay ⃗⃗⃗ . tới với các đỉnh cuối là . Số đỉnh của đường đi , chu trình . Độ dài (số cạnh) của đường đi , chu trình . Chu vi của , hay độ dài của chu trình dài nhất trong . Bài toán đường đi Hamilton (Hamiltonian Path) Bài toán chu trình Hamilton (Hamiltonian Cycle) Bài toán trong lớp đồ thị thỏa mãn Bài toán trong lớp đồ thị thỏa mãn | | | | . . , với với là một chu trình dài nhất của . là một chu trình dài nhất của . vii Danh mục hình vẽ Hình 1.1. Đồ thị . ..................................................................................... 5 Hình 1.2. Đường đi sau khi mở rộng đến đỉnh . .............................................................. 8 Hình 1.3. Đồ thị Petersen. .................................................................................................... 12 Hình 1.4. Đồ thị . ............................................................................................................... 13 Hình 1.5. Quá trình tạo bao đóng đồ thị. ............................................................................. 16 Hình 1.6. Biến đổi chu trình . ............................................................................................ 18 Hình 1.7. Chu trình Dominating. ......................................................................................... 19 Hình 1.8. Đồ thị Hình 2.1. Đồ thị . .......................................................................................................... 20 ̅ . .......................................................................... 23 ̅ Hình 2.2. Đồ thị . ............................................................................................... 24 Hình 2.3. Đồ thị Dạng 1, Định lý 2.3................................................................................... 25 Hình 2.4. Đồ thị Dạng 2, Định lý 2.3................................................................................... 26 Hình 2.5. Đồ thị Dạng 3, Định lý 2.3................................................................................... 26 Hình 2.6. Minh họa cho chứng minh phần c) Mệnh đề 2.3. ................................................ 30 Hình 2.7. Minh họa cho chứng minh Mệnh đề 2.4. ............................................................. 31 Hình 2.8. Đồ thị trong phần chứng minh I, Định lý 2.3. .................................................. 33 Hình 2.9. Minh họa cho Trường hợp 1, phần chứng minh II, Định lý 2.3. ......................... 34 Hình 2.10. Minh họa cho Trường hợp 2, phần chứng minh II, Định lý 2.3. ....................... 35 Hình 2.11. Minh họa cho Trường hợp 2.1, phần chứng minh II, Định lý 2.3. .................... 36 Hình 2.12. Minh họa đỉnh kề với và , Trường hợp 2.1. .......................................... 36 Hình 2.13. Đồ thị trong phần chứng minh Trường hợp 2.1, Định lý 2.3. ........................ 37 Hình 2.14. Minh họa cho chứng minh Khẳng định 2.9. ...................................................... 37 Hình 2.15. Minh họa cho chứng minh Khẳng định 2.10. .................................................... 38 Hình 2.16. Minh họa cho chứng minh Khẳng định 2.12. .................................................... 39 Hình 2.17. Minh họa cho chứng minh Khẳng định 2.13. .................................................... 40 Hình 2.18. Đồ thị trong phần chứng minh Trường hợp 2.2, Định lý 2.3. ........................ 41 Hình 2.19. Minh họa cho Trường hợp 2.3, phần chứng minh II, Định lý 2.3. .................... 41 Hình 2.20. Minh họa cho Trường hợp 3, phần chứng minh II, Định lý 2.3. ....................... 42 Hình 2.21. Minh họa cho chứng minh Khẳng định 2.16. .................................................... 43 Hình 2.22. Minh họa cho chứng minh Khẳng định 2.18. .................................................... 43 Hình 2.23. Minh họa cho chứng minh Khẳng định 2.20. .................................................... 44 Hình 2.24. Minh họa cho chứng minh Khẳng định 2.21. .................................................... 45 Hình 2.25. Minh họa cho chứng minh Khẳng định 2.24. .................................................... 46 Hình 2.26. Đồ thị trong phần chứng minh Trường hợp 3.2, Định lý 2.3. ........................ 47 viii Hình 2.27. Minh họa cho Trường hợp 3.3, phần chứng minh II, Định lý 2.3. .................... 48 Hình 3.1. Mở rộng chu trình theo trường hợp thứ 2 và 3 của Thuật toán 3.2. ................. 58 Hình 3.2. Một số chương trình tìm chu trình Hamilton khác (nguồn [44]) ......................... 60 Hình 3.3. Sơ đồ thuật toán xác định chu trình Hamilton sử dụng bao đóng đồ thị ............. 61 Hình 3.4. Sơ đồ khối thực hiện chương trình ...................................................................... 62 Hình 3.5. Biểu đồ thời gian chạy Chương trình 1 và Chương trình 2 theo số đỉnh ............. 64 Hình 3.6. Chu trình ban đầu và vòng lặp mở rộng . ...................................................... 65 Hình 3.7. Biểu đồ thời gian chạy Chương trình 2 trên đồ thị S3-2000 theo độ dài chu trình khởi tạo ban đầu. .................................................................................................................. 68 Hình 4.1. Minh họa việc thiết lập các đỉnh trên . ............................................................. 72 Hình 4.2. Minh họa Trường hợp 1, Bổ đề 4.2. .................................................................... 74 Hình 4.3. Minh họa cho chứng minh Bổ đề 4.3. .................................................................. 74 Hình 4.4. Minh họa cho chứng minh Bổ đề 4.4. .................................................................. 75 Hình 4.5. Minh họa cho chứng minh Bổ đề 4.5. .................................................................. 75 Hình 4.6. Minh họa cho chứng minh Bổ đề 4.6. .................................................................. 76 Hình 4.7. Minh họa cho chứng minh Bổ đề 4.7. .................................................................. 76 Hình 4.8. Minh họa cho chứng minh Bổ đề 4.9. .................................................................. 77 Hình 4.9. Minh họa cho chứng minh Bổ đề 4.10. ................................................................ 78 Hình 4.10. Minh họa cho chứng minh Khẳng định 4.1. ...................................................... 79 Hình 4.11. Minh họa cho chứng minh Khẳng định 4.2. ...................................................... 79 Hình 4.12. Minh họa cho chứng minh Khẳng định 4.5. ...................................................... 81 Hình 4.13. Minh họa cho chứng minh Khẳng định 4.7. ...................................................... 81 Hình 4.14. Minh họa cho chứng minh Khẳng định 4.8. ...................................................... 82 Hình 4.15. Minh họa cho Trường hợp 2.1. .......................................................................... 84 Hình 4.16. Minh họa cho chứng minh Khẳng định 4.11. .................................................... 85 Hình 4.17. Minh họa cho chứng minh Khẳng định 4.12. .................................................... 85 Hình 4.18. Minh họa cho chứng minh Mệnh đề 4.3. ........................................................... 87 Hình 4.19. Minh họa cho chứng minh Khẳng định 4.19. .................................................... 88 Hình 4.20. Minh họa cho chứng minh Khẳng định 4.21. .................................................... 89 Hình 4.21. Minh họa cho chứng minh Mệnh đề 4.4. ........................................................... 90 ix Danh mục bảng Bảng 1.1. Một số thuật toán Backtrack và Heuristic xác định chu trình Hamilton ............. 14 Bảng 3.1. Các chương trình thực nghiệm xác định chu trình Hamilton .............................. 62 Bảng 3.2. Danh sách các đồ thị được tiến hành thực nghiệm .............................................. 63 Bảng 3.3. Thống kê thời gian chạy chương trình khi sử dụng Thuật toán 1.1 .................... 64 Bảng 3.4. Tổng hợp thời gian chạy Chương trình 1 trước và sau khi cải tiến. .................... 67 Bảng 3.5. Tổng hợp thời gian chạy Chương trình 2 trước và sau khi cải tiến. .................... 67 Bảng 3.6. Thống kê thời gian chạy Chương trình 2 trên đồ thị S3-2000 theo độ dài chu trình khởi tạo ban đầu. ......................................................................................................... 68 1 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 2 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 với lớp đồ thị thỏa mãn vẫn còn là bài toán với mọi . 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. 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 bài báo [8], các tác giả D. Bauer, G. Fan, H. J. Veldman đã đư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 trên các lớp đồ thị có tổng bậc đó tập trung vào trường hợp . và lớn, trong  Đánh giá độ phức tạp của bài toán theo một tham số . Xác định bài toán chuyển từ lớp sang lớp . để  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ố 3 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 (với nguyên dương, số thực là tham số) như sau: Instance: Đồ thị Question: . có là đồ thị Hamilton? Instance: Đồ thị Question: thỏa mãn và thỏa mãn . có là đồ thị Hamilton? 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ố để tìm ra các lớp đa thức của bài toán . Chƣơng 3: Thuật toán đa thức xác định chu trình Hamilton trong đồ thị và . 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 đồ thị và , sau đó tác giả tiến hành thực nghiệm trên các đồ thị lớn (hàng 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 đó, 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. Chƣơng 4: Đánh giá độ dài chu trình dài nhất trong đồ thị 1-tough với . 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ả Bauer, Fan, Veldman trong [8] về cận dưới của độ dài chu trình dài nhất rằng: Nếu là đồ thị 1-tough và thì . 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, 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 đúng nào cho Giả thuyết này và đây vẫn là vấn đề mở. 4 CHƢƠNG 1. TỔNG QUAN VỀ CHU TRÌNH TRONG ĐỒ THỊ 1.1. Một số khái niệm và quy ƣớc 1.1.1. Các khái niệm cơ bản của lý thuyết đồ thị Trong luận án này, ta chỉ xét tới các đồ thị hữu hạn, đơn, vô hướng và không có trọng số. Các khái niệm, ký hiệu chủ yếu tham khảo trong [16]. Một đồ thị là một cặp , trong đó là tập đỉnh và [ ] là tập cạnh. Số đỉnh của đồ thị gọi là bậc của đồ thị , được viết là | |. Trong luận án luôn sử dụng ký hiệu là số đỉnh của đồ thị . Hai đỉnh và được gọi là kề nhau nếu là một cạnh của đồ thị . Nếu mọi đỉnh của kề nhau từng đôi một thì được gọi là đồ thị đầy đủ. Một đồ thị đầy đủ có đỉnh được ký hiệu là . Tập đỉnh con là độc lập nếu mọi cặp đỉnh thuộc đều không kề nhau. Ký hiệu (hay viết đơn giản là nếu không xảy ra sự hiểu lầm) là số phần tử của tập độc lập lớn nhất trong và được gọi là số ổn định trong của . Với đỉnh , ta ký hiệu (hay viết đơn giản là ) là tập láng giềng của trong , . Bậc của đỉnh , ký hiệu bởi | |. (hay viết đơn giản là ) là số phần tử của , Đồ thị được gọi là đồ thị con của đồ thị , ký hiệu là , nếu và . Với , ta ký hiệu là đồ thị con thu được từ đồ thị bằng cách loại bỏ tất cả các đỉnh thuộc và các cạnh nối tới các đỉnh đó. Ngoài ra, đồ thị con sinh của trên tập đỉnh , ký hiệu là [ ], được định nghĩa là đồ thị trên tập đỉnh và bảo toàn tập cạnh, tức là hai đỉnh trong [ ] kề nhau khi và chỉ khi chúng kề nhau trong . Trong luận án thường viết đơn giản là thay cho [ ]. Với thì ta ký hiệu là tập hợp các đỉnh thuộc và có láng giềng thuộc , tức là: . Ta cũng thường viết thay cho nếu không xảy ra sự hiểu lầm. Đồ thị (hoặc ) và (hoặc ) tương ứng được ký hiệu là đồ thị thu được từ đồ thị bằng cách loại bỏ hoặc bổ sung cạnh nối giữa hai đỉnh và . 5 Đồ thị bù của [ ] . , ký hiệu bởi ̅ , là đồ thị có tập đỉnh là và tập cạnh là Hai đồ thị và được gọi là rời nhau nếu . Với số nguyên dương cho trước và đồ thị đôi một rời nhau , phép kết nối đồ thị này là một đồ thị được ký hiệu bởi với tập đỉnh là và tập cạnh là với mọi . Ví dụ, , hay với số nguyên thì là đồ thị được biểu diễn như trong Hình 1.1. Hình 1.1. Đồ thị . 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 đỉnh không quá một lần. Một đường đi (đơn) là một đồ thị con không rỗng có cấu trúc: và trong đó, với mọi . Các đỉnh . được nối bởi , và gọi là các đỉnh cuối; các đỉnh gọi là các đỉnh trong của . Số cạnh của đường đi gọi là độ dài của nó, ký hiệu là . Nếu là một đường đi và thì được gọi là một chu trình, khi đó chu trình được viết như sau: . Số cạnh của chu trình gọi là độ dài của nó, ký hiệu là . Chu trình có độ dài được ký hiệu là . Độ dài của chu trình dài nhất trong đồ thị được gọi là chu vi, ký hiệu là . Đồ thị được gọi là liên thông nếu hai đỉnh bất kỳ của nó được nối với nhau bởi một đường đi trong . Nếu không liên thông thì sẽ bao gồm các đồ thị con liên thông và gọi là các thành phần liên thông của . Ký hiệu số thành phần liên 6 thông của là . Đỉnh được gọi là đỉnh cắt nếu được gọi là tập đỉnh cắt nếu . . Tập đỉnh | Đồ thị được gọi là -liên thông ( ) nếu | và thông với mọi tập mà | | . Số nguyên lớn nhất thỏa mãn thông gọi là chỉ số liên thông của , ký hiệu là . Khoảng cách giữa hai đỉnh , ký hiệu là nếu cùng thuộc một thành phần liên thông thì ngắn nhất nối hai đỉnh đó, ngược lại thì . Với số nguyên dương liên là -liên , được định nghĩa như sau: là độ dài của đường đi , ta định nghĩa như sau: là tập đỉnh độc lập , Trường hợp thì đặt cặp đỉnh có khoảng cách 2, ta định nghĩa: . Với và chỉ xét tới các , Trong luận án thường viết lần lượt thay cho và nếu không xảy ra sự hiểu lầm. Nếu không là đồ thị đầy đủ, ta định nghĩa giá trị và như sau: | | | | Trường hợp là đồ thị đầy đủ thì đặt thường viết đơn giản là lần lượt thay cho Đồ thị | | được gọi là -tough ( , . . Ta cũng và . ) nếu với mọi tập đỉnh cắt thì . Đồ thị 1-tough cũng thường được gọi là đồ thị tough. Lƣu ý 1.1.  Việc kiểm tra tính liên thông và tìm các thành phần liên thông của đồ thị chỉ cần một thuật toán đa thức không quá phép toán thực hiện [1].  Việc tìm một đường đi giữa hai đỉnh của đồ thị cũng chỉ cần một thuật toán đa thức không quá phép toán thực hiện [1]. Nếu sử dụng phương pháp tìm kiếm theo chiều rộng (BFS) thì đường đi tìm được sẽ là đường đi ngắn nhất. 7  Mọi đồ thị tough đều là đồ thị 2-liên thông nhưng điều ngược lại không đúng, chẳng hạn như đồ thị ̅ (với nguyên dương) là đồ thị 2-liên thông nhưng không là đồ thị tough.  Việc nhận biết một đồ thị có là 2-liên thông hay không chỉ cần một thuật toán đa thức không quá phép toán thực hiện nên đây là vấn đề thuộc lớp . Tuy nhiên, việc nhận biết một đồ thị có là tough hay không lại là vấn đề thuộc lớp [6]. 1.1.2. Một số ký hiệu và quy ƣớc 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ị . Ví dụ, viết tương ứng thay cho . Giả sử là một đường đi và là một chu trình của đồ thị . Trong luận án, đôi khi ta có thể xem như là một tập đỉnh con của (tương ứng thay cho ). Một đường đi là mở rộng (theo tập đỉnh) của đường đi . Tương tự, một chu trình là mở rộng của chu trình nếu nếu . Với , ta ký hiệu là đoạn đường chạy dọc theo từ đỉnh tới đỉnh . Như vậy, nếu là các đỉnh cuối của thì cũng chính là . Ngoài ra, | | quy ước là số đỉnh nằm trên đoạn đường con này. . Ta quy định một chiều quay Giả sử chu trình ⃗⃗⃗ theo thứ tự chỉ số các đỉnh và chỉ số các đỉnh được lấy theo , ký hiệu lần lượt là đỉnh liền trước và liền sau của đã định. Với tập đỉnh thì , nguyên dương , ký hiệu . Ta ký hiệu đoạn đường trên theo chiều quay đã quy định bởi ký hiệu là ⃖⃗⃗⃗ . Nếu . Với đỉnh theo chiều quay . Với số và bắt đầu từ một đỉnh và kết thúc tại ⃗⃗⃗ , đoạn đường đó theo chiều ngược lại là một thành phần liên thông của , ký hiệu là tập hợp các láng giềng của trên . Một dãy cung ngoại biên nối hai đỉnh trên là một đường đi có các đỉnh cuối là 2 đỉnh đó và các đỉnh trong thuộc . Đặc biệt, một cạnh nối 2 đỉnh không liền nhau trên cũng là một dãy cung ngoại biên. Đôi khi ta cũng thường không viết dấu phẩy (,) ngăn cách giữa các đỉnh của một chu trình hoặc một đường đi. Ví dụ, viết thay cho . 8 1.2. Chu trình trong đồ thị 2-liên thông Trước hết, ta có một khẳng định quan trọng sau cho đồ thị 2-liên thông: Mệnh đề 1.1. Mọi đồ thị 2-liên thông đều có chu trình. Việc chứng minh Mệnh đề 1.1 là khá đơn giản và cũng đã được đề cập trong [16]. Có thể xây dựng thuật toán đa thức xác định một chu trình bất kỳ cho đồ thị 2liên thông bằng cách là xuất phát từ một đường đi độ dài 1 (gồm 2 đỉnh kề nhau), sau đó ta sẽ liên tục mở rộng đường đi cho đến khi nào có đỉnh cuối thỏa mãn tính | chất có láng giềng thuộc đoạn đường trước đó và | (Hình 1.2). Khi đó, ta sẽ có chu trình gồm các đỉnh từ tới dọc theo đường , sau đó quay trở lại . Hình 1.2. Đường đi sau khi mở rộng đến đỉnh . Thuật toán 1.1. Xác định một chu trình trong đồ thị 2-liên thông Input: Đồ thị 2-liên thông . Output: Một chu trình của . Procedure Create_Cycle() Begin Tìm một cạnh ; While ( ; ; ) Do Begin Lấy là một đỉnh cuối của If and | | ; Then Else Begin Tìm một đỉnh ; End; End; End; ; 9 Thuật toán trên là đúng đắn vì trong trường hợp đỉnh cuối không có láng | giềng thuộc thì sẽ tồn tại một đỉnh và | , vì nếu không thì và do đó đồ thị không 2-liên thông (khi ta loại bỏ đỉnh liền trước trên đoạn đường thì số thành phần liên thông của đồ thị sẽ lớn hơn 1). Thuật toán sẽ kết thúc sau không quá phép toán thực hiện. Nếu là một chu trình dài nhất của , ta có Bổ đề quan trọng sau: Bổ đề 1.1. Cho đồ thị 2-liên thông với , là một thành phần liên thông của đỉnh và là một chu trình dài nhất của . Nếu có không quá đỉnh thì : (a) . (b) Không có dãy cung ngoại biên nối hai đỉnh của (c) Nếu với hoặc ⃗⃗⃗ thì không có . Tương tự, không có ⃗⃗⃗ . sao cho đồng thời có sao cho đồng thời có . Việc chứng minh các phần (a), (b), (c) của Bổ đề 1.1 là đơn giản và đã trở thành chuẩn (luôn chứng minh bằng phản chứng và chỉ ra mâu thuẫn bằng cách mở rộng được chu trình ) nên ta không chứng minh lại ở đây. Với giả thiết là chu trình với không quá đỉnh, ta có kết quả sau: Bổ đề 1.2. Cho đồ thị không quá đỉnh, và ta có: 2-liên thông với đỉnh và là một chu trình của với là một thành phần liên thông của . Nếu là tập đỉnh độc lập thì với mọi và với mọi . Chứng minh. Có | | suy ra | | | | | | | | | | | | | | | | | | | | | | | | | | | | |. Theo giả thiết |, do đó . (Đpcm) 1.3. Chu trình Hamilton Chu trình đi qua mọi đỉnh của đồ thị, mỗi đỉnh đi qua đúng một lần, gọi là chu trình Hamilton. Đồ thị có chu trình Hamilton được gọi là đồ thị Hamilton. Tương tự, đường đi qua mọi đỉnh của đồ thị, mỗi đỉnh đi qua đúng một lần, gọi là đường Hamilton và đồ thị có đường Hamilton gọi là đồ thị nửa Hamilton.