CH NG IIIƯƠ
Đ THỒ Ị
Lý thuy t đ th là m t ngành khoa h c đ c phát tri n t lâu nh ng l i cóế ồ ị ộ ọ ượ ể ừ ư ạ
nhi u ng d ng hi n đ i. Nh ng ý t ng c b n c a nó đ c đ a ra t th k 18 b iề ứ ụ ệ ạ ữ ưở ơ ả ủ ượ ư ừ ế ỷ ở
nhà toán h c Th y Sĩ tên là Leonhard Euler. Ông đã dùng đ th đ gi i quy t bài toánọ ụ ồ ị ể ả ế
7 chi c c u Konigsberg n i ti ng.ế ầ ổ ế
Đ th cũng đ c dùng đ gi i các bài toán trong nhi u lĩnh v c khác nhau. Thíồ ị ượ ể ả ề ự
d , dùng đ th đ xác đ nh xem có th c hi n m t m ch đi n trên m t b ng đi nụ ồ ị ể ị ự ệ ộ ạ ệ ộ ả ệ
ph ng đ c không. Chúng ta cũng có th phân bi t hai h p ch t hóa h c có cùng côngẳ ượ ể ệ ợ ấ ọ
th c phân t nh ng có c u trúc khác nhau nh đ th . Chúng ta cũng có th xác đ nhứ ử ư ấ ờ ồ ị ể ị
xem hai máy tính có đ c n i v i nhau b ng m t đ ng truy n thông hay không n uượ ố ớ ằ ộ ườ ề ế
dùng mô hình đ th m ng máy tính. Đ th v i các tr ng s đ c gán cho các c nhồ ị ạ ồ ị ớ ọ ố ượ ạ
c a nó có th dùng đ gi i các bài toán nh bài toán tìm đ ng đi ng n nh t gi a haiủ ể ể ả ư ườ ắ ấ ữ
thành ph trong m t m ng giao thông. Chúng ta cũng có th dùng đ th đ l p l ch thiố ộ ạ ể ồ ị ể ậ ị
và phân chia kênh cho các đài truy n hình.ề
3.1. Đ NH NGHĨA VÀ THÍ D .Ị Ụ
Đ 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 đó. Ng i ta phân lo i đ th tùy theo đ c tính và s các c nh n iướ ố ỉ ườ ạ ồ ị ặ ố ạ ố
các c p đ nh c a đ th . 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 . Ch ng h n ng i ta có th dùng đ th đ bi u di n sượ ằ ồ ị ẳ ạ ườ ể ồ ị ể ể ễ ự
c nh tranh các loài trong m t môi tr ng sinh thái, dùng đ th đ bi u di n ai có nhạ ộ ườ ồ ị ể ể ễ ả
h ng lên ai trong m t t ch c nào đó, và cũng có th dùng đ th đ bi u di n cácưở ộ ổ ứ ể ồ ị ể ể ễ
k t c c c a cu c thi đ u th thao. Chúng ta cũng có th dùng đ th đ gi i các bàiế ụ ủ ộ ấ ể ể ồ ị ể ả
toán nh bài toán tính s các t h p khác nhau c a các chuy n bay gi a hai thành phư ố ổ ợ ủ ế ữ ố
trong m t m ng hàng không, hay đ gi i bài toán đi tham quan t t c các đ ng phộ ạ ể ả ấ ả ườ ố
c a m t thành ph sao cho m i đ ng ph đi qua đúng m t l n, ho c bài toán tìm sủ ộ ố ỗ ườ ố ộ ầ ặ ố
các màu c n thi t đ tô các vùng khác nhau c a m t b n đ .ầ ế ể ủ ộ ả ồ
Trong đ i s ng, chúng ta th ng g p nh ng s đ , nh s đ t ch c b máy,ờ ố ườ ặ ữ ơ ồ ư ơ ồ ổ ứ ộ
s đ giao thông, s đ h ng d n th t đ c các ch ng trong m t cu n sách, ,ơ ồ ơ ồ ướ ẫ ứ ự ọ ươ ộ ố
g m nh ng đi m bi u th các đ i t ng đ c xem xét (ng i, t ch c, đ a danh,ồ ữ ể ể ị ố ượ ượ ườ ổ ứ ị
ch ng m c sách, ) và n i m t s đi m v i nhau b ng nh ng đo n th ng (ho cươ ụ ố ộ ố ể ớ ằ ữ ạ ẳ ặ

Đ th vô h ng nh n đ c t đ th có h ng G b ng cách xoá b các chi uồ ị ướ ậ ượ ừ ồ ị ướ ằ ỏ ề
mũi tên trên các cung đ c g i là đ th vô h ng n n c a G.ượ ọ ồ ị ướ ề ủ
Thí d 2:ụ

Đ th có h ng Đa đ th có h ng ồ ị ướ ồ ị ướ
38
v
1
v
2
v
3
v
4
v
5
v
6
v
7
v
1
v
2
v
3
v
4
v
5

trong m t h sinh thái có th mô hình hóa b ng đ th “l n t ”. M i loài đ c bi uộ ệ ể ằ ồ ị ấ ổ ỗ ượ ể
di n b ng m t đ nh. M t c nh vô h ng n i hai đ nh n u hai loài đ c bi u di nễ ằ ộ ỉ ộ ạ ướ ố ỉ ế ượ ể ễ
b ng các đ nh này là c nh tranh v i nhau.ằ ỉ ạ ớ
2) Đ th nh h ngồ ị ả ưở . Khi nghiên c u tính cách c a m t nhóm ngu i, ta th y m t sứ ủ ộ ờ ấ ộ ố
ng i có th có nh h ng lên suy nghĩ c a nh ng ng i khác. Đ th có h ng đ cườ ể ả ưở ủ ữ ườ ồ ị ướ ượ
g i là đ th nh h ngọ ồ ị ả ưở có th dùng đ mô hình bài toán này. M i ng i c a nhómể ể ỗ ườ ủ
đ c bi u di n b ng m t đ nh. Khi m t ng i đ c bi u di n b ng đ nh a có nhượ ể ễ ằ ộ ỉ ộ ườ ượ ể ễ ằ ỉ ả
h ng lên ng i đ c bi u di n b ng đ nh b thì có m t cung n i t đ nh a đ n đ nh b.ưở ườ ượ ể ễ ằ ỉ ộ ố ừ ỉ ế ỉ
3) Thi đ u vòng tròn.ấ M t cu c thi đ u th thao trong đó m i đ i đ u v i m i đ iộ ộ ấ ể ỗ ộ ấ ớ ỗ ộ
khác đúng m t l n g i là đ u vòng tròn. Cu c thi đ u nh th có th đ c mô hìnhộ ầ ọ ấ ộ ấ ư ế ể ượ
b ng m t đ th có h ng trong đó m i đ i là m t đ nh. M t cung đi t đ nh a đ nằ ộ ồ ị ướ ỗ ộ ộ ỉ ộ ừ ỉ ế
đ nh b n u đ i a th ng đ i b.ỉ ế ộ ắ ộ
4) Các ch ng trình máy tính có th thi hành nhanh h n b ng cách thi hành đ ng th iươ ể ơ ằ ồ ờ
m t s câu l nh nào đó. Đi u quan tr ng là không đ c th c hi n m t câu l nh đòiộ ố ệ ề ọ ượ ự ệ ộ ệ
h i k t qu c a câu l nh khác ch a đ c th c hi n. S ph thu c c a các câu l nhỏ ế ả ủ ệ ư ượ ự ệ ự ụ ộ ủ ệ
vào các câu l nh tr c có th bi u di n b ng m t đ th có h ng. M i câu l nhệ ướ ể ể ễ ằ ộ ồ ị ướ ỗ ệ
đ c bi u di n b ng m t đ nh và có m t cung t m t đ nh t i m t đ nh khác n u câuượ ể ễ ằ ộ ỉ ộ ừ ộ ỉ ớ ộ ỉ ế
l nh đ c bi u di n b ng đ nh th hai không th th c hi n đ c tr c khi câu l nhệ ượ ể ễ ằ ỉ ứ ể ự ệ ượ ướ ệ
đ c bi u di n b ng đ nh th nh t đ c th c hi n. Đ th này đ c g i làượ ể ễ ằ ỉ ứ ấ ượ ự ệ ồ ị ượ ọ đ th cóồ ị
u tiên tr c sauư ướ .
3.2. B C C A Đ NH.Ậ Ủ Ỉ
3.2.1. Đ nh nghĩa: ị 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.ủ ạ
3.2.2. Đ nh nghĩa:ị 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ó, riêng 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.ỉ ọ ỉ ế ọ ỉ ậ ế
Thí d 4: ụ
39

