MỤC LỤC
1
|
Đồ thị
|
2
|
1.1
|
Giới thiệu
|
2
|
1.1.1
|
Định nghĩa về đồ thị
|
2
|
1.1.2
|
Biểu diễn đồ thị:
|
3
|
1.1.3
|
Tìm kiếm trên đồ thị
|
4
|
1.1.4
|
Ьờng đi trong đồ thị
|
5
|
1.1.5
|
Đồ thị liên thông, đồ thị con và thành phần liên
thông.
|
5
|
1.1.6
|
Cầu và đỉnh nối.
|
5
|
1.1.7
|
Bậc của đồ thị
|
5
|
1.1.8
|
Đồ thị hai phía
|
8
|
1.1.9
|
Đồ thị t¬ơng đ¬ơng
|
8
|
1.1.10
|
Sắp xếp Topo
|
10
|
1.2
|
Bài tập
|
11
|
1.2.1
|
Đề bài
|
11
|
1.2.2
|
Bài giải
|
11
|
1.3
|
Cây
|
14
|
1.3.1
|
Định nghĩa về cây.
|
14
|
1.3.2
|
Một số định nghĩa khác
|
14
|
1.3.3
|
Biểu diễn cây
|
15
|
1.3.4
|
Những bài toán liên quan đến cây:
|
17
|
1.4
|
Cây khung nhỏ nhất
|
23
|
1.4.1
|
Phát biều bài
toán
|
23
|
1.4.2
|
Thuật toán
tìm cây khung nhỏ nhất
|
23
|
1.4.3
|
Bài tập
|
27
|
1.5
|
Ьờng đi và chu trình
|
28
|
1.5.1
|
Ьờng đi và chu trình
Euler
|
28
|
1.5.2
|
Chu trình và đ¬ờng đi Hamilton
|
33
|
1.6
|
Bài toán đ¬ờng đi ngắn nhất
|
35
|
1.6.1
|
Ьờng đi ngắn nhất từ một đỉnh
|
35
|
1.6.2
|
Bài toán đ¬ờng đi ngắn nhất giữa các cặp đỉnh
|
43
|
1.6.3
|
Bài tập và lời giải
|
47
|
