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 với lớp
vẫn còn là bài toán với mọi . Có thể nói rằng kết
đồ thị thỏa mãn 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à chưa có thuật toán xác lớn, tuy nhiên các lớp đồ thị được xác định theo điều kiện và đị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.
lớn, trong đó tập
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 và
trung vào trường hợp .
Đá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ố 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à (với
nguyên dương, số thực là tham số) như sau:
. Instance: Đồ thị thỏa mãn
.
Question: có là đồ thị Hamilton?
Instance: Đồ thị thỏa mãn
Question: 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à
4
, sau đó tác giả tiến hành thực nghiệm trên các đồ thị lớn (hàng 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 đồ và
thị 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 [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ở.
CHƢƠNG 1. TỔNG QUAN VỀ CHU TRÌNH TRONG ĐỒ THỊ
1.1. Một số khái niệm và quy ƣớc
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ố.
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 .
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à .
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 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.
. Với số nguyên dương , ký hiệu
Giả sử chu trình . Ta quy định một chiều quay ⃗⃗⃗ theo lần thứ tự chỉ số các đỉnh (chỉ số được lấy theo ). Với đỉnh , ký hiệu 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à
5
. 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.
lớn.
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à
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
với mọi : 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ị
là bài toán với mọi . Định lý 1.1 [15, Định lý 16].
lớn.
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à
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ó:
. Khi đó, là đồ
Định lý 1.7 [18]. Cho G là đồ thị 1-tough với đỉnh và thị Hamilton.
Với đồ thị -liên thông, Bondy đưa ra kết quả tổng quát cho như sau:
thì là đồ thị
Định lý 1.8 [11]. Nếu là đồ thị -liên thông thỏa mãn Hamilton.
. Khi đó xảy ra một trong hai trường hợp sau:
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
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
Bảng 1.1. Một số thuật toán Backtrack và Heuristic xác định chu trình Hamilton
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]:
Thuật toán
Tác giả
Pósa UHC HAM SparseHam HideHam DB2 LongPath LinearHam
Loại Heuristic Heuristic Heuristic Heuristic Heuristic Heuristic Heuristic Heuristic
Snakes and Ladders
Heuristic
MultiPath MultiPath cải tiến KTC
Pósa Angluin and Valiant Bollobas, Fenner and Frieze Frieze Broder, Frieze and Shamir Brunacci Kocay and Li Thomason P. Baniasadi, V. Ejov, J.A. Filar, M. Haythorpe, S. Rossomakhine Kocay Andrew Chalaturnyk Shufelt and Berliner
Backtrack Backtrack 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].
Hình 1.5. Quá trình tạo bao đóng đồ thị.
8
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:
Question: có là đồ thị Hamilton?
. Instance: Đồ thị thỏa mãn
.
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ó:
là đồ thị Hamilton. Hệ quả 2.3. Mọi đồ thị 2-liên thông thỏa mã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 Điều kiện thỏa mãn nhưng không Hamilton, chẳng hạn các đồ thị ̅ với .
11
là bài toán thuộc lớp . Hệ quả 2.4.
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:
Hình 2.1. Đồ thị Dạng 1, Định lý 2.3.
1. Dạng 1: Tồn tại | | sao cho . (Hình 2.1)
Hình 2.2. Đồ thị Dạng 2, Đị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)
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)
Hình 2.3. Đồ thị Dạng 3, Định lý 2.3.
12
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;
là bài toán thuộc lớp .
Hệ quả 2.7. 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:
thì là đồ thị Hamilton. 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à
CHƢƠNG 3. THUẬT TOÁN ĐA THỨC XÁC ĐỊNH CHU TRÌNH
VÀ
HAMILTON TRONG ĐỒ THỊ
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
và
. Thêm vào đó, tác giả đề xuất việc sử dụng bao
hai lớp đồ thị đó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ị
và là đồ thị Hamilton. là một chu trình Bổ đề 3.1. Cho là đồ thị thỏa mãn 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:
. với .
,
1. Tồn tại sao cho 2. Tồn tạ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
1:
) Then
// Kiểm tra không là đồ thị Hamilton If ( ̅
̅
̅
Begin
Thông báo không có chu trình Hamilton; Kết thúc;
2: 3: 4: 5: 6: 7: 8:
End; // Trường hợp là đồ thị Hamilton Tìm một chu trình tùy ý của đồ thị ; // Vòng lặp mở rộng tập đỉnh của While | | Do Begin
Then
Tìm một thành phần liên thông của – ; Đánh số các đỉnh của lần lượt là ; // Mở rộng chu trình theo 4 trường hợp If tồn tại Begin
;
9: 10: 11: 12: 13: 14:
Tìm sao cho Tìm một đường đi nối x với y trong ; ⃗⃗⃗ ; Thay thế thành chu trình mới
Then
15: 16: 17: 18: 19: 20:
⃗⃗⃗ ;
Tìm sao cho ; Tìm một đường đi nối x với y trong ; Thay thế thành chu trình mới ⃖⃗⃗⃗
End Else If tồn tại Then Begin
21: 22: 23: 24: 25: 26:
⃗⃗⃗ ;
Chọn tùy ý và tìm sao cho ; Tìm một đường đi nối x với y trong ; Thay thế thành chu trình mới ⃖⃗⃗⃗
End Else Begin
và tìm sao cho ;
27: 28: 29: 30: 31: 32:
⃗⃗⃗ ;
Tìm Tìm một đường đi nối x với y trong ; Thay thế thành chu trình
⃗⃗⃗
End;
End;
33: 34: 35:
End Else If tồn tại Begin
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 .
1:
// Gán nhãn bằng 1 cho tất cả các cạnh của For each in do [ ] ; ; Tìm một chu trình tùy ý của đồ thị ; While | | Do Begin
2: 3: 4: 5: 6:
Đánh số lại các đỉnh của ; Tìm một thành phần liên thông của – ; Tìm tập đỉnh ; // Mở rộng theo 3 trường hợp If tồn tại Then Begin
7: 8: 9: 10: 11: 12:
Tìm sao cho ; Tìm một đường đi nối x với y trong ; Thay thế thành chu trình mới ⃗⃗⃗ ;
End Else If tồn tại Then Begin
13: 14: 15: 16: 17: 18:
Tìm sao cho ; Tìm một đường đi nối x với y trong ; Thay thế thành chu trình mới ⃖⃗⃗⃗ ⃗⃗⃗ ;
End Else Begin
19: 20: 21: 22: 23: 24: 25: 26: 27:
Tìm hai đỉnh bất kỳ thuộc ; // Bổ sung cạnh mới cho đồ thị và gãn nhãn ; ; [ ] ; Tìm sao cho ;
Procedure Hamilton3; BEGIN
16
Tìm một đường đi nối x với y trong ; Thay thế thành chu trình mới ⃖⃗⃗⃗ ⃗⃗⃗ ;
End;
End; // Biến đổi thành chu trình Hamilton của ban đầu TransformCycle( );
28:
29: 30: 31: 32:
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
Hình 3.1. Sơ đồ thuật toán xác định chu trình Hamilton sử dụng bao đóng đồ thị
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 lớn trong đồ thị bao trong đồ thị (Vì ), do đó các điều kiện về tổng bậc đó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:
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
và
. giả đã đề xuất để xác định chu trình Hamilton cho lớp đồ thị
Hình 3.2. Sơ đồ khối thực hiện chương trình
3.4.1. Giới thiệu chƣơng trình
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 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:
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
cần thuật toán nên việc kiểm tra một đồ thị bất chỉ mất thời gian là , do đó Chương trình
18
Việc xác định giá trị hoặc hoặc
kỳ có thuộc lớp 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
và
nên tác giả sẽ xây dựng
chu trình Hamilton trên những lớp đồ thị 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.
, nhưng không thỏa mãn , nhưng
Bộ dữ liệu 1 gồm các đồ thị 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
Bảng 3.2. Danh sách các đồ thị được tiến hành thực nghiệm
điều kiện không thỏa mãn điều kiện
Đồ thị
Số đỉnh ( )
)
Bộ dữ liệu 2 (
Bộ dữ liệu 1 ) (
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
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
3.4.3. Đánh giá hiệu năng
Chƣơng trình 1
Chƣơng trình 2
Đồ thị
Thời gian (s)
Đồ thị
Thời gian (s)
S2sao-1000 S2sao-2000 S2sao-3000
2.467 S3-1000 19.664 S3-2000 64.895 S3-3000
2.283 17.945 61.586
S2sao-4000 S2sao-5000 S2sao-6000 S2sao-7000 S2sao-8000 S2sao-9000 S2sao-10000
154.620 S3-4000 300.194 S3-5000 525.644 S3-6000 836.379 S3-7000 1249.134 S3-8000 1780.245 S3-9000 2416.288 S3-10000
141.135 264.959 476.623 754.716 1122.091 1618.704 2200.797
19
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 = ;
While Not(Found) Do
Begin
If tồn tại sao cho | | = Length và Then Begin
; Found = True;
End
Else Length = Length – 1;
End;
20
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ả
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.
đã cải tiến được đáng kể thời gian chạy hai chương trình.
Chƣơng trình 1
Chƣơng trình 1 cải tiến
Đồ thị
Thời gian (s)
Thời gian (s)
Độ dài ban đầu
Độ dài ban đầu
S2sao-1000 S2sao-2000 S2sao-3000 S2sao-4000 S2sao-5000 S2sao-6000 S2sao-7000 S2sao-8000 S2sao-9000 S2sao-10000
4 4 4 4 4 4 4 4 4 4
2.467 19.664 64.895 154.620 300.194 525.644 836.379 1249.134 1780.245 2416.288
999 1997 2988 3980 4997 5990 6987 7951 8997 9986
0.032 0.098 0.653 1.738 0.482 1.996 3.470 16.556 1.496 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.
Chƣơng trình 2
Chƣơng trình 2 cải tiến
Đồ thị
Thời gian (s)
S3-1000 S3-2000 S3-3000 S3-4000 S3-5000 S3-6000 S3-7000 S3-8000 S3-9000 S3-10000
Độ dài ban đầu 3 3 3 3 3 3 3 4 3 3
Thời gian (s) 2.283 17.945 61.586 141.135 264.959 476.623 754.716 1122.091 1618.704 2200.797
Độ dài ban đầu 994 1998 2992 3995 4997 5997 6995 7998 8998 9998
0.065 0.123 0.436 0.639 0.799 1.418 1.753 2.192 2.569 3.373
21
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.
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:
Độ 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
và
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ị . 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ài của chu trình khởi tạo ban đầu bằng lý thuyết và thực nghiệm. Việc cải tiến chương trình bằng Thuật toán 3.3 đã giảm được đáng kể thời gian chạy chương trình.
Tác giả cũng đã đưa ra một đề xuất quan trọng khác cho việc mở rộng lớp đồ thị có thể áp dụng các thuật toán tìm chu trình Hamilton trên các đồ thị có tổng bậc lớn bằng việc xây dựng bao đóng đồ thị. Việc sử dụng bao đóng tuy có làm tăng thời gian chạy chương trình nhưng ưu điểm là thực hiện được trên lớp đồ thị tổng quát hơn, và đặc biệt là trên các đồ thị có tổng bậc lớn thì thời gian chạy chương trình tăng không đáng kể.
CHƢƠNG 4. ĐÁNH GIÁ ĐỘ DÀI CHU TRÌNH DÀI NHẤT TRONG ĐỒ THỊ 1-TOUGH VỚI
4.1. Giới thiệu Giả thuyết Bauer
Giả thuyết 1.3 của Bauer, Fan, Veldman đánh giá độ dài chu trình dài nhất rằng [8]:
Nếu đồ thị là đồ thị 1-tough và thì .
Giả thuyết này cũng đã được một số tác giả 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, chẳng hạn như chứng minh của tác giả Tri Lai [43] bị sai tại Proposition 26. 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ở. Chương này tác giả sẽ đưa ra chứng minh của mình cho Giả thuyết 1.3 này.
Trong toàn bộ chứng minh của Chương, các Quy ước 4.1, 4.2, 4.3, 4.4, 4.5 đều được
sử dụng ngay sau khi phát biểu cho đến hết Chương.
Quy ƣớc 4.1. Giả sử rằng đồ thị là 1-tough thỏa mãn và không Hamilton.
Theo Quy ước 4.1 ta cần chứng minh rằng .
4.2. Các Tính chất và Bổ đề
Tính chất 4.1. Mọi chu trình dài nhất của đều là chu trình Dominating.
Với một chu trình dài nhất của (cũng là chu trình Dominating) ta định nghĩa:
| và | .
Quy ƣớc 4.2. Lấy ⃗⃗⃗ là một chu trình dài nhất của với một chiều quay định hướng thỏa mãn và một đỉnh sao cho . Đặt .
. Tính chất 4.2 (Tham khảo chứng minh của Định lý 9 trong [9]).
Tính chất 4.3 [41, Bổ đề 9]. | | . Tính chất 4.4. | | .
23
Bổ đề 4.1 [42]. Cho ⃗⃗⃗ là một chu trình có độ dài của đồ thị . Giả sử rằng không có chu trình độ dài và không có chu trình độ dài với , và là một đỉnh cô lập của . Đặt , và với thì:
, .
. Khi đó: Đặt ⋃ và ⋃
.
(a) .
(b) Nếu thì
(c) .
Quy ƣớc 4.3. Giả sử rằng hai tập đỉnh được xây dựng như trong Bổ đề 4.1 với đỉnh (nói trong Bổ đề 4.1) chính là đỉnh được xác định từ Quy ước 4.2.
Tính chất 4.5.
(a) Không có cạnh nối một đỉnh của với một đỉnh của .
(b) , do đó | |.
(c) là tập đỉnh độc lập.
và
. Với , đặt
(d) và .
Quy ƣớc 4.4. Nhận thấy rằng mọi đỉnh nên . Ta lấy cố định một đỉnh và kí hiệu đỉnh của là | | , xuất hiện lần lượt trên ⃗⃗⃗ sao cho . Theo Bổ đề và do đó sẽ là hợp của các đường rời nhau ⃗⃗⃗ , ta gọi là các 4.1 (b), arc. Một arc với đỉnh được gọi là một -arc. Khi đó ⃗⃗⃗ là 1-arc khi và chỉ khi (chính là một đỉnh thuộc ). Hai arc được gọi là kề nhau nếu tồn tại một cạnh nối giữa một đỉnh thuộc arc này với một đỉnh thuộc arc còn lại.
Tính chất 4.6.
(a) là tập đỉnh độc lập.
(b) | | .
Tính chất 4.7. có ít nhất hai arc với độ dài không nhỏ hơn 2.
Quy ƣớc 4.5. | | và .
Tính chất 4.8 [41, Bổ đề 4]. và là các tập đỉnh độc lập.
Định nghĩa 4.1. Cặp đỉnh được gọi là bad-pair nếu và | | | |.
Định nghĩa 4.2. Đường đi trong được gọi là bad-path nếu là một trong hai dạng sau:
1. gồm tất cả các đỉnh của ⃗⃗⃗ , các đỉnh cuối của là và
với và .
2. gồm tất cả các đỉnh của ⃖⃗⃗⃗ , các đỉnh cuối của là và
với và .
24
Tính chất 4.9. Không có cặp đỉnh nào trong là bad-pair.
Bổ đề 4.2. Không có đường đi nào trong là bad-path.
Bổ đề 4.3. Nếu với thì hoặc .
Bổ đề 4.4. Nếu với thì .
⃗⃗⃗
Bổ đề 4.5. Giả sử rằng với . Khi đó với mọi . Tương tự, với mọi .
. Nếu Bổ đề 4.6. Giả sử rằng với và đỉnh và thì . Tương tự, nếu và thì . Bổ đề 4.7. Giả sử rằng với . Nếu tồn tại một đỉnh ⃗⃗⃗ sao cho thì . Bổ đề 4.8. Giả sử rằng có một -arc ⃗⃗⃗ và một -arc ⃗⃗⃗ với và . Khi đó, { } .
} thì .
hoặc {
} thì .
Bổ đề 4.9. Giả sử rằng có một -arc ⃗⃗⃗ và một -arc ⃗⃗⃗ với , sao cho và không có -arc nào thuộc ⃗⃗⃗ . Nếu
Bổ đề 4.10. Giả sử rằng có một -arc ⃗⃗⃗ và một -arc ⃗⃗⃗ với , sao cho không có -arc nào thuộc ⃗⃗⃗ ⃗⃗⃗ . Nếu hoặc {
Vì | | và theo Tính chất 4.6 (b), ta có hoặc | | , hoặc
| | . Ta xét hai trường hợp:
Trƣờng hợp 1. | | . Trong trường hợp này, theo Tính chất 4.7 thì
bao gồm hai 2-arc và còn lại là các 1-arc.
Trƣờng hợp 2. | | . Trong trường hợp này, theo Tính chất 4.7 thì xảy ra
hai khả năng sau:
Trƣờng hợp 2.1. bao gồm một 2-arc, một 3-arc và các 1-arc.
Trƣờng hợp 2.2. bao gồm ba 2-arc và còn lại là các 1-arc.
4.3. Chứng minh cho các trƣờng hợp
Trong phần này sẽ chứng minh rằng tất cả các trường hợp trên đều không xảy ra bằng
phương pháp phản chứng. Chứng minh gồm có 4 Mệnh đề và 21 Khẳng định.
25
4.4. Kết luận Chƣơng 4
Chương này đã đánh giá độ dài của chu trình dài nhất theo một Giả thuyết của các tác thì thị là 1-tough và
giả Bauer, Fan, Veldman rằng: Nếu đồ . Có thể tóm tắt các bước trong chứng minh như sau:
Giả thiết là đồ thị 1-tough thỏa mãn và không Hamilton.
Từ Bổ đề Hopping xây dựng tập hai .
Chứng minh | | và | | .
Nếu | | thì suy ra .
Nếu | | , chứng minh: | | và | | .
Kết luận: .
KẾT LUẬN
Luận án đã đưa ra các kết quả mới trong việc nghiên cứu bài toán chu trình Hamilton và đặc biệt đã hoàn thành chứng minh một Giả thuyết của các nhà toán học lớn Bauer, Fan, Veldman cho việc đánh giá độ dài của chu trình dài nhất trong đồ thị.
Vấn đề chu trình Hamilton được nghiên cứu trong luận án theo hai bài toán và
, các kết quả đạt được trong luận án 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à (trường hợp ) là các bài toán
thuộc lớp .
.
và
Xây dựng các thuật toán đa thức để xác định chu trình Hamilton trong đồ thị
Thực nghiệm cho các thuật toán xác định chu trình Hamilton đã đề xuất trên các đồ thị lớn (từ 1000 đến 10000 đỉnh). Kết quả thực nghiệm đã cho thấy tính hiệu quả và khả thi của các thuật toán.
Hoàn thành việc chứng minh cho một Giả thuyết của Bauer, Fan, Veldman rằng:
Nếu là đồ thị 1-tough và thì .
Với việc đánh giá được độ phức tạp của bài toán thuộc lớp thì tác giả
đã khẳng định được cho Giả thuyết 2.1 với .
, ,
,…
Một số vấn đề nghiên cứu tiếp: Tiếp tục giải quyết Giả thuyết 2.1 và Giả thuyết 2.2 cho trường hợp . Chu trình Hamilton trong đồ thị: Thiết kế thuật toán thời gian đa thức xác định chu trình Hamilton cho lớp đồ thị 2-
liên thông thỏa mãn .
Thiết kế thuật toán thời gian đa thức tìm một chu trình có độ dài không nhỏ hơn
trong đồ thị 1-tough không Hamilton thỏa mãn .
26
Những công trình đã công bố liên quan đến luận án
,
[1] Vũ Đình Hòa, Nguyễn Hữu Xuân Trường, Chu trình Hamilton trong đồ thị
Tạp chí Tin học và Điều khiển học, T.28, S.2, 153-160, 2012.
[2] Vũ Đình Hòa, Nguyễn Hữu Xuân Trường, Thuật toán đa thức xác định chu trình Hamilton trong lớp đồ thị , Tạp chí Khoa học và Công nghệ - Viện Hàn Lâm Khoa Học và Công Nghệ Việt Nam, T.51, S.5, 533-541, 2013.
[3] Vũ Đình Hòa, Nguyễn Hữu Xuân Trường, Chu trình Hamilton trong đồ thị
, Kỷ yếu Hội nghị Khoa học Công nghệ quốc gia lần thứ VI (FAIR), 91-96, 2013.
2014.
[4] Vũ Đình Hòa, Nguyễn Hữu Xuân Trường, Chu trình Hamilton trong đồ thị , Kỷ yếu Hội nghị Khoa học Công nghệ quốc gia lần thứ VII (FAIR), 60-67,
[5] Nguyen Huu Xuan Truong, Vu Dinh Hoa, Hamiltonian cycle in graphs , International Journal of Computer Science and Business Informatics, Vol.15, No.2, 38-60, 2015.
[6] Nguyen Huu Xuan Truong, Vu Dinh Hoa, A new lower bound for the circumference of tough graphs, International Journal of Advanced Research in Computer Science and Software Engineering, Volume 5, Issue 9, 643-649, 2015.