4
là đ nh cô l p và đ nh vỉ ậ ỉ
6
là đ nh treo.ỉ
3.2.3. M nh đ :ệ ề Cho đ th G = (V, E). Khi đó ồ ị
2|E| =
∑
∈Vv
v)deg(
.
Ch ng minh:ứ Rõ ràng 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). T đó suy ra t ng t t c các b c c a các đ nh b ng hai l n s c nh.ừ ổ ấ ả ậ ủ ỉ ằ ầ ố ạ
3.2.4. H qu :ệ ả S đ nh b c l c a m t đ th là m t s ch n.ố ỉ ậ ẻ ủ ộ ồ ị ộ ố ẵ
Ch ng minh:ứ G i Vọ
1
và V
2
t ng ng là t p các đ nh b c ch n và t p các đ nh b c lươ ứ ậ ỉ ậ ẵ ậ ỉ ậ ẻ
c a đ th G = (V, E). Khi đóủ ồ ị
2|E| =
∑
∈
1
)deg(
Vv
v
+
∑
∈
2

1
) = 3,
deg
t
(v
2
) = 5, deg
o
(v
2
) = 1,
deg
t
(v
3
) = 2, deg
o
(v
3
) = 4,
deg
t
(v
4
) = 1, deg
0
(v
4
) = 3,
deg

