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
.PDF 
108 
935 
75 
