Chương VI. ĐỒ THỊ
I. ĐỊNH NGHĨA VÀ MỘT SỐ KHÁI NIỆM
Một đồ thị G(V,E) là 1 tập bao gồm 2 tập con :
- Tập hữu hạn V, không rỗng, của các phân tử mà ta gọi là đỉnh (vertices).
- Tập hữu hạn E, của các cặp đỉnh, mà mỗi cặp ta gọi là 1 cung (edge).
Bản đồ đường bộ giữa các thành phố trong 1 khu vực là 1 đồ thị với thành
phố là đỉnh, đường lối trong thời gian đó là cung.
Mạng máy tính của 1 công ty, sơ đồ mạch điện của 1 khu chung cư, cấu trúc
phân tử của các hợp chất hữu cơ v.v…tất cả đều có dạng đồ thị.
Nếu u và v là 2 đỉnh trên đồ thị mà thứ tự được phân biệt trong từng cặp,
nghĩa vụ là (u, v) khác với (v, u) thì đồ thị được gọi là đồ thị có hướng (directed
graph).
Lúc đó (u, v)được gọi là cung từ u tới v còn (v, u) được gọi là cung từ v tới
u.
Nếu thứ tự 2 đỉnh của 1 cung không được coi trọng thì đồ thị được gọi là đồ
thị vô hướng (undirected grap) và (u, v)được gọi là cung giữa u và v hoặc cung
giữa v và u.
Trên hình vẽ cung có hướng được biểu diễn bằng mũi tên còn cung vô
hướng thì bằng 1 đoạn thẳng.
Hình 6.1 minh hoạ 1 số đồ thị :G1, G2 là các đồ thị có hướng ; G3, G4 là các
đồ thị vô hướng. Ở đây ta quy ước : các đỉnh được đánh số từ 1 tới n (nếu đồ thị
có n đỉnh).
Nếu trên đồ thị G (V,E) có 1 cung đi từ u tới v thì ta nói : v là đỉnh lân cận
của u hay là đỉnh kề (adjacent) của u. Tất nhiên với đồ thị vô hướng, khi có cung
giữa 2 đỉnh, thì ta nói đỉnh này là lân cận của đỉnh kia.
1
2
3
G
1
1
2
4
3
Một đường đi (path) từ đỉnh u tới đỉnh v là 1 dãy các đỉnh :
x0, x1,…,xn-1, xn (n là số nguyên dương), trong đó : u = x0, v = xn và (xi, xi+1)
với i = 0, 1, 2, …, n-1 là các cung thuộc E , u gọi là đỉnh đầu, v gọi là đỉnh cuối.
Số lượng các cung trên 1 đường đi được gọi là độ dài của đường đi (path length).
Một đường đi đơn (simple path) là đường đi mà mọi đỉnh trên đó, trừ đỉnh
đầu và đỉnh cuối đều khác nhau.
Trường hợp đỉnh đầu trùng với đỉnh cuối ta gọi là chu trình (cycle).
Ví dụ : với đồ thị G2 (hình 6.1),ta có :
Đường đi 1, 2, 3, 4 là đường đi đơn có độ dài bằng 3.
Đường đi 1, 4, 2, 3, 1 là 1 chu trình có độ dài bằng 4.
Một đồ thị gọi là liên thông(cennected) nếu luôn có đường đi giữa 2 đỉnh bất
kì của nó. Đối với đồ thị có hướng thì trường hợp đó người ta gọi là liên thông
mạnh (strengly connected).
Ví dụ : trong hình 6.1 :
- Các đồ thị G2 và G3 là liên thông.
- Các đồ thị G1 và G4 là không liên thông (vì ở G1 không có đường đi, chẳng
hạn, từ đỉnh 1 đến đỉnh 2 ; ở G4 không có đường đi từ đỉnh 4 dến đỉnh 3 v.v…).
Có khi ở mỗi cung của đồ thị người ta gắn vào đấy 1 giá trị thể hiện 1 thông
tin nào đó có liên quan tới cung, giá trị đó được gọi là trọng số, và đồ thị được gọi
là đồ thị có trọng số (weighted graph).
1
2
3
4
5
G3
1
2
3
4
5
G4
a) Đồ thị có hướng
b) Đồ thị vô hướng
Hình 6.
1
Ví dụ : đồ thị trên hình 6.2 thể hiện các đường đi nối giữa6 tỉnh A, B, C, D,
E, F với các trọng số là độ dài tính theo km, của các tuyến đường.
II. BIỂU DIỄN TRONG MÁY CỦA ĐỒ THỊ
Cũng như các cấu trúc dữ liệu nói ở các chương trước, đối với đồ thị, ta cũng
xét tới 2 cách biểu diễn thông dụng sau đây :
1. Biểu diễn bằng ma trận lân cận (lưu trữ kế tiếp)
Xét 1 đồ thị có hướng G (V, E) với V có n đỉnh (n≥1). Giả sử các đỉnh đã
được đánh số từ 1 đến n.
Đồ thị G có thể được biểu diễn trong máy bởi 1 ma trận vuông A, kích thước
n × n, mà các phần tử Aij của nó sẽ nhận giá trị 1 hoặc 0 :
Aij = 1 nếu trên G tồn tại 1 cung đi từ đỉnh i tới đỉnh j.
Aij = 0 nếu không có cung giữa đỉnh i và j.
Dĩ nhiên với đồ thị vô hướng, nếu tồn tại 1 cung (i, j) thì ta có thể hiểu là tồn
tại 1 cung đi từ i đến j, và ngược lại, cũng tồn tại 1 cung đi từ j tới i, nghĩa là Aij
=1thì Aji = 1.
Như vậy với đồ thị vô hướng thì ma trận A biểu diễn nó có các phân tử đối
xứng với nhau qua đường chéo chính.
Ma trận A được gọi là ma trận lân cận hay ma trận kề (adjacency matrix)
của đồ thị G.
Ví dụ : với đồ thị G2 ở hình 6.1 thì ma trận lân cận có dạng
A
B
C
D
E
F
Hình 6.2
83 55
47 60
26
150
A =
0
0
1
0
1
0
0
1
1
1
0
0
1
0
1
0
Với đồ thị G3 ở hình 6.1 thì ma trận lân cận có dạng :
Do ma trận được lưu trữ kế tiếp (đã nêu ở mục 2.2.2 chương 2) nên việc truy
cập vào các phần tử của ma trận lân cận được thực hiện trực tiếp với tốc độ nhanh.
Nhưng cách lưu trữ này rõ ràng tốn không gian nhớ khi n lớn.
2. Biểu diễn bằng danh sách lân cận (lưu trữ móc nối)
Với cách biểu diễn này mỗi đỉnh sẽ ứng với 1 danh sách móc nối được gọi là
danh sách lân cận hay danh sách kề (adjacency list). Mỗi nút trong danh sách đó
có quy cách :
Trường VERTEX chứa số j ứng với đỉnh j là lân cận của đỉnh i (1≤ i ≤ n)
trong danh sách lân cận của i.
Trường LINK chứa con trỏ, trỏ tới nút tiếp theo trong danh sách.
Danh sách có m nút (người ta còn gọi là “nút danh sách”) ; nếu đỉnh i có m
đỉnh lân cận.
Mỗi danh sách như vậy lại có “nút đầu danh sách” (list head node). Thường
các “ nút đầu danh sách” là các phần tử của 1 vectơ V, có kích thước bằng n, phần
tử V[i] của V(1≤ i ≤ n), ứng với danh sách lân cận của nút thứ i, nó chứa địa chỉ
nút đầu tiên của danh sách lân cận này.
Hình ảnh danh sách lân cận biểu diễn đồ thị G2 và G3 sẽ như sau :
VERTEX LINK
0
0
1
1
0
A =
1
1
0
0
1
0
1
0
0
1
0
1
0
1
0
1
0
1
1
0
V[ 1 ]
V[ 2 ]
V[ 3 ]
V[ 4 ]
2
1
4
3
3
4
2
a) Danh sách lân cận biểu diễn G2
(ở đây ta quy ước : Các số ở trường VERTEX của các nút được sắp xếp theo thứ
tự tăng dần )
Ta thấy nếu đồ thị có hướng G (V, E) có n đỉnh, e cung thì số nút cần thiết sẽ
là : n “nút đầu danh sách” và e “nút danh sách”. Nhưng với đồ thị vô hướng thì lại
cần n + 2e nút.
III. ÁP DỤNG
1.Bài toán đi tìm đường đi
Xét 1 đồ thị G(V, E) với n đỉnh được đánh số từ 1 tới n.
Một câu hỏi có thể được đặt ra là :
“có hay không đường đi từ đỉnh i tới đỉnh j ?”(1)
Nếu đồ thị này biểu diễn 1 mạng lưới đường bộ giữa các thành phố thuộc 1
vùng nào đó thì đối với 1 người đi du lịch bằng xe đạp, muốn đi từ i đến j, câu hỏi
này họ sẽ phải đặt ra đầu tiên. Hành trình của họ chỉ có thể tiếp tục được nếu câu
trả lời là “có”. Mà “có” thì cần phải hiểu là : có thể có nhiều đường nhưng ít nhất
thì cũng phải có 1 đường.
Vậy để trả lời cho câu hỏi (1) đặt ra ở trên ta phải dựa vào đâu?
Ta biết rằng : đồ thị G(V, E) được biểu diễn trong máy bởi ma trận lân cận
A. Nếu Aij = 1 thì nghĩa là có 1 cung đi từ i tới j hay có thể nói : có đường đi độ
dài 1 (bằng 1 cung) từ i tới j.
b) Danh sách lân cận biểu diễn G3
Hình 6.3
V[1 ]
V[2 ]
V[3 ]
V[4 ]
V[5 ]
24
1
3
2
5
1
3
4
4
2
5