v
6
3.2.8. M nh đ : ệ ề Cho G =(V, E) là m t đ th có h ng. Khi đó ộ ồ ị ướ
∑ ∑
∈ ∈
=
Vv Vv
ot
vv )(deg)(deg
= |E|.
Ch ng minh:ứ K t qu có ngay là vì m i cung đ c tính m t l n cho đ nh đ u và m tế ả ỗ ượ ộ ầ ỉ ầ ộ
l n cho đ nh cu i.ầ ỉ ố
3.3. NH NG Đ N Đ TH Đ C BI T.Ữ Ơ Ồ Ị Ặ Ệ
3.3.1. Đ th đ y đ :ồ ị ầ ủ Đ th đ y đ n đ nh, ký hi u là Kồ ị ầ ủ ỉ ệ
n
, là đ n đ th mà hai đ nhơ ồ ị ỉ
phân bi t b t kỳ c a nó luôn li n k . Nh v y, Kệ ấ ủ ề ề ư ậ
n
có
2
)1( −nn
c nh và m i đ nh c aạ ỗ ỉ ủ
K
n
có b c là nậ −1.
Thí d 6:ụ

K
1
K

) đ c g i là đ th vòng, ký hi u là Cượ ọ ồ ị ệ
n
. Nh v y, m i đ nh c a Cư ậ ỗ ỉ ủ
n
có
b c là 2.ậ
Thí d 7:ụ
C
3
C
4
C
5
C
6
3.3.3. Đ th bánh xe:ồ ị T đ th vòng Cừ ồ ị
n
, thêm vào đ nh vỉ
n+1
và các c nh (vạ
n+1
,v
1
),
(v
n+1
,v
2
), , (v
n+1

v
1
v
2
v
3
v
1
v
2
v
3
v
4
v
5
v
1
v
2
v
1
v
3
V
4
v
1
v
2

v
4
v
2
v
3
v
1
v
2
v
4
v
3
v
1
v
5
v
2
v
4
v
3
v
6
v
5
v
2

Thí d 9:ụ
Q
1
Q
2

Q
3
3.3.5. Đ th phân đôi (đ th hai phe):ồ ị ồ ị Đ n đ th G=(V,E) sao cho V=Vơ ồ ị
1
∪V
2
,
V
1
∩V
2
=∅, V
1
≠∅ , V
2
≠∅ và m i c nh c a G đ c n i m t đ nh trong Vỗ ạ ủ ượ ố ộ ỉ
1
và m t đ nhộ ỉ
trong V
2
đ c g i là đ th phân đôi.ượ ọ ồ ị
N u đ th phân đôi G=(Vế ồ ị
1
∪V

K
2,4
K
3,3

3.3.6. M t vài ng d ng c a các đ th đ c bi t:ộ ứ ụ ủ ồ ị ặ ệ
1) Các m ng c c b (LAN):ạ ụ ộ M t s m ng c c b dùng c u trúc hình sao, trong đó t tộ ố ạ ụ ộ ấ ấ
c các thi t b đ c n i v i thi t b đi u khi n trung tâm. M ng c c b ki u này cóả ế ị ượ ố ớ ế ị ề ể ạ ụ ộ ể
th bi u di n b ng m t đ th phân đôi đ y đ Kể ể ễ ằ ộ ồ ị ầ ủ
1,n
. Các thông báo g i t thi t b nàyử ừ ế ị
t i thi t b khác đ u ph i qua thi t b đi u khi n trung tâm.ớ ế ị ề ả ế ị ề ể
M ng c c b cũng có th có c u trúc vòng tròn, trong đó m i thi t b n i v iạ ụ ộ ể ấ ỗ ế ị ố ớ
đúng hai thi t b khác. M ng c c b ki u này có th bi u di n b ng m t đ th vòngế ị ạ ụ ộ ể ể ể ễ ằ ộ ồ ị
C
n
. Thông báo g i t thi t b này t i thi t b khác đ c truy n đi theo vòng tròn cho t iử ừ ế ị ớ ế ị ượ ề ớ
khi đ n n i nh n.ế ơ ậ
42
0
1
10
11
01
00
000
100
010
001
011

3
v
4
v
5
v
1
v
6
v
7
v
8
v
9
v
1
v
2
v
8
v
7
v
6
v
5
v
4
v

không th gi i trong kho ng th i gian h p lý b ng các thao tác n i ti p. Vì v y, ng iể ả ả ờ ợ ằ ố ế ậ ườ
ta ph i nghĩ đ n ki u x lý song song.ả ế ể ử
Khi x lý song song, ng i ta dùng các máy tính có nhi u b x lý riêng bi t,ử ườ ề ộ ử ệ
m i b x lý có b nh riêng, nh đó có th kh c ph c đ c nh ng h n ch c a cácỗ ộ ử ộ ớ ờ ể ắ ụ ượ ữ ạ ế ủ
máy n i ti p. Các thu t toán song song phân chia bài toán chính thành m t s bài toánố ế ậ ộ ố
con sao cho có th gi i đ ng th i đ c. Do v y, b ng các thu t toán song song và nhể ả ồ ờ ượ ậ ằ ậ ờ
vi c s d ng các máy tính có b đa x lý, ng i ta hy v ng có th gi i nhanh các bàiệ ử ụ ộ ử ườ ọ ể ả
toán ph c t p. Trong thu t toán song song có m t dãy các ch th theo dõi vi c th cứ ạ ậ ộ ỉ ị ệ ự
hi n thu t toán, g i các bài toán con t i các b x lý khác nhau, chuy n các thông tinệ ậ ử ớ ộ ử ể
vào, thông tin ra t i các b x lý thích h p.ớ ộ ử ợ
Khi dùng cách x lý song song, m i b x lý có th c n các thông tin ra c a cácử ỗ ộ ử ể ầ ủ
b x lý khác. Do đó chúng c n ph i đ c k t n i v i nhau. Ng i ta có th dùng lo iộ ử ầ ả ượ ế ố ớ ườ ể ạ
đ th thích h p đ bi u di n m ng k t n i các b x lý trong m t máy tính có nhi uồ ị ợ ể ể ễ ạ ế ố ộ ử ộ ề
b x lý. Ki u m ng k t n i dùng đ th c hi n m t thu t toán song song c th phộ ử ể ạ ế ố ể ự ệ ộ ậ ụ ể ụ
thu c vào nh ng yêu c u v i vi c trao đ i d li u gi a các b x lý, ph thu c vàoộ ữ ầ ớ ệ ổ ữ ệ ữ ộ ử ụ ộ
t c đ mong mu n và t t nhiên vào ph n c ng hi n có.ố ộ ố ấ ầ ứ ệ
M ng k t n i các b x lý đ n gi n nh t và cũng đ t nh t là có các liên k t haiạ ế ố ộ ử ơ ả ấ ắ ấ ế
chi u gi a m i c p b x lý. Các m ng này có th mô hình b ng đ th đ y đ Kề ữ ỗ ặ ộ ử ạ ể ằ ồ ị ầ ủ
n
,
trong đó n là s b x lý. Tuy nhiên, các m ng liên k t ki u này có s k t n i quáố ộ ử ạ ế ể ố ế ố
nhi u mà trong th c t s k t n i c n ph i có gi i h n.ề ự ế ố ế ố ầ ả ớ ạ
Các b x lý có th k t n i đ n gi n là s p x p chúng theo m t m ng m tộ ử ể ế ố ơ ả ắ ế ộ ả ộ
chi u. u đi m c a m ng m t chi u là m i b x lý có nhi u nh t 2 đ ng n i tr cề Ư ể ủ ả ộ ề ỗ ộ ử ề ấ ườ ố ự
ti p v i các b x lý khác. Nh c đi m là nhi u khi c n có r t nhi u các k t n iế ớ ộ ử ượ ể ề ầ ấ ề ế ố
trung gian đ các b x lý trao đ i thông tin v i nhau.ể ộ ử ổ ớ
43
v
7
P

m
bộ
x lý.ử
3.4. BI U DI N Đ TH B NG MA TR N VÀ S Đ NG C U Đ TH :Ể Ễ Ồ Ị Ằ Ậ Ự Ẳ Ấ Ồ Ị
3.4.1. Đ nh nghĩa:ị Cho đ th G=(V,E) (vô h ng ho c có h ng), v i V={vồ ị ướ ặ ướ ớ
1
,v
2
, ,
v
n
}. Ma tr n li n k c a G ng v i th t các đ nh vậ ề ề ủ ứ ớ ứ ự ỉ
1
,v
2
, , v
n
là ma tr nậ
A=
),()(
,1
ZnMa
njiij
∈
≤≤
,
trong đó a
ij
là s c nh ho c cung n i t vố ạ ặ ố ừ
i

P(0,2)
P(0,3)
P(1,0)
P(1,1)
P(1,2)
P(1,3)
P(2,0)
P(2,1)
P(2,2)
P(2,3)
P(3,0)
P(3,1)
P(3,2)
P(3,3)
P
1
P
2
P
3
P
4
P
5
P
6
P
0
P
7

, v
2
, v
3
, v
4
, v
5
là:

















01011
10200
01001
01210

n i v i đ nh vố ớ ỉ
i
và b ng 0 n u c nh eằ ế ạ
j
không n i v i đ nh vố ớ ỉ
i
.
Thí d 12:ụ Ma tr n liên thu c theo th t các đ nh vậ ộ ứ ự ỉ
1
, v
2
, v
3
, v
4
, v
5
và các c nh eạ
1
, e
2
, e
3
,
e
4
, e
5
, e
6

2
=(V
2
,E
2
) đ c g i là đ ng c uượ ọ ẳ ấ
n u t n t i m t song ánh f t Vế ồ ạ ộ ừ
1
lên V
2
sao cho các đ nh u và v là li n k trong Gỉ ề ề
1
khi
và ch khi f(u) và f(v) là li n k trong Gỉ ề ề
2
v i m i u và v trong Vớ ọ
1
. Ánh x f nh th g iạ ư ế ọ
là m t phép đ ng c u.ộ ẳ ấ
Thông th ng, đ ch ng t hai đ n đ th là không đ ng c u, ng i ta ch raườ ể ứ ỏ ơ ồ ị ẳ ấ ườ ỉ
chúng không có chung m t tính ch t mà các đ n đ th đ ng c u c n ph i có. Tínhộ ấ ơ ồ ị ẳ ấ ầ ả
ch t nh th g i là m t b t bi n đ i v i phép đ ng c u c a các đ n đ th .ấ ư ế ọ ộ ấ ế ố ớ ẳ ấ ủ ơ ồ ị
Thí d 13:ụ 1) Hai đ n đ th Gơ ồ ị
1
và G
2
sau là đ ng c u qua phép đ ng c u f: aẳ ấ ẳ ấ
ấ
x, b
x

