1
CHƯƠNG 6
ĐỒ THỊ

2
Chương 6: Đồ thị
6.1 Định nghĩa và các khái niệm
6.2 Biểu diễn đồ thị
6.3 Phép duyệt đồ thị
6.4 Tìm đường đi ngắn nhất

3
Đồ thị là một cấu trúc rời rạc gồm các đỉnh và
các cạnh (vô hướng hoặc có hướng) nối các
đỉnh đó .
Nhiều bài toán thuộc những lĩnh vực rất khác
nhau có thể giải được bằng mô hình đồ thị:
biểu diễn sự cạnh tranh các loài trong một môi
trường sinh thái, hai máy tính có được nối với
nhau bằng một đường truyền thông hay
không. tìm đường đi ngắn nhất giữa hai thành
phố, lập lịch thi, phân chia kênh cho các đài
truyền hình …
6.1-Định nghĩa và khái niệm

4
Khi mô hình hoá bằng đồ thị: đỉnh biểu thị các đối
tượng được xem xét (người, tổ chức, địa danh, ),
cạnh đồ thị là những đoạn thẳng (hoặc cong) hay
những mũi tên nối một số điểm với nhau, tượng

v
2
6.1-Định nghĩa và khái niệm

7
Các thuật ngữ về đồ thị :
Hai đỉnh u và v trong đồ thị (vô hướng) G=(V,E) được gọi
là liền kề nếu (u,v)∈E. Nếu e = (u,v) thì e gọi là cạnh
liên thuộc với các đỉnh u và v. Cạnh e cũng được gọi là
cạnh nối các đỉnh u và v. Các đỉnh u và v gọi là các
điểm đầu mút của cạnh e.
Bậc của đỉnh v trong đồ thị G=(V,E), ký hiệu deg(v), là số
các cạnh liên thuộc với nó. Khuyên tại một đỉnh được
tính hai lần cho bậc của nó.
Đỉnh v gọi là đỉnh treo nếu deg(v)=1 và gọi là đỉnh cô lập
nếu deg(v)=0
6.1-Định nghĩa và khái niệm

8
v
1
v
2
v
3
v
4
v
5
v

ij
bằng 1 nếu cạnh (i,j)∈ E và bằng 0 nếu ngược lại.
Rõ ràng ma trận kề của đồ thị vô hướng là đối xứng.
Ngoài ra, a
ij
có thể gán một số nào đó gọi là trọng số.
Lúc đó, ta có ma trận trọng số.
Nhược điểm là luôn phải dùng n
2
đơn vị bộ nhớ để lưu
trữ ma trận kề.
}, ,2,1,:){( njiaA
ij
==
6.2- Biểu diễn đồ thị

11
Ví dụ: Ma trận kề của đồ thị













6
6.2- Biểu diễn đồ thị

12
622. Danh sách kề: Mỗi đỉnh v của đồ thị có danh
sách lưu trữ các đỉnh kề với nó, ký hiệu Ke(v):
Ke(v)={ u∈V: (v,u)∈E}
Người ta có thể dùng mảng hoặc danh sách liên kết
cho Ke(v). Chúng ta phải dùng m+n đơn vị bộ nhớ
để lưu trữ danh sách kề.
6.2- Biểu diễn đồ thị
v
1
v
2
v
3
v
4
v
5
e
1
e
2
e
3
e
4
e

13
12
Kết quả tìm kiếm theo
chiều sâu: 1, 2, 10, 4, 3,
5, 8, 6, 7, 9, 12, 11, 13
6.3- Duyệt đồ thị

15
Đặc điểm:
-
Mỗi đỉnh được thăm đúng 1 lần.
-
Mỗi lần quay về chương trình chính, thuật toán se
tạo ra một thành phần liên thông mới.
-
Độ phức tạp của thuật toán là O(n+m).
6.3- Duyệt đồ thị

16
Tim kiem theo chieu rong:
void main()
{ for (v ∈ V) chuaxet[v]:=true;
for (v ∈ V) do
if (chuaxet[v]) BFS(v);
}
6.3- Duyệt đồ thị

17
void BFS(v)
{ Queue:=∅;

=(x
n-1
,x
n
), với x
0
=u và
x
n
=v. Trong đồ thị đơn, ta ký hiệu đường đi này
bằng dãy các đỉnh x
0
, x
1
, , x
n
.
Nếu mỗi cung được đặt tương ứng một số thực a(x
i
,x
j
)
gọi là trọng số, lúc đó độ dài đường đi là:
Σa(x
i-1
,x
j
) với i=1 đến n
6.4- Đường đi ngắn nhất


}
6.4- Đường đi ngắn nhất

22
6.4- Đường đi ngắn nhất
2
1
3
4
6
5
1
2
7
2
5
1
1
1
4
3

23
6.4- Đường đi ngắn nhất
Bước lặp đỉnh 1 đỉnh 2 đỉnh 3 đỉnh 4 đỉnh 5 đỉnh 6
khởi tạo 0,1 1,1* ∞,1 ∞,1 ∞,1 ∞,1
1 - - 6,2 3,2* ∞,1 8,2
2 - - 4,4* - 7,4 8,2
3 - - - - 7,4 5,3*
4 - - - - 6,6* -