PDF Giáo trình lý thuyết đồ thị, Đặng Trường Sơn, Lê Văn Vinh

Giáo trình lý thuyết đồ thị, Đặng Trường Sơn, Lê Văn Vinh

 

........................................................................................... 3
MỤC LỤC ................................................................................................. 5
Chƣơng I: CÁC KHÁI NIỆM CƠ BẢN ................................................ 9
1.1. MỞ ĐẦU ............................................................................................ 9
1.2. ĐỊNH NGHĨA VÀ PHÂN LOẠI ĐỒ THỊ ....................................... 10
1.2.1. Định nghĩa đồ thị .................................................................... 10
1.2.2. Phân loại đồ thị ....................................................................... 10
1.3. CÁC THUẬT NGỮ CƠ BẢN .......................................................... 14
1.4. ĐƢỜNG ĐI, CHU TRÌNH, ĐỒ THỊ LIÊN THÔNG ...................... 16
1.4.1. Đƣờng đi ................................................................................. 16
1.4.2. Chu trình ................................................................................. 17
1.4.3. Đƣờng đi và chu trình trong đồ thị có hƣớng ......................... 17
1.4.4. Đồ thị liên thông ..................................................................... 18
1.5. MỘT SỐ DẠNG ĐỒ THỊ ĐẶC BIỆT ............................................. 20
1.5.1. Đồ thị đầy đủ .......................................................................... 20
1.5.2. Đồ thị vòng, đồ thị bánh xe .................................................... 20
1.5.3. Đồ thị siêu khối ...................................................................... 21
1.5.4. Đồ thị hai phía ........................................................................ 22
1.5.5. Đồ thị phẳng ........................................................................... 25
1.6. BÀI TẬP CHƢƠNG I .................................................................. 27
Chƣơng II: BIỂU DIỄN ĐỒ THỊ TRÊN MÁY TÍNH ....................... 29
2.1. MA TRẬN KỀ, MA TRẬN TRỌNG SỐ ....................................... 29
2.1.1. Ma trận kề ............................................................................... 29
2.1.2. Ma trận trọng số ..................................................................... 31
2.1.3. Cài đặt ..................................................................................... 31
2.2. DANH SÁCH CẠNH (CUNG) ........................................................ 33
6
2.3. DANH SÁCH KỀ ............................................................................. 34
2.4. MA TRẬN LIÊN THUỘC ............................................................... 38
2.5. SỰ ĐẲNG CẤU CỦA ĐỒ THỊ ....................................................... 38
2.5.1. Định nghĩa ............................................................................. 38
2.5.2. Tính bất biến ........................................................................... 39
2.6. BÀI TẬP CHƢƠNG II ..................................................................... 39
Chƣơng III: DUYỆT ĐỒ THỊ .............................................................. 43
3.1. DUYỆT ĐỒ THỊ THEO CHIỀU SÂU ............................................ 43
3.1.1. Phƣơng pháp duyệt ................................................................. 43
3.1.2. Cài đặt thuật toán .................................................................... 44
3.2. DUYỆT ĐỒ THỊ THEO CHIỀU RỘNG ......................................... 46
3.2.1. Phƣơng pháp duyệt ................................................................. 46
3.2.2. Cài đặt thuật toán .................................................................... 46
3.3. TÌM ĐƢỜNG ĐI VÀ KIỂM TRA TÍNH LIÊN THÔNG ............... 50
3.3.1. Bài toán tìm đƣờng đi ............................................................ 50
3.3.2. Bài toán kiểm tra tính liên thông ............................................ 52
3.4. BÀI TẬP CHƢƠNG III .................................................................... 54
Chƣơng IV: ĐỒ THỊ EULER VÀ ĐỒ THỊ HAMILTON ................. 57
4.1. ĐỒ THỊ EULER ............................................................................... 57
4.1.1. Định nghĩa .............................................................................. 57
4.1.2. Định lý Euler .......................................................................... 57
4.1.3. Giải thuật xây dựng chu trình Euler ....................................... 59
4.2. ĐỒ THỊ HAMILTON ....................................................................... 62
4.2.1. Định nghĩa .............................................................................. 62
4.2.2. Định lý Dirac .......................................................................... 63
4.2.3. Giải thuật xây dựng chu trình Hamilton ................................. 63
4.3. BÀI TẬP CHƢƠNG IV ................................................................... 65
7
Chƣơng V: CÂY..................................................................................... 67
5.1. ĐỊNH NGHĨA VÀ CÁC TÍNH CHẤT CƠ BẢN CỦA CÂY ......... 67
5.2. CÂY KHUNG CỦA ĐỒ THỊ ........................................................... 69
5.2.1. Định nghĩa .............................................................................. 69
5.2.2. Thuật toán xây dựng cây khung ............................................. 70
5.3. BÀI TOÁN CÂY KHUNG NHỎ NHẤT ......................................... 73
5.3.1. Thuật toán Kruskal ................................................................. 74
5.3.2. Thuật toán Prim ...................................................................... 77
5.4. CÂY CÓ GỐC .................................................................................. 79
5.4.1. Các định nghĩa ........................................................................ 79
5.4.2. Cây nhị phân tìm kiếm ........................................................... 81
5.4.3. Cây quyết định ........................................................................ 83
5.4.4. Các phƣơng pháp duyệt cây ................................................... 83
5.5. BÀI TẬP CHƢƠNG V ..................................................................... 86
Chƣơng VI: TÔ MÀU ĐỒ THỊ ............................................................ 89
6.1. MỞ ĐẦU .......................................................................................... 89
6.1.1. Định nghĩa 1 ........................................................................... 89
6.1.2. Định nghĩa 2 ........................................................................... 90
6.2. ĐỊNH LÝ BỐN MÀU ...................................................................... 90
6.3. ĐỒ THỊ 2 MÀU ................................................................................ 90
6.4. THUẬT TOÁN SEQUENTIALCOLOR ......................................... 91
6.5. NHỮNG ỨNG DỤNG CỦA BÀI TOÁN TÔ MÀU ĐỒ THỊ ......... 93
6.5.1. Bài toán lập lịch thi ................................................................ 94
6.5.2. Bài toán phân chia tần số ........................................................ 95
6.6. BÀI TẬP CHƢƠNG VI ................................................................... 95
Chƣơng VII: ĐƢỜNG ĐI NGẮN NHẤT ............................................ 97
7.1. ĐỊNH NGHĨA .................................................................................. 97
7.2. THUẬT TOÁN DIJKSTRA ............................................................. 97
8
7.2.1. Ý tƣởng thuật toán .................................................................. 97
7.2.2. Cài đặt thuật toán .................................................................... 98
7.3. THUẬT TOÁN FORD-BELLMAN .............................................. 100
7.3.1. Ý tƣởng thuật toán ................................................................ 101
7.3.2. Cài đặt thuật toán .................................................................. 101
7.4. THUẬT TOÁN FLOYD ................................................................ 103
7.4.1. Ý tƣởng thuật toán ................................................................ 103
7.4.2. Cài đặt thuật toán .................................................................. 103
7.5. BÀI TẬP CHƢƠNG VII ................................................................ 106
Chƣơng VIII: LUỒNG TRONG MẠNG........................................... 110
8.1. MỘT SỐ KHÁI NIỆM CƠ BẢN .................................................. 110
8.1.1. Mạng ..................................................................................... 110
8.1.2. Luồng trong mạng ................................................................ 111
8.2. ĐỊNH LÝ FORD-FULKERSON ................................................... 113
8.3. THUẬT TOÁN TÌM LUỒNG CỰC ĐẠI TRONG MẠNG .......... 117
8.4. BÀI TẬP CHƢƠNG VIII ............................................................... 122
PHỤ LỤC .............................................................................................. 123
HƢỚNG DẪN VÀ ĐÁP ÁN MỘT SỐ BÀI TẬP ................................ 139
TÀI LIỆU THAM KHẢO ..................................................................... 147