e
2
e
3
e
4
e
5
e
6
a
b
c
e
d
u
v
z
G
1
G
2
2) Hai đ th Gồ ị
1
và G
2
sau đ u có 5 đ nh và 6 c nh nh ng không đ ng c u vì trong Gề ỉ ạ ư ẳ ấ
1
có m t đ nh b c 4 mà trong Gộ ỉ ậ
2

theo th t cácứ ự
đ nh uỉ
1
, u
2
, u
3
, u
4
, u
5
, u
6
và c a Gủ
2
theo th t các đ nh vứ ự ỉ
6
, v
3
, v
4
, v
5
, v
1
, v
2
là nh nhau vàư
b ng:ằ


c
b
g
e
h
u
v
x
y
w
t
z
u
1
v
3
v
1
u
2
u
4
u
6
u
5
u
3
v
6

⊂ E
1
. Trong tr ng h p Vườ ợ
1
=V
2
thì G
2
g i là con bao trùm c aọ ủ
G
1
.
Thí d 14:ụ
G G
1
G
2
G
3
G
4
G
5

G
1
, G
2
, G
3

2
, ký hi u là Gệ
1
∪ G
2
.
Thí d 15:ụ
G
1
G
2
G
1
∪G
2
3.5.3. Đ nh nghĩa:ị Đ n đ th G’=(V,E’) đ c g i là đ th bù c a đ n đ thơ ồ ị ượ ọ ồ ị ủ ơ ồ ị
G=(V,E) n u G và G’ không có c nh chung nào (E ế ạ ∩ E’=∅) và G ∪ G’là đ th đ y đ .ồ ị ầ ủ
D th y r ng n u G’ là bù c a G thì G cũng là bù c a G’. Khi đó ta nói hai đễ ấ ằ ế ủ ủ ồ
th là bù nhau.ị
Thí d 16:ụ
G’ G G
1
’ G
1
Hai đ th G’ và G là bù nhau và hai đ th Gồ ị ồ ị
1
và G
1
’ là bù nhau.
3.6. TÍNH LIÊN THÔNG.

