Tóm tắt Luận án 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

ng ứng thay cho ). Một đường đi là mở rộng (theo tập đỉnh) của đường đi nếu . Tương tự, một chu trình là mở rộng của chu trình 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. Giả sử chu trình . Ta quy định một chiều quay ⃗⃗ ⃗ theo thứ tự chỉ số các đỉnh (chỉ số được lấy theo ). Với đỉnh , ký hiệu lần lượt là đỉnh liền trước và liền sau của theo chiều quay đã định. Với tập đỉnh thì , . Với số nguyên dương , ký hiệu 5 và . Ta ký hiệu đoạn đường trên bắt đầu từ một đỉnh và kết thúc tại theo chiều quay đã quy định bởi ⃗⃗ ⃗ , đoạn đường đó theo chiều ngược lại ký hiệu là ⃖⃗⃗⃗ . Nếu 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 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 . 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. Lịch sử phát sinh đồ thị Hamilton được xuất phát từ trò chơi đố vui của William Rowan Hamilton vào năm 1859. 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 Cho đến nay, vấn đề chu trình Hamilton vẫn còn là mở và trở thành một vấn đề trung tâm của lý thuyết đồ thị với rất nhiều công trình nghiên cứu. Thông qua ba bài tổng quan của Ronald J. Gould trong [25], [26], [27] thì có thể thấy rằng trong vòng 20 năm trở lại đây có khoảng 400 bài báo khoa học nghiên cứu về chu trình Hamilton đượ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 luận án sẽ nghiên cứu chu trình Hamilton theo hướng sau:  Nghiên cứu bài toán trên lớp đồ thị có tổng bậc và lớn.  Nghiên cứu độ phức tạp của bài toán và xác định ranh giới để 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 mà bài toán thuộc lớp . 1.3.1. Độ phức tạp của bài toán Bài toán đã được chứng minh trong [23] là các bài toán . (Hamiltonian Cycle Problem) Instance: Đồ thị . Question: có là đồ thị Hamilton? Một số tác giả đã nghiên cứu đến độ phức tạp của bài toán trên những lớp đồ thị đặc biệt, chẳng hạn như trong [37] đánh giá độ phức tạp trên lớp đồ thị có hướng phẳng, hay 6 trong [3] nghiên cứu trên hai lớp đồ thị dạng lưỡng phân... Trong [15], các tác giả đã chỉ ra rằng bài toán vẫn còn là bài toán trên lớp đồ thị với mọi : Định lý 1.1 [15, Định lý 16]. là bài toán với mọi . Kết quả trên là một tiền đề quan trọng để tác giả tiếp tục nghiên cứu đến độ phức tạp của bài toán trên các lớp đồ thị có tổng bậc và lớn. 1.3.3. Một số điều kiện đủ đối với bậc của đỉnh Các kết quả nghiên cứu về chu trình Hamilton hầu hết tập trung ở điều kiện đủ, đặc biệt là điều kiện đủ đối với bậc của đỉnh. Ta bắt đầu bằng với một kết quả của Dirac: Định lý 1.4 [17]. Nếu đồ thị với đỉnh và bậc mỗi đỉnh đều không nhỏ hơn thì là đồ thị Hamilton. Định lý Dirac là trường hợp riêng của Định lý Ore. Định lý 1.5 [36]. Nếu đồ thị với đỉnh và thì là đồ thị Hamilton. Với đồ thị tough, mở rộng cho Định lý Ore, Jung có kết quả sau: Định lý 1.6 [29]. Cho là đồ thị 1-tough với đỉnh và . Khi đó,G là đồ thị Hamilton. Mở rộng kết quả cho có: Định lý 1.7 [18]. Cho G là đồ thị 1-tough với đỉnh và . Khi đó, là đồ thị Hamilton. Với đồ thị -liên thông, Bondy đưa ra kết quả tổng quát cho như sau: Định lý 1.8 [11]. Nếu là đồ thị -liên thông thỏa mãn thì là đồ thị Hamilton. Liên quan đến khoảng cách có kết quả sau: Định lý 1.10 [32, Định lý 5]. Cho là đồ thị 2-liên thông với đỉnh thỏa mãn . Khi đó xảy ra một trong hai trường hợp sau: 1. là đồ thị Hamilton. 2. là số lẻ và ̅ ̅ ̅ . 1.3.4. Một số thuật toán xác định chu trình Hamilton Các nghiên cứu về thuật toán xác định chu trình Hamilton được tiếp cận theo các hướng sau:  Thuật toán Backtrack (Quay lui).  Thuật toán Heuristic.  Thuật toán tìm kiếm chu trình Hamilton cho các lớp đồ thị đặc biệt. 7 Các thuật toán Backtrack luôn đảm bảo tìm được chu trình Hamilton (nếu có) hoặc sẽ kết thúc sau khi vét cạn các trường hợp mà đồ thị không có chu trình Hamilton, tuy nhiên khả năng thực hiện hạn chế và thời gian chạy không khả thi trên các đồ thị lớn. Các thuật toán Heuristic có sự cải tiến về khả năng thực hiện trên các đồ thị lớn và thời gian chạy tuyến tính hoặc đa thức, tuy nhiên nó không đảm bảo rằng sẽ tìm được chu trình Hamilton, mặc dù được thực hiện trên đồ thị Hamilton. Dưới đây là một số thuật toán Backtrack và Heuristic xác định chu trình Hamilton trong đồ thị [5], [12], [38]: Bảng 1.1. Một số thuật toán Backtrack và Heuristic xác định chu trình Hamilton Thuật toán Tác giả Loại Pósa Pósa Heuristic UHC Angluin and Valiant Heuristic HAM Bollobas, Fenner and Frieze Heuristic SparseHam Frieze Heuristic HideHam Broder, Frieze and Shamir Heuristic DB2 Brunacci Heuristic LongPath Kocay and Li Heuristic LinearHam Thomason Heuristic Snakes and Ladders P. Baniasadi, V. Ejov, J.A. Filar, M. Haythorpe, S. Rossomakhine Heuristic MultiPath Kocay Backtrack MultiPath cải tiến Andrew Chalaturnyk Backtrack KTC Shufelt and Berliner Backtrack Một số tác giả khác đã nghiên cứu tới việc xây dựng các thuật toán xác định chu trình Hamilton trong các lớp đồ thị đặc biệt. Các thuật toán này là chính xác và đảm bảo tìm được chu trình Hamilton, thời gian đa thức, tuy nhiên nhược điểm là không thực hiện được trên đồ thị tổng quát. Gần đây, các tác giả trong [28] đã đưa ra thuật toán thời gian trên đồ thị Circular-Arc, trong [22] sử dụng phương pháp “tham lam” và 2-matching để xây dựng thuật toán thời gian xác định chu trình Hamilton trong đồ thị ngẫu nhiên Với đồ thị Ore (lớp đồ thị ), một số tác giả cũng đưa ra thuật toán đa thức để xác định chu trình Hamilton, chẳng hạn như thuật toán do Albertson đề xuất [4] 1.4. Bao đóng đồ thị Bổ đề 1.2 [10]. Giả sử đồ thị có bậc và hai đỉnh không kề nhau thỏa mãn . Khi đó, là đồ thị Hamilton khi và chỉ khi là đồ thị Hamilton. Khái niệm bao đóng của đồ thị được Bondy và Chvátal đưa ra lần đầu tiên trong [10]. Bao đóng của đồ thị , ký hiệu bởi là đồ thị thu được từ bằng cách bổ sung thêm các cạnh nối các cặp đỉnh không kề nhau có tổng bậc không nhỏ hơn , quá trình này được thực hiện cho đến khi nào không còn cặp đỉnh không kề nhau mà có tổng bậc không nhỏ hơn nữa. Bao đóng của một đồ thị luôn xác định duy nhất, không phụ thuộc vào thứ tự cạnh mới được thêm vào [2]. 8 Hình 1.5. Quá trình tạo bao đóng đồ thị. Trong việc bổ sung lần lượt các cạnh mới để tạo bao đóng , ta thực hiện việc gán nhãn tăng dần theo thứ tự các cạnh được bổ sung bằng mảng . Trước hết, [ ] với mọi cạnh và đặt . Khi cạnh mới đầu tiên được bổ sung, ta gán [ ] , và thu được đồ thị mới . Quá trình được thực hiện liên tục cho đến khi không có cạnh nào được bổ sung nữa và thu được đồ thị cuối cùng là . Rõ ràng là: . Thuật toán 1.2. Xây dựng đồ thị bao đóng và gán nhãn cho các cạnh. Input: Đồ thị . Output: Đồ thị và các cạnh được gán nhãn. Procedure Construct_Cl Begin For each do Begin [ ] ; For each do If Then [ ] [ ] ; End; For each do [ ] ; ; Repeat Stop True; For each do For each do If and [ ] [ ] Then Begin Stop False; ; ; [ ] ; [ ] [ ] ; [ ] [ ] ; End; Until Stop; End; Nếu là một đồ thị con của , ta đặt: [ ] [ ] . 9 Mệnh đề 1.2. Nếu thì là đồ thị Hamilton khi và chỉ khi là đồ thị Hamilton. Thuật toán 1.3. Biến đổi chu trình Hamilton của đồ thị bao đóng. Input: là một chu trình Hamilton của . Output: Một chu trình Hamilton của đồ thị . Procedure TransformCycle( ) Begin While ( [ ] ) do Begin Tìm [ ] [ ]; Tìm và [ ] [ ] [ ]; ; Đánh số lại các đỉnh trên theo thứ tự mới: ; End; End; 1.6. Chu trình trong đồ thị có tập láng giềng lớn Định lý 1.20 [8]. Nếu là đồ thị 2-liên thông và thì . Định lý 1.21 [8]. Nếu là đồ thị 1-tough và thì . Bauer, Fan, Veldman đã đưa ra Giả thuyết quan trọng sau: Giả thuyết 1.3 [8, Giả thuyết 27]. Nếu là đồ thị 1-tough và thì . 1.7. Kết luận Chƣơng 1 Như vậy, chương này đầu tiên đã giới thiệu các khái niệm cơ bản nhất của lý thuyết đồ thị cần thiết cho luận án. Kế đến giới thiệu các Bổ đề, Thuật toán cơ bản, đặc biệt là bao đóng đồ thị làm nền tảng cơ sở quan trọng cho các chứng minh trong luận án. Cuối cùng trình bày tổng quan về chu trình trong đồ thị, tập trung trọng tâm tới chu trình Hamilton với các vấn đề nêu ra là: độ phức tạp bài toán của , một số điều kiện cần và đủ cho một đồ thị là Hamilton, một số thuật toán để xác định chu trình Hamilton trong đồ thị. Ngoài ra, chu trình Dominating, chu trình trong đồ thị có tập láng giềng lớn cũng được đề cập tới. Định lý 1.1 của các tác giả trong [15] đã chỉ ra rằng bài toán trong lớp đồ thị vẫn còn là bài toán với mọi là tiền đề để tác giả tiếp tục nghiên cứu bài toán cho lớp đồ thị tổng quát hơn theo các giá trị (với tổng quát) và trong Chương 2 và Chương 3. Giả thuyết 1.3 của các tác giả trong [8] đưa ra đánh giá về độ 10 dài của chu trình dài nhất hiện nay vẫn còn là vấn đề mở, trong Chương 4 tác giả sẽ đưa ra một chứng minh cho Giả thuyết này. 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à Với số nguyên dương và số thực ta xét bài toán tổng quát sau: Instance: Đồ thị thỏa mãn . Question: có là đồ thị Hamilton? Với , mở rộng cho bài toán khi ta chỉ xét tới các cặp đỉnh khoảng cách 2: Instance: Đồ thị thỏa mãn . Question: có là đồ thị Hamilton? Trường hợp thì và chính là bài toán trong trường hợp tổng quát. 2.2. Độ phức tạp của bài toán và Từ Định lý 1.1, dễ dàng suy ra Hệ quả sau: Hệ quả 2.1. là bài toán . Định lý 2.1. là bài toán . Định lý 2.2. là bài toán . Như vậy, với thì bài toán vẫn còn là bài toán . Giả thuyết 2.1. Với mọi số nguyên dương thì bài toán thuộc lớp . 2.3. Độ phức tạp của bài toán 2.3.1. Một số kết quả với Từ Định lý 1.4 (Dirac) và Định lý 1.5 (Ore) ta hiển nhiên có: Hệ quả 2.2. và là các bài toán thuộc lớp . Từ Định lý 1.8 (Bondy) cho trường hợp , ta có: Hệ quả 2.3. Mọi đồ thị 2-liên thông thỏa mãn là đồ thị Hamilton. Điều kiện là tốt nhất có thể theo nghĩa là tồn tại vô hạn đồ thị 2-liên thông thỏa mãn nhưng không Hamilton, chẳng hạn các đồ thị ̅ với . 11 Hệ quả 2.4. là bài toán thuộc lớp . Hệ quả 2.5. là bài toán thuộc lớp . Với kết quả của Bondy (Định lý 1.8) cho trường hợp thì không thể kết luận cho độ phức tạp của bài toán vì điều kiện 3-liên thông không phải là điều kiện cần của một đồ thị Hamilton. Ta sẽ chứng minh cũng là bài toán thuộc lớp bằng việc khảo sát lớp đồ thị thỏa mãn . Định lý 2.3. Cho đồ thị 2-liên thông thỏa mãn . Khi đó, hoặc là đồ thị Hamilton, hoặc và có cấu trúc thuộc một trong 3 dạng sau: 1. Dạng 1: Tồn tại | | sao cho . (Hình 2.1) Hình 2.1. Đồ thị Dạng 1, Định lý 2.3. 2. Dạng 2: có ba đồ thị con đầy đủ và một đỉnh sao cho tồn tại , , và . Hơn nữa, tồn tại ba đỉnh , , sao cho . Ngoài ra, đỉnh có thể kề với bất kỳ đỉnh còn lại nào. (Hình 2.2) Hình 2.2. Đồ thị Dạng 2, Định lý 2.3. 3. Dạng 3: có ba đồ thị con đầy đủ | | | | | | và tồn tại các đỉnh với sao cho . (Hình 2.3) 12 Hình 2.3. Đồ thị Dạng 3, Định lý 2.3. Hệ quả 2.6. Mọi đồ thị 2-liên thông thỏa mãn và là đồ thị Hamilton. Từ thuật toán đa thức nhận biết 3 dạng đồ thị đặc biệt không Hamilton trong Định lý 2.3, ta có: Định lý 2.4. là bài toán thuộc lớp . 2.4. Bài toán Từ Định lý 1.10, để đánh giá được độ phức tạp của bài toán ta sẽ đưa ra thuật toán thời gian sau: Thuật toán 2.4. Nhận biết đồ thị thuộc dạng: ̅ ̅ ̅ . Input: Đồ thị . Output: Is_Graph4 = True nếu ̅ ̅ ̅ , ngược lại, Is_Graph4 = False. Chương trình: Function Boolean Is_Graph4 Begin If ( ) Then Return False; Tính bậc các đỉnh của ; ; For each do If ( ) Then ; If (| | ) and ( là tập đỉnh độc lập) Then Return True Else Return False; End; Hệ quả 2.7. là bài toán thuộc lớp . Hệ quả 2.8. là bài toán thuộc lớp . 13 2.5. Kết luận Chƣơng 2 Bài toán đã được đánh giá độ phức tạp trong [15] và Chương này tác giả đã tiếp tục nghiên cứu mở rộng theo hai bài toán (với nguyên dương tổng quát) và . Các kết quả đạt được như sau:  Với thì các bài toán vẫn còn là bài toán .  Với thì các bài toán và thuộc lớp . Như vậy, có thể nói rằng Giả thuyết 2.1 đã được tác giả giải quyết đến trường hợp , với thì vẫn còn là vấn đề mở. Dựa trên các kết quả đạt được và Hệ quả 2.6, tác giả đưa ra Giả thuyết thứ hai: Giả thuyết 2.2. Với mọi số nguyên dương , nếu đồ thị 2-liên thông thỏa mãn và thì là đồ thị Hamilton. CHƢƠNG 3. THUẬT TOÁN ĐA THỨC XÁC ĐỊNH CHU TRÌNH HAMILTON TRONG ĐỒ THỊ VÀ Chương này tác giả sẽ đề xuất các thuật toán đa thức xác định chu trình Hamilton cho hai lớp đồ thị và . Thêm vào đó, tác giả đề xuất việc sử dụng bao đóng đồ thị để mở rộng lớp đồ thị thực hiện thuật toán. Cuối cùng, tác giả tiến hành thực nghiệm trên các đồ thị có số đỉnh lớn để cho thấy tính hiệu quả và khả thi thực hiện của các thuật toán đề xuất. 3.1. Thuật toán cho lớp đồ thị Bổ đề 3.1. Cho là đồ thị thỏa mãn và là đồ thị Hamilton. là một chu trình bất kỳ trong , là một thành phần liên thông của . Giả sử các đỉnh của được đánh số theo một chiều quay trên lần lượt là . Nếu có không quá đỉnh thì sẽ xảy ra một trong các trường hợp sau: 1. Tồn tại sao cho . 2. Tồn tại với . 3. Tồn tại , khi đó kề với tất cả các đỉnh , 4. Tồn tại sao cho . a. Thuật toán 3.1. Xác định chu trình Hamilton cho đồ thị . Input: Đồ thị 2-liên thông thỏa mãn . Output: Chu trình Hamilton của nếu là đồ thị Hamilton, hoặc trả lời không có chu trình Hamilton. Procedure Hamilton2*; 14 BEGIN // Kiểm tra không là đồ thị Hamilton 1: If ( ̅ ̅ ̅ ) Then 2: Begin 3: Thông báo không có chu trình Hamilton; 4: Kết thúc; 5: End; // Trường hợp là đồ thị Hamilton 6: Tìm một chu trình tùy ý của đồ thị ; // Vòng lặp mở rộng tập đỉnh của 7: While | | Do 8: Begin 9: Tìm một thành phần liên thông của – ; 10: Đánh số các đỉnh của lần lượt là ; // Mở rộng chu trình theo 4 trường hợp 11: If tồn tại Then 12: Begin 13: Tìm sao cho ; 14: Tìm một đường đi nối x với y trong ; 15: Thay thế thành chu trình mới ⃗⃗ ⃗ ; 16: End 17: Else If tồn tại Then 18: Begin 19: Tìm sao cho ; 20: Tìm một đường đi nối x với y trong ; 21: Thay thế thành chu trình mới ⃖⃗⃗⃗ ⃗⃗ ⃗ ; 22: End 23: Else If tồn tại Then 24: Begin 25: Chọn tùy ý và tìm sao cho ; 26: Tìm một đường đi nối x với y trong ; 27: Thay thế thành chu trình mới ⃖⃗⃗⃗ ⃗⃗ ⃗ ; 28: End 29: Else 30: Begin 31: Tìm và tìm sao cho ; 32: Tìm một đường đi nối x với y trong ; 33: Thay thế thành chu trình ⃗⃗ ⃗ ⃗⃗ ⃗ ; 34: End; 35: End; END; Thuật toán 3.1 cần không quá phép toán thực hiện. 15 3.2. Thuật toán cho lớp đồ thị Ý tưởng của thuật toán là trong trường hợp 2-liên thông thì xây dựng một chu trình tùy ý trong với thời gian đa thức, sau đó mở rộng cho đến khi đủ đỉnh bằng cách nối thêm một số cạnh cho cặp đỉnh không kề nhau có tổng bậc không nhỏ hơn , đồng thời kết hợp với việc gán nhãn cho các cạnh (được trình bày trong phần 1.4). Cuối cùng, ta sử dụng Thuật toán 1.3 (TransformCycle) để tìm chu trình Hamilton cho đồ thị ban đầu từ . a. Thuật toán 3.2. Xác định chu trình Hamilton cho đồ thị Input: Đồ thị 2-liên thông thỏa mãn . Output: Chu trình Hamilton của . Procedure Hamilton3; BEGIN // Gán nhãn bằng 1 cho tất cả các cạnh của 1: For each in do [ ] ; 2: ; 3: Tìm một chu trình tùy ý của đồ thị ; 4: While | | Do 5: Begin 6: Đánh số lại các đỉnh của ; 7: Tìm một thành phần liên thông của – ; 8: Tìm tập đỉnh ; // Mở rộng theo 3 trường hợp 9: If tồn tại Then 10: Begin 11: Tìm sao cho ; 12: Tìm một đường đi nối x với y trong ; 13: Thay thế thành chu trình mới ⃗⃗ ⃗ ; 14: End 15: Else If tồn tại Then 16: Begin 17: Tìm sao cho ; 18: Tìm một đường đi nối x với y trong ; 19: Thay thế thành chu trình mới ⃖⃗⃗⃗ ⃗⃗ ⃗ ; 20: End 21: Else 22: Begin 23: Tìm hai đỉnh bất kỳ thuộc ; // Bổ sung cạnh mới cho đồ thị và gãn nhãn 24: ; 25: ; 26: [ ] ; 27: Tìm sao cho ; 16 28: Tìm một đường đi nối x với y trong ; 29: Thay thế thành chu trình mới ⃖⃗⃗⃗ ⃗⃗ ⃗ ; 30: End; 31: End; // Biến đổi thành chu trình Hamilton của ban đầu 32: TransformCycle( ); END; Thuật toán 3.2 cần không quá phép toán thực hiện. 3.3. Sử dụng bao đóng cho các lớp đồ thị có tổng bậc lớn Theo Mệnh đề 1.2 thì là đồ thị Hamilton khi và chỉ khi là đồ thị Hamilton. Trong đồ thị bao đóng , bậc của mỗi đỉnh đều không nhỏ hơn bậc của đỉnh tương ứng trong đồ thị (Vì ), do đó các điều kiện về tổng bậc lớn trong đồ thị bao đóng sẽ có nhiều khả năng thỏa mãn hơn so với đồ thị ban đầu. Sau khi tìm được một chu trình Hamilton trong đồ thị , sử dụng Thuật toán 1.3 sẽ tìm được một chu trình Hamilton trong đồ thị ban đầu từ chu trình . Do đó, tác giả đưa ra đề xuất sau: Hình 3.1. Sơ đồ thuật toán xác định chu trình Hamilton sử dụng bao đóng đồ thị 17 Đề xuất 3.1. Sử dụng bao đóng đồ thị kết hợp với các thuật toán xác định chu trình Hamilton trong các lớp đồ thị có tổng bậc lớn để có thể thực hiện cho lớp đồ thị tổng quát hơn. Như vậy, thay vì việc không áp dụng được thuật toán cho đồ thị ban đầu, khi chuyển sang đồ thị bao đóng thì khả năng áp dụng được thuật toán sẽ cao hơn. Với Thuật toán 3.1 và 3.2 khi sử dụng bao đóng đồ thị như sơ đồ thuật toán trên cũng chỉ cần không quá phép toán thực hiện. Với các đồ thị có tổng bậc lớn thì số cạnh cũng lớn nên khi chạy chương trình cho Thuật toán tìm chu trình Hamiltton trên đồ thị bao đóng thì thời gian tăng không đáng kể. 3.4. Chƣơng trình thực nghiệm Phần này sẽ xây dựng chương trình thực nghiệm cho hai thuật toán 3.1 và 3.2 mà tác giả đã đề xuất để xác định chu trình Hamilton cho lớp đồ thị và . 3.4.1. Giới thiệu chƣơng trình Hình 3.2. Sơ đồ khối thực hiện chương trình Chương trình thực nghiệm sẽ được xây dựng theo sơ đồ khối đưa ra trong Hình 3.2 và phần thực hiện Tìm Chu trình Hamilton theo thuật toán tƣơng ứng sẽ được đo thời gian. Tác giả xây dựng hai chương trình thực nghiệm xác định chu trình Hamilton như sau: Bảng 3.1. Các chương trình thực nghiệm xác định chu trình Hamilton Chƣơng trình Lớp đồ thị Thuật toán áp dụng Thời gian Chương trình 1 . Thuật toán 3.1 Chương trình 2 . Thuật toán 3.2 18 Việc xác định giá trị hoặc cần thuật toán nên việc kiểm tra một đồ thị bất kỳ có thuộc lớp hoặc chỉ mất thời gian là , do đó Chương trình có thể nhận dữ liệu đầu vào là đồ thị tổng quát và thực hiện khả thi với các đồ thị lớn. Chương trình sử dụng ngôn ngữ lập trình C# và được tiến hành thực nghiệm trên máy tính sử dụng Hệ điều hành Windows7, bộ vi xử lý Core i3 2.53 GHz, RAM 8GB. 3.4.2. Bộ dữ liệu đầu vào Do không có đồ thị mẫu và cũng chưa có tác giả nào tiến hành thực nghiệm việc tìm chu trình Hamilton trên những lớp đồ thị và nên tác giả sẽ xây dựng hai bộ dữ liệu được sinh ngẫu nhiên gồm các đồ thị 2-liên thông thỏa mãn điều kiện đầu vào tương ứng của Thuật toán 3.1 hoặc Thuật toán 3.2 để thực nghiệm. Bộ dữ liệu 1 gồm các đồ thị thỏa mãn điều kiện , nhưng không thỏa mãn điều kiện . Bộ dữ liệu 2 gồm các đồ thị thỏa mãn điều kiện , nhưng không thỏa mãn điều kiện . Bảng 3.2. Danh sách các đồ thị được tiến hành thực nghiệm Số đỉnh ( ) Đồ thị Bộ dữ liệu 1 ( ) Bộ dữ liệu 2 ( ) 1000 S2sao-1000 S3-1000 2000 S2sao-2000 S3-2000 3000 S2sao-3000 S3-3000 4000 S2sao-4000 S3-4000 5000 S2sao-5000 S3-5000 6000 S2sao-6000 S3-6000 7000 S2sao-7000 S3-7000 8000 S2sao-8000 S3-8000 9000 S2sao-9000 S3-9000 10000 S2sao-10000 S3-10000 3.4.3. Đánh giá hiệu năng 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 Chƣơng trình 1 Chƣơng trình 2 Đồ thị Thời gian (s) Đồ thị Thời gian (s) S2sao-1000 2.467 S3-1000 2.283 S2sao-2000 19.664 S3-2000 17.945 S2sao-3000 64.895 S3-3000 61.586 19 S2sao-4000 154.620 S3-4000 141.135 S2sao-5000 300.194 S3-5000 264.959 S2sao-6000 525.644 S3-6000 476.623 S2sao-7000 836.379 S3-7000 754.716 S2sao-8000 1249.134 S3-8000 1122.091 S2sao-9000 1780.245 S3-9000 1618.704 S2sao-10000 2416.288 S3-10000 2200.797 Thuật toán 3.1 và Thuật toán 3.2 đều có điểm chung là sử dụng Thuật toán 1.1 để xây dựng một chu trình ban đầu, sau đó mở rộng cho đến khi có đủ đỉnh do đó độ dài của chu trình ban đầu sẽ có ảnh hưởng rất lớn đến thời gian chạy chương trình. Thuật toán 1.1 tìm một chu trình bất kỳ trong đồ thị làm chu trình khởi tạo ban đầu, tuy nhiên độ dài của là thường là nhỏ. Để tăng tốc độ thực hiện cho chương trình thì có thể sử dụng một số phương pháp Heuristic thay cho Thuật toán 1.1 để chu trình ban đầu có độ dài lớn, khi đó số vòng lặp mở rộng chu trình sẽ giảm đáng kể. Đề xuất 3.2. Tìm một đường đi dài nhất có thể, sau đó tìm cặp đỉnh thuộc sao cho và đoạn đường dài nhất có thể. Khi đó, ta có một chu trình độ dài lớn là ; Đề xuất trên có thể được thực hiện bởi Thuật toán sau. Thuật toán 3.3. Xác định một chu trình có độ dài lớn trong đồ thị 2-liên thông Input: Đồ thị 2-liên thông . Output: Một chu trình của có độ dài lớn. Procedure Create_Long_Cycle() Begin Tìm một cạnh ; ; Stop = False; While Not(Stop) Do Begin Stop = True; For each Do If và ( là một đỉnh cuối của ) Then Begin ; ; Stop = False; End; End; Found = False; Length = ; 20 While Not(Found) Do Begin If tồn tại sao cho | | = Length và Then Begin ; Found = True; End Else Length = Length – 1; End; End; Thay thế Thuật toán 1.1 bởi Thuật toán 3.3 để tìm chu trình khởi tạo ban đầu , tác giả đã cải tiến được đáng kể thời gian chạy hai chương trình. 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. Đồ thị Chƣơng trình 1 Chƣơng trình 1 cải tiến Độ dài ban đầu Thời gian (s) Độ dài ban đầu Thời gian (s) S2sao-1000 4 2.467 999 0.032 S2sao-2000 4 19.664 1997 0.098 S2sao-3000 4 64.895 2988 0.653 S2sao-4000 4 154.620 3980 1.738 S2sao-5000 4 300.194 4997 0.482 S2sao-6000 4 525.644 5990 1.996 S2sao-7000 4 836.379 6987 3.470 S2sao-8000 4 1249.134 7951 16.556 S2sao-9000 4 1780.245 8997 1.496 S2sao-10000 4 2416.288 9986 7.569 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. Đồ thị Chƣơng trình 2 Chƣơng trình 2 cải tiến Độ dài ban đầu Thời gian (s) Độ dài ban đầu Thời gian (s) S3-1000 3 2.283 994 0.065 S3-2000 3 17.945 1998 0.123 S3-3000 3 61.586 2992 0.436 S3-4000 3 141.135 3995 0.639 S3-5000 3 264.959 4997 0.799 S3-6000 3 476.623 5997 1.418 S3-7000 3 754.716 6995 1.753 S3-8000 4 1122.091 7998 2.192 S3-9000 3 1618.704 8998 2.569 S3-10000 3 2200.797 9998 3.373 21 Phân tích sự ảnh hưởng của độ dài chu trình khởi tạo ban đầu đối với thời gian chạy chương trình, tác giả chọn đồ thị S3-2000 để tiến hành thực nghiệm (bằng Chương trình 2). Kết quả thực nghiệm được đưa ra trong Bảng 3.6 và Hình 3.3 như sau: 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. Độ dài ban đầu Thời gian (s) 3 17.945 200 14.802 400 12.266 600 10.095 800 8.588 1000 6.737 1200 5.380 1400 4.391 1600 2.893 1800 1.587 1998 0.123 Hình 3.3. 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. 3.5. Kết luận Chƣơng 3 Chương này đã đề xuất hai thuật toán chính xác để xác định chu trình Hamilton trong lớp đồ thị và . Hai thuật toán này đã được đánh giá trên phương diện lý thuyết là không quá phép toán thực hiện và tác giả cũng đã tiến hành thực nghiệm trên các đồ thị lớn từ 1000 đỉnh đến 10000 đỉnh. Kết quả thực nghiệm đã cho thấy tính khả thi, hiệu quả và ý nghĩa thực tiễn của các thuật toán do tác giả đề xuất. 22 Tác giả đã tiến hành thực nghiệm theo hai chương trình khác nhau và đánh giá được yếu tố ảnh hưởng chính đến thời gian chạy chương trình là độ d