CH NG 1ƯƠ
CÁC KHÁI NI M C B NỆ Ơ Ả
1. Đ nh nghĩa đ thị ồ ị
-G i Vọ
≠
φ
là t p đ nh; E={e=(u,v): u,vậ ỉ
∈
V} là t p c nh; và G = (V,E) g i là đ th .ậ ạ ọ ồ ị
-N u m i c nh là m t c p đ nh không có th t thì g i là đ th vô h ng, ng c l i g i làế ỗ ạ ộ ặ ỉ ứ ự ọ ồ ị ướ ượ ạ ọ
đ th có h ng. Trong đ th vô h ng, n u c nh (u,v) thu c E thì (v,u) cũng thu c E.ồ ị ướ ồ ị ướ ế ạ ộ ộ
Trong đ th có h ng c nh đ c g i là cung.ồ ị ướ ạ ượ ọ
-N u m i c p đ nh ch t ng ng v i m t c nh thì g i là đ n đ th , ng c l i g i là đa đế ỗ ặ ỉ ỉ ươ ứ ớ ộ ạ ọ ơ ồ ị ượ ạ ọ ồ
th .ị
Ví d :ụ
R t nhi u bài toán có th mô hình hoá b ng đ th và gi i quy t b ng các thu t toán trên đấ ề ể ằ ồ ị ả ế ằ ậ ồ
th . ị
Ví d : ụ
X p l ch thi đ u là m t đ th vô h ng v i m i đ i là đ nh, hai đ i thi đ u v i nhau là c nh.ế ị ấ ộ ồ ị ướ ớ ỗ ộ ỉ ộ ấ ớ ạ
M ng giao thông là m t đa đ th có h ng v i nút giao thông là đ nh, đ ng đi gi a hai nútạ ộ ồ ị ướ ớ ỉ ườ ữ
là cung. T ng t vi c thi t k m ng máy tính, m ng vi n thông có th đ a v bài toán đ th .ươ ự ệ ế ế ạ ạ ễ ể ư ề ồ ị
2. Các thu t ng ậ ữ
-Khuyên: c nh (cung) e g i là khuyên n u e có d ng (v,v).ạ ọ ế ạ
-C nh (cung) l pạ ặ : là hai c nh (cung) cùng t ng ng v i m t c p đ nh.ạ ươ ứ ớ ộ ặ ỉ
-Đ nh kỉ ề: n u (u,v) là c nh (ho c cung) c a đ th thì v g i là k c a u. Trong đ th vôế ạ ặ ủ ồ ị ọ ề ủ ồ ị
h ng n u v k u thì u cũng k v, nh ng trong đ th có h ng thì không ch c.ướ ế ề ề ư ồ ị ướ ắ
-C nh liên thu cạ ộ : Trong đ th vô h ng, c nh e=(u,v) g i là c nh liên thu c v i đ nh u vàồ ị ướ ạ ọ ạ ộ ớ ỉ
liên thu c v i đ nh v. ộ ớ ỉ
-B c c a đ nhậ ủ ỉ : Trong đ th vô h ng, s c nh liên thu c v i v g i là b c c a đ nh v, kíồ ị ướ ố ạ ộ ớ ọ ậ ủ ỉ
hi u là deg(v).ệ
Ví d : Xét đ th hình 1,deg(a)=1, deg(b)=deg(c)=4, deg(d)=1, deg(e)=deg(f)=3, deg(g)=0ụ ồ ị
-Đ nh cô l p, đ nh treoỉ ậ ỉ : Trong đ th vô h ng, đ nh b c 0 g i là đ nh cô l p , đ nh b c 1ồ ị ướ ỉ ậ ọ ỉ ậ ỉ ậ
g i là đ nh treo.ọ ỉ
1
Hình 1: Đ th vô h ngồ ị ướ
a
e
c
d
g
f
b
B
A
E
D
C
Hình 2: Đ th có h ngồ ị ướ
v2
v1
Cung
l pặ
v2
v1
C nh ạ
l pặ
v
v
Khuyên
Ví d : Xét đ th hình 1, a là đ nh treo, g là đ nh cô l pụ ồ ị ỉ ỉ ậ
-Cung vào, ra: Trong đ th có h ng, cung e=(u,v) g i là cung ra kh i u và là cung vào v.ồ ị ướ ọ ỏ
-Bán b c c a đ nhậ ủ ỉ : Trong đ th có h ng, s cung vào v g i là bán b c vào c a đ nh v, kíồ ị ướ ố ọ ậ ủ ỉ
hi u là: degệ-(v), s cung ra kh i v g i là bán b c ra c a đ nh v, kí hi u là: degố ỏ ọ ậ ủ ỉ ệ +(v)
Ví d : Xét đ th hình 1, ụ ồ ị
deg-(A)=2, deg-(B)=3, deg-(C)=1, deg-(D)=2, deg-(E)=2
deg+(A)=3, deg+(B)=2, deg+(C)=2, deg+(D)=2, deg+(E)=1
-Đ nh lý 1ị : Trong đ th vô h ng thì t ng b c c a t t c các đ nh b ng 2 l n s c nh.ồ ị ướ ổ ậ ủ ấ ả ỉ ằ ầ ố ạ
∑
∈Vv
v)deg(
= 2m (m là s c nh)ố ạ
Ch ng minh:ứ
M i c nh e=(u,v) đ c tính m t l n trong deg(u) và m t l n trong deg(v) nên trong t ngỗ ạ ượ ộ ầ ộ ầ ổ
b c c a các đ nh, m i c nh đ c tính hai l n, mà có m c nh nên suy ra t ng b c b ngậ ủ ỉ ỗ ạ ượ ầ ạ ổ ậ ằ
2m.
Ví d : đ th có n đ nh, m i đ nh có b c là 6. H i đ th có bao nhiêu c nh?ụ ồ ị ỉ ỗ ỉ ậ ỏ ồ ị ạ
HD: 6n=2m
m=3n
-H quệ ả : Trong đ th vô h ng, s đ nh có b c là s l là m t s ch n ồ ị ướ ố ỉ ậ ố ẻ ộ ố ẵ
Ch ng minh:ứ
G i O là t p các đ nh có b c là s l , và U là t p các đ nh có b c là s ch n. ọ ậ ỉ ậ ố ẻ ậ ỉ ậ ố ẵ
Ta có:
∑
∈Vv
v)deg(
=
∑
∈Ov
v)deg(
+
∑
∈Uv
v)deg(
= 2m
Do
∀
v
∈
U, deg(v) ch n nên ẵ
∑
∈Uv
v)deg(
∑
∈Ov
v)deg(
ch nẵ
Do
∀
v
∈
O, deg(v) l mà t ng ẻ ổ
∑
∈Ov
v)deg(
ch n, nên t ng này ph i g m m t s ch n cácẵ ổ ả ồ ộ ố ẵ
s h ng ố ạ
⇒
s đ nh có b c là s l là m t s ch n (đpcm).ố ỉ ậ ố ẻ ộ ố ẵ
-Đ nh lý 2ị : Trong đ th có h ng, t ng bán b c ra c a t t c các đ nh b ng t ng bán b cồ ị ướ ổ ậ ủ ấ ả ỉ ằ ổ ậ
vào c a t t c các đ nh và b ng s c nh c a đ thủ ấ ả ỉ ằ ố ạ ủ ồ ị
∑
∈
+
Vv
v)(deg
=
∑
∈
−
Vv
v)(deg
= m (m là s c nh)ố ạ
Ch ng minh: Hi n nhiên vì m i cung đ u ra m t đ nh và vào m t đ nh khác.ứ ể ỗ ề ở ộ ỉ ở ộ ỉ
3. Đ ng đi, chu trình, liên thôngườ
* Đ ng đi, chu trình: ườ
-Đ ng đi:ườ Đ ng đi có đ dài n t đ nh vườ ộ ừ ỉ 0 đ n đ nh vế ỉ n là dãy v0, v1, …,vn-1, vn ; v i (với vi+1)
∈
E,
∀
i=0,…,n-1. Đ ng đi có th bi u di n b ng m t dãy n c nh (cung): (vườ ể ể ễ ằ ộ ạ 0, v1),…, (v1, v2),
…, (vn-1, vn). Đ nh vỉ0 g i là đ nh đ u, đ nh vọ ỉ ầ ỉ n g i là đ nh cu i c a đ ng đi.ọ ỉ ố ủ ườ
-Chu trình: là đ ng đi có đ nh đ u trùng v i đ nh cu i. Đ ng đi (hay chu trình) g i là đ nườ ỉ ầ ớ ỉ ố ườ ọ ơ
n u không có c nh (cung) b l p l i.ế ạ ị ặ ạ
Ví d :ụ
2
d
f
a
b
c
e
Hình 3:đt vô hu ngớ
d
f
a
b
c
e
Hình 4:đt có hu ngớ
Trên hình 3:
a, d, c, f, e: là đ ng đi đ n đ dài 4ườ ơ ộ
d, e, c, a: không ph i đ ng điả ườ
b, c, f, e, b: là chu trình đ dài 4.ộ
a, b, e, d, a, b: là đ ng đi không đ n (qua c nh ab hai l n) có đ dài 5ườ ơ ạ ầ ộ
Trên hình 4:
a, d, c, f, e: là đ ng đi đ dài 4ườ ộ
d, e, c, a: không là đ ng đi.ườ
b, c, f, e, b: là chu trình đ dài 4ộ
a, b, e, d, a, b: là đ ng đi không đ n (qua c nh ab hai l n), có đ dài 5ườ ơ ạ ầ ộ
* Đ th Liên Thông: ồ ị
-Đ th g i là liên thông n u hai đ nh b t kỳ luôn có đ ng đi. N u đ th không liên thông,ồ ị ọ ế ỉ ấ ườ ế ồ ị
đ th luôn có th chia thành các đ th con liên thông và đôi m t không có đ nh chung.ồ ị ể ồ ị ộ ỉ
-Đ th có h ng liên thông còn đ c g i là liên thông m nh. N u đt có h ng không liênồ ị ướ ượ ọ ạ ế ướ
thông nh ng n u đ th vô hu ng t ng ng liên thông thì đ th có h ng g i là liên thôngư ế ồ ị ớ ươ ứ ồ ị ướ ọ
y u.ế
-Đ th vô h ng liên thông g i là đ nh h ng đ c n u có th đ nh h ng các c nh đ thuồ ị ướ ọ ị ướ ượ ế ể ị ướ ạ ể
đ c đ th có h ng liên thông m nh.ượ ồ ị ướ ạ
Ví d :ụ
* Đ nh r nhánh, c u:ỉ ẽ ầ
3
Hình 5: đt G liên thông và đt H g m 3 thành ph n liên thông Hồ ầ 1, H2, H3.
a
b
c
d
e
g
f
G
H
A
B
B
B
B
G
A
B
B
B
B
H
Hình 6: Đt G liên thông m nh, H liên thông y u.ạ ế
-Đ nh v g i là đ nh r nhánh n u vi c lo i b v cùng v i các c nh liên thu c v i nó làm tăngỉ ọ ỉ ẽ ế ệ ạ ỏ ớ ạ ộ ớ
s thành ph n liên thông.ố ầ
-C nh e g i là c u n u vi c lo i b e làm tăng s thành ph n liên thông.ạ ọ ầ ế ệ ạ ỏ ố ầ
Ví d :ụ
Trong hình 5: đ th G có đ nh d, e là đ nh r nhánh; c nh (d,g), (e,f) là c uồ ị ỉ ỉ ẽ ạ ầ
-Đ nh lý 3ị : G là đ th vô h ng liên thông.ồ ị ướ
G đ nh h ng đ c ị ướ ượ
⇔
m i c nh c a G n m trên ít nh t m t chu trình.ỗ ạ ủ ằ ấ ộ
Ch ng minh:ứ
(
) G đ nh h ng đ c ị ướ ượ
⇒
G liên thông m nh ạ
∀
(u,v)
∈
E,
∃
đ ng đi có h ng t u đ n vườ ướ ừ ế
⇒
∃
đ ng đi vô h ng t u đ n v. Đ ng đi này k t h p v i c nh (u,v) s t o m t chu trìnhườ ướ ừ ế ườ ế ợ ớ ạ ẽ ạ ộ
ch a c nh (u,v) (xem hình 7)ứ ạ
(
) Ta xây d ng m t thu t toán xác đ nh h ng các c nh c a G đ G liên thông m nh.ự ộ ậ ị ướ ạ ủ ể ạ
Gi s C là m t chu trình, đ nh h ng các c nh trên chu trình theo m t h ng đi vòng theoả ử ộ ị ướ ạ ộ ướ
chu trình.
N u t t c các c nh c a đ th đã đ c đ nh h ng thì k t thúc thu t toán. Ng c l i, ch nế ấ ả ạ ủ ồ ị ượ ị ướ ế ậ ượ ạ ọ
c nh e ch a đ nh h ng mà e có chung đ nh v i ít nh t m t trong s các c nh đã đ nh h ngạ ư ị ướ ỉ ớ ấ ộ ố ạ ị ướ
(e t n t i vì G liên thông). Theo gi thi t tìm đ c chu trình C’ ch a c nh e. Đ nh h ng cácồ ạ ả ế ượ ứ ạ ị ướ
c nh ch a đ c đ nh h ng c a C’ theo m t h ng d c theo C’. Thu t toán l p l i cho t i khiạ ư ượ ị ướ ủ ộ ướ ọ ậ ặ ạ ớ
t t c các c nh c a đ th đ c đ nh h ng (xem hình 8)ấ ả ạ ủ ồ ị ượ ị ướ
4. M t s đ th đ c bi t.ộ ố ồ ị ặ ệ
a) Đ th đ y đ :ồ ị ầ ủ
Đ th đ y đ n đ nh, ký hi u b i Kồ ị ầ ủ ỉ ệ ở n, là đ n đ th vô h ngơ ồ ị ướ mà gi a hai đ nh b t kỳ c a nóữ ỉ ấ ủ
luôn có c nh n i.ạ ố
-Đ nh lý 4ị : Đ th đ y đ Kồ ị ầ ủ n có t t c n(n-1)/2 c nh, nó là đ n đ th có nhi u c nh nh t.ấ ả ạ ơ ồ ị ề ạ ấ
Ch ng minh:ứ
Đ nh 1 n i v i n-1 đ nh còn l i, đ nh 2 n i v i n-2 đ nh còn l i,…Nên t ng s c nh là:ỉ ố ớ ỉ ạ ỉ ố ớ ỉ ạ ổ ố ạ
(n-1)+(n-2)+…+1 = (n-1)(n-1+1)/2=n(n-1)/2
4
v
u
C
C’
e
Hình 7 Hình 8
b) Đ th vòngồ ị
Đ th vòng Cồ ị n, n≥3. g m n đ nh vồ ỉ 1, v2,. . . .vn và các c nh (vạ1,v2), (v2,v3) . . . (vn-1,vn), (vn,v1).
c) Đ th bánh xeồ ị
Đ th bánh xe Wồ ị n thu đ c t đ th vòng Cượ ừ ồ ị n b ng cách b sung vào m t đ nh m i n i v iằ ổ ộ ỉ ớ ố ớ
t t c các đ nh c a Cấ ả ỉ ủ n
d) Đ th l p ph ngồ ị ậ ươ
Đ th l p ph ng n đ nh Qồ ị ậ ươ ỉ n là đ th v i các đ nh bi u di n 2ồ ị ớ ỉ ể ễ n xâu nh phân đ dài n. Haiị ộ
đ nh c a nó g i là k nhau n u nh hai xâu nh phân t ng ng ch khác nhau 1 bit.ỉ ủ ọ ề ế ư ị ươ ứ ỉ
e) Đ th hai phíaồ ị
Đ n đ th G=(V,E) đ c g i là hai phía n u nh t p đ nh V c a nó có th phân ho chơ ồ ị ượ ọ ế ư ậ ỉ ủ ể ạ
thành hai t p X và Y sao cho m i c nh c a đ th ch n i m t đ nh nào đó trong X v i m tậ ỗ ạ ủ ồ ị ỉ ố ộ ỉ ớ ộ
đ nh nào đó trong Y. Ký hi u G=(Xỉ ệ
∪
Y, E) đ ch đ th hai phía v i t p đ nh Xể ỉ ồ ị ớ ậ ỉ
∪
Y.
-Đ nh lý 5 ị : Đ n đ th là đ th hai phía khi và ch khi nó không ch a chu trình đ dài l .ơ ồ ị ồ ị ỉ ứ ộ ẻ
Ch ng minh: (ch p nh n)ứ ấ ậ
-Thu t toán ki m tra đ th liên thông là hai phía:ậ ể ồ ị
B0:Ch n v là m t đ nh b t kỳ c a đ th . Đ t X={v} ọ ộ ỉ ấ ủ ồ ị ặ
B1:Tính Y là t p các đ nh k c a các đ nh trong X. ậ ỉ ề ủ ỉ
B2:N u Xế
∩
Y
≠
φ
thì đ th không ph i là hai phía, k t thúc. Ng c l i xu ng B3 ồ ị ả ế ượ ạ ố
B3: G i T là t p các đ nh k c a các đ nh trong Y, T ph i thu c vào X. N u Tọ ậ ỉ ề ủ ỉ ả ộ ế
∩
Y
≠
φ
thì đồ
th không ph i là hai phía, k t thúc. Ng c l i xu ng B4 ị ả ế ượ ạ ố
B4: Đ t X=Xặ
∪
T. N u Xế
∪
Y=E thì đ th là hai phía, k t thúc. Ng c l i l p l i B1.ồ ị ế ượ ạ ặ ạ
5