u
v
u
x
y
z
w
x
y
z
u
v
w
x
y
u
v
x
u
y
v
x
v
y
u
z
x
v
u
z

=u và x
n
=v. Khi đ th không có c nh (ho c cung) b i, ta ký hi u đ ng đi nàyồ ị ạ ặ ộ ệ ườ
b ng dãy các đ nh xằ ỉ
0
, x
1
, , x
n
. Đ ng đi đ c g i là chu trình n u nó b t đ u và k tườ ượ ọ ế ắ ầ ế
thúc t i cùng m t đ nh. Đ ng đi ho c chu trình g i là đ n n u nó không ch a cùngạ ộ ỉ ườ ặ ọ ơ ế ứ
m t c nh (ho c cung) quá m t l n. M t đ ng đi ho c chu trình không đi qua đ nh nàoộ ạ ặ ộ ầ ộ ườ ặ ỉ
quá m t l n (tr đ nh đ u và đ nh cu i c a chu trình là trùng nhau) đ c g i là đ ngộ ầ ừ ỉ ầ ỉ ố ủ ượ ọ ườ
đi ho c chu trình s c p. Rõ ràng r ng m t đ ng đi (t. . chu trình) s c p là đ ng điặ ơ ấ ằ ộ ườ ư ơ ấ ườ
(t. . chu trình) đ n.ư ơ
Thí d 17:ụ
Trong đ n đ th trên, x, y, z, w, v, y là đ ng đi đ n (không s c p) đ dài 5; x,ơ ồ ị ườ ơ ơ ấ ộ
w, v, z, y không là đ ng đi vì (v, z) không là c nh; y, z, w, x, v, u, y là chu trình s c pườ ạ ơ ấ
đ dài 6.ộ
3.6.2. Đ nh nghĩa:ị M t đ th (vô h ng) đ c g i là liên thông n u có đ ng điộ ồ ị ướ ượ ọ ế ườ
gi a m i c p đ nh phân bi t c a đ th .ữ ọ ặ ỉ ệ ủ ồ ị
M t đ th không liên thông là h p c a hai hay nhi u đ th con liên thông, m iộ ồ ị ợ ủ ề ồ ị ỗ
c p các đ th con này không có đ nh chung. Các đ th con liên thông r i nhau nh v yặ ồ ị ỉ ồ ị ờ ư ậ
đ c g i là các thành ph n liên thông c a đ th đang xét. Nh v y, m t đ th là liênượ ọ ầ ủ ồ ị ư ậ ộ ồ ị
thông khi và ch khi nó ch có m t thành ph n liên thông.ỉ ỉ ộ ầ
Thí d 18:ụ
G G’
Đ th G là liên thông, nh ng đ th G’ không liên thông và có 3 thành ph n liên thông.ồ ị ư ồ ị ầ
3.6.3. Đ nh nghĩa:ị M t đ nh trong đ th G mà khi xoá đi nó và t t c các c nh liênộ ỉ ồ ị ấ ả ạ
thu c v i nó ta nh n đ c đ th con m i có nhi u thành ph n liên thông h n đ th Gộ ớ ậ ượ ồ ị ớ ề ầ ơ ồ ị

