LOGO
Ths. Phạm Thanh An
Bộ môn Khoa học máy tính - Khoa CNTT
Trường Đại học Ngân hàng TP.HCM
Chương 5: ĐỒ THỊ
Mục tiêu của chương

Trình bày những kiến thức căn bản về lý
thuyết đồ thị, cách biểu diễn, một số
thuật toán trên đồ thị

Đánh giá thuật toán

Một số ứng dụng của đồ thị
Định nghĩa
Boston
Hartford
Atlanta
Minneapolis
Austin
SF
Seattle
Anchorage
Định nghĩa

Đồ thị G = (V,E)

V = tập hợp hữu hạn các phần tử (đỉnh hay
nút)

E ⊆ V × V, tập hữu hạn các cạnh (cung)

Độ dài đường: length(u
1
,u
2
,…,u
n
)=n

(u
1
,u
2
,…,u
n
) đường đi đơn, nếu u
i
≠u
j
,
1<∀i≠j<n (là đường đi, mà các đỉnh phân
biệt, ngoại trừ đình đầu và đỉnh cuối)
Các khái niệm (tt)

Chu trình (cycle) = (u
1
,u
2
,…,u
n
), u

Tính liên thông (connectivity)

Trong đồ thị G, hai đỉnh x,y gọi là liên thông
(connected), nếu có một đường từ x đến y

Đồ thị G liên thông, nếu ∀(x,y) ∈ E, ∃ đường
đi từ x đến y

Đồ thị G gọi là có trọng số, nếu mỗi cung
được gán một giá trị số đặc trưng
Các khái niệm (tt)
Đồ thị liên thông Đồ thị không liên thông
Các khái niệm (tt)

Đồ thị có trọng số
0
1
3
2
20
10
1
5
4
Biểu diễn đồ thị

Biểu diễn bằng ma trận kề

Adjacency matrice


Biểu diễn bằng ma trận kề(tt)
0
1
3
2
A[i][j] 0 1 2 3
0 0 1 1 0
1 1 0 1 1
2 1 1 0 1
3 0 1 1 0
A =
0 1 1 0
1 0 1 1
1 1 0 1
0 1 1 0
Biểu diễn bằng ma trận kề(tt)
A[i][j] 0 1 2 3
0 0 1 1 1
1 0 0 0 1
2 0 0 0 1
3 0 0 0 0
0
1
3
2
A =
0 1 1 1
0 0 0 1
0 0 0 1
0 0 0 0

11000
00110
Biểu diễn bằng ma trận kề (tt)
A[i][j] 0 1 2 3
0 0 20 10 1
1 20 0 0 5
2 10 0 0 4
3 1 5 4 0
0
1
3
2
10
20
1
4
5
A =
0 20 10 1
20 0 0 5
10 0 0 4
1 5 4 0
Biểu diễn bằng ma trận kề (tt)

Chú ý

Đối với đồ thị không định hướng, ma trận kề
là ma trận đối xứng

Đối với đồ thị định hướng, số lượng phần tử

3
1 2 3
3
3
Biểu diễn đồ thị
bằng danh sách kề (tt)
x
1
x
2
x
3
x
4
x
5
x[1]
2 3
x[2]
5
x[3]
2
x[4]
3
x[5]
1 4
Biểu diễn đồ thị
bằng danh sách kề (tt)
0
1

Thứ tự các nút không quan trọng
Phép duyệt đồ thị

Từ một đỉnh, liệt kê tất cả các đỉnh của đồ
thị

Phép tìm kiếm theo chiều sâu
•
Depth first search

Phép tìm kiếm theo chiều rộng
•
Breadth first search