Thạc Sĩ 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

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 22
2.1. Giới thiệu bài toán và . 22
2.2. Độ phức tạp của bài toán và 22
2.3. Độ phức tạp của bài toán . 24
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 48
2.4. Bài toán 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 trên đồ thị Đồ 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 và [ ] Đồ thị con sinh của trên tập đỉnh con Toughness của đồ thị Khoảng cách của hai đỉnh trong đồ thị Phép kết nối đồ 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 ⃗⃗⃗ Đỉnh liền trước và đỉnh liền sau của theo chiều ⃗⃗⃗ . , với . vi
, với . ⃗⃗⃗ ⃖⃗⃗⃗ Đoạn đường trên từ tới theo chiều quay ⃗⃗⃗ . Đường đ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ị . 20
Hình 2.1. Đồ thị ̅ . 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 và lớn, trong
đó tập 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ố 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à (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à
.
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 . Tập đỉnh được gọi là tập đỉnh cắt nếu .
Đồ thị được gọi là -liên thông ( ) nếu | | và liên
thông với mọi tập mà | | . Số nguyên lớn nhất thỏa mãn là -liê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à , được định nghĩa như sau:
nếu cùng thuộc một thành phần liên thông thì là độ dài của đường đi
ngắn nhất nối hai đỉnh đó, ngược lại thì .
Với số nguyên dương , ta định nghĩa như sau: là tập đỉnh độc lập ,
Trường hợp thì đặt . Với và chỉ xét tới các
cặp đỉnh có khoảng cách 2, ta định nghĩa: ,
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 . Ta cũng
thường viết đơn giản là lần lượt thay cho và .
Đồ thị được gọi là -tough ( ) 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 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 và chỉ số các đỉnh đượ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 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 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ị 2-
liê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 đỉnh và là một chu trình dài nhất của , là một thành phần liên thông 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 hoặc .
(c) Nếu với thì không có ⃗⃗⃗ sao cho đồng thời có . Tương tự, không 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ị 2-liên thông với đỉnh và là một chu trình của với
không quá đỉnh, là một thành phần liên thông của . Nếu
và là tập đỉnh độc lập thì với mọi và với mọi
ta có: .
Chứng minh. Có | | | | | | | | . Theo giả thiết
suy ra | | | | | | | | | | | | , 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.