đ ng đi s c p.ườ ơ ấ
Ch ng minh:ứ Gi s u và v là hai đ nh phân bi t c a m t đ th liên thông G. Vì G liênả ử ỉ ệ ủ ộ ồ ị
thông nên có ít nh t m t đ ng đi gi a u và v. G i xấ ộ ườ ữ ọ
0
, x
1
, , x
n
, v i xớ
0
=u và x
n
=v, là dãy
các đ nh c a đ ng đi có đ dài ng n nh t. Đây chính là đ ng đi s c p c n tìm.ỉ ủ ườ ộ ắ ấ ườ ơ ấ ầ
Th t v y, gi s nó không là đ ng đi đ n, khi đó xậ ậ ả ử ườ ơ
i
=x
j
v i 0 ớ ≤ i < j. Đi u này cóề
nghĩa là gi a các đ nh u và v có đ ng đi ng n h n qua các đ nh xữ ỉ ườ ắ ơ ỉ
0
, x
1
, , x
i-1
, x
j
, , x
n
nh n đ c b ng cách xoá đi các c nh t ng ng v i dãy các đ nh xậ ượ ằ ạ ươ ứ ớ ỉ

− 1) = n
1
+n
2
−2 ≤ n−2 <n.
Đi u mâu thu n trên d n đ n k t lu n là đ th G ph i liên thông.ề ẫ ở ẫ ế ế ậ ồ ị ả
3.6.6. H qu : ệ ả Đ n đ th mà b c c a m i đ nh c a nó không nh h n m t n a sơ ồ ị ậ ủ ỗ ỉ ủ ỏ ơ ộ ử ố
đ nh là đ th liên thông.ỉ ồ ị
3.6.7. M nh đ :ệ ề N u m t đ th có đúng hai đ nh b c l thì hai đ nh này ph i liênế ộ ồ ị ỉ ậ ẻ ỉ ả
thông, t c là có m t đ ng đi n i chúng.ứ ộ ườ ố
Ch ng minh:ứ Cho G=(V,E) là đ th th có đúng hai đ nh b c l là u và v. Gi s u vàồ ị ị ỉ ậ ẻ ả ử
v không liên thông v i nhau. Khi đó chúng ph i thu c hai thành ph n liên thông nào đóớ ả ộ ầ
c a đ th G, Gủ ồ ị
1
ch a u và Gứ
2
ch a v.ứ
B c c a đ nh u trong Gậ ủ ỉ
1
cũng chính là b c c a u trong G, nên trong Gậ ủ
1
đ nh uỉ
v n có b c l và Gẫ ậ ẻ
1
có duy nh t m t đ nh b c l . Đi u này mâu thu n. V y hai đ nh uấ ộ ỉ ậ ẻ ề ẫ ậ ỉ
và v ph i liên thông.ả
3.6.8. M nh đ :ệ ề Cho G=(V,E) là m t đ th liên thông. Khi đó m t đ nh c a G làộ ồ ị ộ ỉ ủ
đi m kh p khi và ch khi trong G t n t i hai đ nh u và v sao cho m i đ ng đi n i u vàể ớ ỉ ồ ạ ỉ ỗ ườ ố
v đ u ph i đi qua đ nh này.ề ả ỉ
49

