BÀI 01
1.1. Khái nim đồ th
1.1.1. Định nghĩa đồ th
Chúng ta đã nhìn thy hoc s dng bn đồ các tuyến đường giao thông ca
mt thành ph, sơ đồ t chc mt cơ quan, sơ đồ khi tính toán ca mt thut toán,
sơ đồ mt mng máy tính ... Đó là nhng ví d c th v đồ th.
Đồ th (graph) là mt mô hình toán hc được ng dng trong nhiu lĩnh vc
khoa hc, k thut và được định nghĩa như sau.
Định nghĩa 1.1: Đồ th là mt cp G = (V, E), trong đó:
1) V là tp hp các đỉnh (vertex),
2) E V × V là tp hp các cnh (edge).
Ví d 1.2:
Hình 1.1: Đồ th hu hn
Đồ th G cho hình v trên vi tp các đỉnh V = {a, b, c, d, e} và tp các cnh
E = {(a, b), (a, c), (b, c), (d, b), (d, c), (e, a), (e, b), (e, d)}.
Nếu (a, b) là mt cnh ca đồ th thì ta nói rng đỉnh b k vi đỉnh a và c
hai đỉnh ab k vi cnh (a, b).
Trong đồ th Ví d 1.2 hai đỉnh bc k vi đỉnh a, ba đỉnh a, b d k
vi đỉnh e. Do vy, ta có th định nghĩa đồ th bng ánh x k như sau.
Định nghĩa 1.3: Đồ th là mt cp G = (V, F), trong đó:
1) V là tp hp các đỉnh,
2) F : V 2V, được gi là ánh x k.
ánh x k ca đồ th trong Ví d 1.2 được xác định như sau:
F(a) = {b, c} , F(b) = {c} , F(c) = , F(d) = {b, c} và F(e) = {a, b, d}.
S tương đương ca hai định nghĩa ca đồ th được th hin bng mnh đề
sau đây:
x, y V : (x, y) E y F(x).
V bn cht, đồ th là mt tp hp các đối tượng được biu din bng các
đỉnh và gia các đối tượng này có mt quan h nh nguyên biu din bng các
cnh.
Cp đỉnh (x, y) E không sp th t được gi là cnh vô hướng, còn nếu nó
có sp th t thì được gi là cnh có hướng. Vì thế, chúng ta thường phân các đồ
th thành hai lp.
Định nghĩa 1.4: Đồ th ch cha các cnh vô hướng được gi là đồ th vô hướng,
còn đồ th ch cha các cnh có hướng được gi là đồ th có hướng.
Hin nhiên, mi đồ th vô hướng có th biu din bng mt đồ th có hướng
bng cách thay mi cnh vô hướng bng hai cnh có hướng tương ng.
Định nghĩa 1.5: Đồ th G = (V, E) được gi là đối xng nếu:
x, y V : (x, y) E (y, x) E.
Các đồ th vô hướng là đối xng.
Định nghĩa 1.6: Đồ th G = (V, E) mà mi cp đỉnh được ni vi nhau bi không
quá mt cnh được gi là đơn đồ th (thường gi tt là đồ th). Còn nếu đồ th
nhng cp đỉnh được ni vi nhau nhiu hơn mt cnh thì được gi là đa đồ th.
Ta có th biu din hình hc cho đồ th như sau: Trên mt phng biu din
đỉnh bng các vòng tròn nh, biu din cnh vô hướng bng đon thng, biu din
cnh có hướng bng mũi tên ni hai đỉnh ca đồ th.
Trong giáo trình này chúng ta ch xét các đồ th hu hn, nghĩa là các đồ th
có tp đỉnh là hu hn.
1.1.2. Đường đi và chu trình
Gi s G = (V, E) là mt đồ th.
Định nghĩa 1.7: Đường đi trong đồ th là mt dãy các đỉnh:
< x1, x2, ... , xi, xj+1, ... , xk-1 , xk >
sao cho, mi đỉnh trong dãy (không k đỉnh đầu tiên) k vi đỉnh trước nó bng
mt cnh nào đó, nghĩa là: i = 2, 3, ... , k-1, k : (xi-1, xi) E.
Ta nói rng đường đi này đi t đỉnh đầu x1 đến đỉnh cui xk. S cnh ca
đường đi được gi là độ dài ca đường đi đó.
Đường đi đơn là đường đi mà các đỉnh trên nó khác nhau tng đôi.
Định nghĩa 1.8: Chu trình là mt đường đi khép kín (tc là đỉnh cui ca đường
trùng vi đỉnh đầu ca đường). Ta thường ký hiu chu trình là:
[x1, x2, ... , xi, xj+1, ... xk-1, xk] , trong đó x1 = xk.
Để cho gn, trong ký hiu ca chu trình thường không viết đỉnh cui:
[x1, x2, ... , xi, xj+1, ... xk-1] .
Khi nói đến mt chu trình, ta cũng không cn xác định đỉnh đầu và đỉnh cui ca
chu trình đó.
Chu trình được gi là chu trình đơn nếu các đỉnh trên nó khác nhau tng đôi.
Trong mt đồ th, đỉnh nútđỉnh k vi chính nó. Hai cnh có ít nht mt
đỉnh chung được gi là hai cnh k nhau.
Để vic trình bày được ngn gn, trong sut cun sách này ta ký hiu n là s
đỉnh, m là s cnh ca mt đồ th.
1.1.3. Đồ th con và đồ th riêng
Gi s G = (V, E) là mt đồ th.
Định nghĩa 1.9:
1) Đồ th G = (V, E) được gi là đồ th con ca đồ th G nếu:
V V và E = E (V × V).
2) Đồ th G = (V, E) vi E E, được gi là đồ th riêng ca đồ th G.
Mi tp con các đỉnh V ca đồ th tương ng duy nht vi mt đồ th con,
do vy để xác định mt đồ th con ta ch cn nêu tp đỉnh ca nó. Còn đồ th riêng
đồ th gi nguyên tp đỉnh và b bt mt s cnh.
1.1.4. S đẳng hình ca các đồ th
S đẳng hình ca hai đồ th da trên s đẳng cu ca hai tp đỉnh sao cho s
đẳng cu y bo toàn được các cnh ca đồ th.
Định nghĩa 1.10: Hai đồ th G1 = (V1, E1) và G2 = (V2, E2) được gi là đẳng hình
nếu tn ti mt song ánh trên các tp đỉnh, S : V1 V2 bo toàn các cnh:
x, y V1 , (x, y) E1 (S(x), S(y)) E2.
Chúng ta s không phân bit hai đồ th đẳng hình vi nhau vì v thc cht
chúng ch khác nhau v tên gi ca các đỉnh và cách biu din bng hình v.
Ví d 1.11: Hai đồ th dưới đây là đẳng hình vi song ánh:
S(ai) = xi
, i = 1, 2, 3, 4.
Hình 1.2. Hai đồ th đẳng hình
1.1.5. Các cách biu din đồ th trong máy tính
a) Biu din đồ th bng ma trn k
Gi s G = (V, E) là mt đồ th. Ta đánh s các đỉnh ca đồ th bng các s
t nhiên: 1, 2, ... , n. Xây dng ma trn vuông biu din đồ th như sau:
Ma trn vuông An x n được gi là ma trn k ca đồ th G nếu:
i, j V, A[i,j] = d , trong đó d là s cnh ni đỉnh i vi đỉnh j trong G.
D thy rng, đồ th G là đối xng khi và ch khi ma trn k A là đối xng.
Ví d 1.12: Ma trn k ca đa đồ th có hướng.
Hình 1.3. Đồ th có hướng và ma trn k tương ng
Cách biu din đơn gin này ca đồ th cho ta kết qu sau đây.
Định lý 1.1: Phn t hàng i ct j ca ma trn lu tha Ak là s các đường
đi khác nhau có độ dài k ni đỉnh i vi đỉnh j trong đồ th G.
Chng minh:
Ta chng minh bng quy np theo độ dài k ca đường đi.
k = 1: suy t chính định nghĩa ca ma trn k.
(k) (k+1): Ký hiu A = [aij] , Ak = [bij] ,
C = Ak . A = [cij]
Khi đó: cij =
=
n
q1
biq* aqj
Hình 1.4. Các đường đi t đỉnh i đến đỉnh j qua đỉnh q
Vi q bt k, 1
q
n thì theo gi thiết quy np biq s đường đi t đỉnh i đến
đỉnh q có độ dài k. Nếu aqj = 0 thì không có cnh t q đến j, do đó cũng không
đường đi t i đến j qua q vi độ dài k+1.
Nếu atj = d 1 thì có cnh đi t q đến j. Do đó có các đường đi t i đến j qua
q vi độ dài k+1, mà s các đường đi đó chính là d.bit.
Vy tính cij theo tng trên, ta s có tt c các đường đi t i đến j vi độ dài
k+1. Định lý đã được chng minh.
b) Biu din đồ th bng các danh sách k
Vi mi đỉnh ca đồ th ta xây dng mt danh sách móc ni cha các đỉnh k
vi đỉnh này. Danh sách này được gi là danh sách k. Mt đồ th được biu din
bng mt mng các danh sách k.
Ví d 1.13: Biu din mng các danh sách k ca đồ th G trong Ví d 1.2.
p[a] b c
p[b] c
p[c]
p[d] b c
p[e] a b d
Hình 1.5. Mng các danh sách k biu din đồ th