nh n đ c t G ch a hai đ nh u, v khôngậ ượ ừ ứ ỉ
liên thông. Do đó G
1
là đ th không liên thông hay đ nh x là đi m kh p c a G.ồ ị ỉ ể ớ ủ
3.6.9. Đ nh lý:ị Cho G là m t đ n đ th có n đ nh, m c nh và k thành ph n liên thông.ộ ơ ồ ị ỉ ạ ầ
Khi đó
2
)1)(( +−−
≤≤−
knkn
mkn
.
Ch ng minh:ứ B t đ ng th c ấ ẳ ứ
mkn ≤−
đ c ch ng minh b ng quy n p theo m. N uượ ứ ằ ạ ế
m=0 thì k=n nên b t đ ng th c đúng. Gi s b t đ ng th c đúng đ n mấ ẳ ứ ả ử ấ ẳ ứ ế −1, v i m ớ ≥ 1.
G i G’ là đ th con bao trùm c a G có s c nh mọ ồ ị ủ ố ạ
0
là nh nh t sao cho nó có k thànhỏ ấ
ph n liên thông. Do đó vi c lo i b b t c c nh nào trong G’ cũng tăng s thành ph nầ ệ ạ ỏ ấ ứ ạ ố ầ
liên thông lên 1 và khi đó đ th thu đ c s có n đ nh, k+1 thành ph n liên thông vàồ ị ượ ẽ ỉ ầ
m
0
−1 c nh. Theo gi thi t quy n p, ta có mạ ả ế ạ
0
−1 ≥ n−(k+1) hay m
0
≥ n−k. V y m ậ ≥ n-k.
B sung c nh vào G đ nh n đ c đ th G’’ có mổ ạ ể ậ ượ ồ ị
1

j
−1 đ nh thì t ng s đ nh khôngỉ ổ ố ỉ
thay đ i nh ng s c nh tăng thêm m t l ng là:ổ ư ố ạ ộ ượ
1
2
)2)(1(
2
)1(
2
)1(
2
)1(
+−=






−−
−
−
−






−

, , v
n
. Khi đó s các đ ng đi khác nhau đ dài r t vố ườ ộ ừ
i
t i vớ
j
trong đó r là m t s nguyên d ng, b ng giá tr c a ph n t dòng i c t j c a maộ ố ươ ằ ị ủ ầ ử ộ ủ
tr n Aậ
r
.
Ch ng minh:ứ Ta ch ng minh m nh đ b ng quy n p theo r. S các đ ng đi khácứ ệ ề ằ ạ ố ườ
nhau đ dài 1 t vộ ừ
i
t i vớ
j
là s các c nh (ho c cung) t vố ạ ặ ừ i t i vớ
j
, đó chính là ph n tầ ử
dòng i c t j c a ma tr n A; nghĩa là, m nh đ đúng khi r=1.ộ ủ ậ ệ ề
Gi s m nh đ đúng đ n r; nghĩa là, ph n t dòng i c t j c a Aả ử ệ ề ế ầ ử ộ ủ
r
là s cácố
đ ng đi khác nhau đ dài r t vườ ộ ừ
i
t i vớ
j
. Vì A
r+1
=A
r

t i vớ
j
s đ c t o nên t đ ng đi đ dài r t vẽ ượ ạ ừ ườ ộ ừ
i
t iớ
đ nh trung gian vỉ
k
nào đó và m t c nh (ho c cung) t vộ ạ ặ ừ
k
t i vớ
j
. Theo quy t c nhân s cácắ ố
đ ng đi nh th là tích c a s đ ng đi đ dài r t vườ ư ế ủ ố ườ ộ ừ
i
t i vớ
k
, t c là bứ
ik
, và s các c nhố ạ
(ho c cung) t vặ ừ
k
t i vớ
j
, t c là aứ
kj
. C ng các tích này l i theo t t c các đ nh trung gianộ ạ ấ ả ỉ
v
k
ta có m nh đ đúng đ n r+1.ệ ề ế
BÀI T P CH NG III:Ậ ƯƠ

ph ng án này.ươ
4. Hãy v các đ th vô h ng đ c bi u di n b i ma tr n li n k sau:ẽ ồ ị ướ ượ ể ễ ở ậ ề ề
a)
1 2 3
2 0 4
3 4 0










, b)
1 2 0 1
2 0 3 0
0 3 1 1
1 0 1 0










n
, b) C
n
, c) W
n
, d) K
m,n
, e) Q
n
.
7. Có bao nhiêu đ n đ th không đ ng c u v i n đ nh khi:ơ ồ ị ẳ ấ ớ ỉ
a) n=2, b) n=3, c) n=4.
8. Hai đ n đ th v i ma tr n li n k sau đây có là đ ng c u không?ơ ồ ị ớ ậ ề ề ẳ ấ














0111
1000
1001







01110
11000
10101
00011
,














10101
01001
01110
10010
.

u
2
u
3
u
4
u
5
v
1
v
2
v
6
v
3
v
5
v
4
11. Cho V={2,3,4,5,6,7,8} và E là t p h p các c p ph n t (u,v) c a V sao cho u<v vàậ ợ ặ ầ ử ủ
u,v nguyên t cùng nhau. Hãy v đ th có h ng G=(V,E). Tìm s các đ ng đi phânố ẽ ồ ị ướ ố ườ
bi t đ dài 3 t đ nh 2 t i đ nh 8.ệ ộ ừ ỉ ớ ỉ
12. Hãy tìm s đ ng đi đ dài n gi a hai đ nh li n k (t. . không li n k ) tùy ý trongố ườ ộ ữ ỉ ề ề ư ề ề
K
3,3
v i m i giá tr c a n sau:ớ ỗ ị ủ
a) n=2, b) n=3, c) n=4, d) n=5.
14. M t cu c h p có ít nh t ba đ i bi u đ n d . M i ng i quen ít nh t hai đ i bi uộ ộ ọ ấ ạ ể ế ự ỗ ườ ấ ạ ể
khác. Ch ng minh r ng có th x p đ c m t s đ i bi u ng i xung quanh m t bànứ ằ ể ế ượ ộ ố ạ ể ồ ộ