[Giáo trình Toán rời rạc] - Chương3 - Đồ thị

Chia sẻ: trungtran5

Tài liệu " [Giáo trình Toán rời rạc] - Chương3 - Đồ thị " mang tính chất tham khảo, giúp ích cho các bạn tự học, ôn thi, với phương pháp học hay, thú vị, rèn luyện kỹ năng giải đề, nâng cao vốn kiến thức cho các bạn trong các kỳ thi sắp tới. Tác giả hy vọng tài liệu này sẽ giúp ích cho các bạn.

Bạn đang xem 7 trang mẫu tài liệu này, vui lòng download file gốc để xem toàn bộ.

Nội dung Text: [Giáo trình Toán rời rạc] - Chương3 - Đồ thị

http://ebook.here.vn T i mi n phí ð thi, eBook, Tài li u h c t p
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 cong) hay nh ng
mũi tên, tư ng trưng cho m t quan h nào ñó gi a các ñ i tư ng. ðó là nh ng thí d v
ñ th .
3.1.1. ð nh nghĩa: M t ñơn ñ th G = (V, E) g m m t t p khác r ng V mà các ph n
t c a nó g i là các ñ nh và m t t p E mà các ph n t c a nó g i là các c nh, ñó là các
c p không có th t c a các ñ nh phân bi t.

37
http://ebook.here.vn T i mi n phí ð thi, eBook, Tài li u h c t p

3.1.2. ð nh nghĩa: M t ña ñ th G = (V, E) g m m t t p khác r ng V mà các ph n t
c a nó g i là các ñ nh và m t h E mà các ph n t c a nó g i là các c nh, ñó là các c p
không có th t c a các ñ nh phân bi t. Hai c nh ñư c g i là c nh b i hay song song
n u chúng cùng tương ng v i m t c p ñ nh.
Rõ ràng m i ñơn ñ th là ña ñ th , nhưng không ph i ña ñ th nào cũng là ñơn
ñ th .
3.1.3. ð nh nghĩa: M t gi ñ th G = (V, E) g m m t t p khác r ng V mà các ph n t
c a nó g i là các ñ nh và m t h E mà các ph n t c a nó g i là các c nh, ñó là các c p
không có th t c a các ñ nh (không nh t thi t là phân bi t).
V i v∈V, n u (v,v)∈E thì ta nói có m t khuyên t i ñ nh v.
Tóm l i, gi ñ th là lo i ñ th vô hư ng t ng quát nh t vì nó có th ch a các
khuyên và các c nh b i. ða ñ th là lo i ñ th vô hư ng có th ch a c nh b i nhưng
không th có các khuyên, còn ñơn ñ th là lo i ñ th vô hư ng không ch a c nh b i
ho c các khuyên.
Thí d 1:
v1 v2 v3 v4 v1 v2 v3



v5 v6 v7 v4 v5 v6

ðơn ñ th
Gi ñ th
3.1.4. ð nh nghĩa: M t ñ th có hư ng G = (V, E) g m m t t p khác r ng V mà các
ph n t c a nó g i là các ñ nh và m t t p E mà các ph n t c a nó g i là các cung, ñó là
các c p có th t c a các ph n t thu c V.
3.1.5. ð nh nghĩa: M t ña ñ th có hư ng G = (V, E) g m m t t p khác r ng V mà
các ph n t c a nó g i là các ñ nh và m t h E mà các ph n t c a nó g i là các cung,
ñó là các c p có th t c a các ph n t thu c V.
ð 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:
v1 v2 v3 v5 v1 v2 v3



V5 v6 v7 v4 v5 v6

ð th có hư ng ða ñ th có hư ng

38
http://ebook.here.vn T i mi n phí ð thi, eBook, Tài li u h c t p

Thí d 3: 1) ð th “l n t ” trong sinh thái h c. ð th ñư c dùng trong nhi u mô
hình có tính ñ n s tương tác c a các loài v t. Ch ng h n s c nh tranh c a các loài
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:
v1 v2 v3

v4


v5 v6 v7
Ta có deg(v1)=7, deg(v2)=5, deg(v3)=3, deg(v4)=0, deg(v5)=4, deg(v6)=1, deg(v7)=2.
ð nh v4 là ñ nh cô l p và ñ nh v6 là ñ nh treo.

39
http://ebook.here.vn T i mi n phí ð thi, eBook, Tài li u h c t p

3.2.3. M nh ñ : Cho ñ th G = (V, E). Khi ñó
2|E| = ∑ deg(v) .
v∈V
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 V1 và V2 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| = ∑ deg(v) + ∑ deg(v)
v∈V1 v∈V2
V trái là m t s ch n và t ng th nh t cũng là m t s ch n nên t ng th hai là m t s
ch n. Vì deg(v) là l v i m i v ∈ V2 nên |V2| là m t s ch n.
3.2.5. M nh ñ : Trong m t ñơn ñ th , luôn t n t i hai ñ nh có cùng b c.
Ch ng minh: Xét ñơn ñ th G=(V,E) có |V|=n. Khi ñó phát bi u trên ñư c ñưa v bài
toán: trong m t phòng h p có n ngư i, bao gi cũng tìm ñư c 2 ngư i có s ngư i quen
trong s nh ng ngư i d h p là như nhau (xem Thí d 6 c a 2.2.3).
3.2.6. ð nh nghĩa: ð nh u ñư c g i là n i t i v hay v ñư c g i là ñư c n i t u trong
ñ th có hư ng G n u (u,v) là m t cung c a G. ð nh u g i là ñ nh ñ u và ñ nh v g i là
ñ nh cu i c a cung này.
3.2.7. ð nh nghĩa: B c vào (t.ư. b c ra) c a ñ nh v trong ñ th có hư ng G, ký hi u
degt(v) (t.ư. dego(v)), là s các cung có ñ nh cu i là v.
Thí d 5:
v2 v3
v1


v4 v5 v6

degt(v1) = 2, dego(v1) = 3,
degt(v2) = 5, dego(v2) = 1,
degt(v3) = 2, dego(v3) = 4,
degt(v4) = 1, deg0(v4) = 3,
degt(v5) = 1, dego(v5) = 0,
degt(v6) = 0, dego(v6) = 0.
ð nh có b c vào và b c ra cùng b ng 0 g i là ñ nh cô l p. ð nh có b c vào b ng 1
và b c ra b ng 0 g i là ñ nh treo, cung có ñ nh cu i là ñ nh treo g i là cung treo.
3.2.8. M nh ñ : Cho G =(V, E) là m t ñ th có hư ng. Khi ñó


40
http://ebook.here.vn T i mi n phí ð thi, eBook, Tài li u h c t p

∑ deg t (v) = ∑ deg o (v) = |E|.
v∈V v∈V
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à Kn, là ñơn ñ th mà hai ñ nh
n(n − 1)
phân bi t b t kỳ c a nó luôn li n k . Như v y, Kn có c nh và m i ñ nh c a Kn
2
có b c là n−1. v1 v2
v1 v1
Thí d 6:

v1 v1 v2 v4 v3 v5 v2
v3 v2
K1 K2
K3 K4 V4 v3
K5
3.3.2. ð th vòng: ðơn ñ th n ñ nh v1, v2, ..., vn (n≥3) và n c nh (v1,v2), (v2,v3), ...,
(vn-1,vn), (vn,v1) ñư c g i là ñ th vòng, ký hi u là Cn. Như v y, m i ñ nh c a Cn có b c
là 2. v1 v1
Thí d 7: v1 v1 v2 v6 v2
v5 v2

v5 v3
v3 v2 v4 v3 v4 v3
v4
C3 C4 C5 C6
3.3.3. ð th bánh xe:T ñ th vòng Cn, thêm vào ñ nh vn+1 và các c nh (vn+1,v1),
(vn+1,v2), ..., (vn+1,vn), ta nh n ñư c ñơn ñ th g i là ñ th bánh xe, ký hi u là Wn. Như
v y, ñ th Wn có n+1 ñ nh, 2n c nh, m t ñ nh b c n và n ñ nh b c 3.
v1 v1
Thí d 8: v1 v1 v2 v6 v2
v5 v2
v6 v7
v5
v4 v5 v3
v3 v2 v4 v3 v4 v3
v4
W3 W4 W5 W6

3.3.4. ð th l p phương: ðơn ñ th 2n ñ nh, tương ng v i 2n xâu nh phân ñ dài n
và hai ñ nh k nhau khi và ch khi 2 xâu nh phân tương ng v i hai ñ nh này ch khác
nhau ñúng m t bit ñư c g i là ñ th l p phương, ký hi u là Qn. Như v y, m i ñ nh c a
Qn có b c là n và s c nh c a Qn là n.2 (t công th c 2|E| = ∑ deg(v) ).
n-1

v∈V


41
http://ebook.here.vn T i mi n phí ð thi, eBook, Tài li u h c t p
110
Thí d 9: 10 11 111

0 1 100 101

Q1 00 01
Q2 010 011
000 001

Q3
3.3.5. ð th phân ñôi (ñ th hai phe): ðơn ñ th G=(V,E) sao cho V=V1∪V2,
V1∩V2=∅, V1≠∅, V2≠∅ và m i c nh c a G ñư c n i m t ñ nh trong V1 và m t ñ nh
trong V2 ñư c g i là ñ th phân ñôi.
N u ñ th phân ñôi G=(V1∪V2,E) sao cho v i m i v1∈V1, v2∈V2, (v1,v2)∈E thì
G ñư c g i là ñ th phân ñôi ñ y ñ . N u |V1|=m, |V2|=n thì ñ th phân ñôi ñ y ñ G
ký hi u là Km,n. Như v y Km,n có m.n c nh, các ñ nh c a V1 có b c n và các ñ nh c a V2
có b c m.
Thí d 10:
v1 v2 v1 v2 v3



v3 v4 v5 v6 v4 v5 v6
K2,4 K3,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 ñ K1,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 Cn.
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.
v2 v3 v4 v1 v2 v2 v3
v8 v3 v9 v4
v5 v1 v6
v1
v7 v4 v8 v5
v7 v8 v9
v6 v5 v7 v6
C u trúc hình sao C u trúc vòng tròn C u trúc h n h p

42
http://ebook.here.vn T i mi n phí ð thi, eBook, Tài li u h c t p

Cu i cùng, m t s m ng c c b dùng c u trúc h n h p c a hai c u trúc trên. Các
thông báo ñư c truy n vòng quanh theo vòng tròn ho c có th qua thi t b trung tâm. S
dư th a này có th làm cho m ng ñáng tin c y hơn. M ng c c b ki u này có th bi u
di n b ng m t ñ th bánh xe Wn.
2) X lý song song: Các thu t toán ñ gi i các bài toán ñư c thi t k ñ th c hi n m t
phép toán t i m i th i ñi m là thu t toán n i ti p. Tuy nhiên, nhi u bài toán v i s
lư ng tính toán r t l n như bài toán mô ph ng th i ti t, t o hình trong y h c hay phân
tích m t mã không th gi i ñư c trong m t kho ng th i gian h p lý n u dùng thu t toán
n i ti p ngay c khi dùng các siêu máy tính. Ngoài ra, do nh ng gi i h n v m t v t lý
ñ i v i t c ñ th c hi n các phép toán cơ s , nên thư ng g p các bài toán 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 ñ Kn, 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.
P1 P2 P3 P4 P5 P6
M ng ki u lư i (ho c m ng hai chi u) r t hay ñư c dùng cho các m ng liên k t.
Trong m t m ng như th , s các b x lý là m t s chính phương, n=m2. Các b x lý

43
http://ebook.here.vn T i mi n phí ð thi, eBook, Tài li u h c t p

ñư c gán nhãn P(i,j), 0 ≤ i, j ≤ m−1. Các k t n i hai chi u s n i b x lý P(i,j) v i b n
b x lý bên c nh, t c là v i P(i,j±1) và P(i±1,j) ch ng nào các b x lý còn trong
lư i.
P(0,0) P(0,1) 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)


M ng k t n i quan tr ng nh t là m ng ki u siêu kh i. V i các m ng lo i này s
các b x lý là lu th a c a 2, n=2m. Các b x lý ñư c gán nhãn là P0, P1, ..., Pn-1. M i
b x lý có liên k t hai chi u v i m b x lý khác. B x lý Pi n i v i b x lý có ch s
bi u di n b ng dãy nh phân khác v i dãy nh phân bi u di n i t i ñúng m t bit. M ng
ki u siêu kh i cân b ng s các k t n i tr c ti p c a m i b x lý và s các k t n i gián
ti p sao cho các b x lý có th truy n thông ñư c. Nhi u máy tính ñã ch t o theo
m ng ki u siêu kh i và nhi u thu t toán ñã ñư c thi t k ñ s d ng m ng ki u siêu
kh i. ð th l p phương Qm bi u di n m ng ki u siêu kh i có 2m b x lý.
P0 P1 P2 P3 P4 P5 P6 P7



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={v1,v2,..., vn}.
Ma tr n li n k c a G ng v i th t các ñ nh v1,v2,..., vn là ma tr n
A= (aij )1≤i , j ≤n ∈ M (n, Z ) ,
trong ñó aij là s c nh ho c cung n i t vi t i vj.
Như v y, ma tr n li n k c a m t ñ th vô hư ng là ma tr n ñ i x ng, nghĩa là
aij = a ji , trong khi ma tr n li n k c a m t ñ th có hư ng không có tính ñ i x ng.
Thí d 11: Ma tr n li n k v i th t các ñ nh v1, v2, v3, v4 là:
v1 v2
0 3 0 2
 
3 0 1 1
0 1 1 2
  v4 v3
2 1 2 0
 


44
http://ebook.here.vn T i mi n phí ð thi, eBook, Tài li u h c t p
Ma tr n li n k v i th t các ñ nh v1, v2, v3, v4, v5 là:
1 1 0 1 1 v1
 
0 1 2 1 0
1 0 0 1 0 v5
  v2
0 0 2 0 1
1 1 0 1 0
 
v4 v3
3.4.2. ð nh nghĩa: Cho ñ th vô hư ng G=(V,E), v1, v2, ..., vn là các ñ nh và e1, e2, ...,
em là các c nh c a G. Ma tr n liên thu c c a G theo th t trên c a V và E là ma tr n
M= (mij )1≤i ≤n ∈ M (n × m, Z ) ,
1≤ j ≤m
mij b ng 1 n u c nh ej n i v i ñ nh vi và b ng 0 n u c nh ej không n i v i ñ nh vi.
Thí d 12: Ma tr n liên thu c theo th t các ñ nh v1, v2, v3, v4, v5 và các c nh e1, e2, e3,
e4, e5, e6 là: e6
v1 v2 v3
1 1 0 0 0 0 
  e3
e4
0 0 1 1 0 1  e1 e5
0 0 0 0 1 1 e2
  v4 v5
1 0 1 0 0 0 
0 1 0 1 1 0 
 
3.4.3. ð nh nghĩa: Các ñơn ñ th G1=(V1,E1) và G2=(V2,E2) ñư c g i là ñ ng c u n u
t n t i m t song ánh f t V1 lên V2 sao cho các ñ nh u và v là li n k trong G1 khi và ch
khi f(u) và f(v) là li n k trong G2 v i m i u và v trong V1. Á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 G1 và G2 sau là ñ ng c u qua phép ñ ng c u f: a a x,
b a u, c a z, d a v, e a y:
a u
z
v
b

c e
y
x
d


G1 G2
45
http://ebook.here.vn T i mi n phí ð thi, eBook, Tài li u h c t p

2) Hai ñ th G1 và G2 sau ñ u có 5 ñ nh và 6 c nh nhưng không ñ ng c u vì trong G1
có m t ñ nh b c 4 mà trong G2 không có ñ nh b c 4 nào.




3) Hai ñ th G1 và G2 sau ñ u có 7 ñ nh, 10 c nh, cùng có m t ñ nh b c 4, b n ñ nh
b c 3 và hai ñ nh b c 2. Tuy nhiên G1 và G2 là không ñ ng c u vì hai ñ nh b c 2 c a G1
(a và d) là không k nhau, trong khi hai ñ nh b c 2 c a G2 (y và z) là k nhau.
b c v x

a h d u w y


g e t z
G1 G2
4) Hãy xác ñ nh xem hai ñ th sau có ñ ng c u hay không?
u1 u2 v1 v3
v2
u5 u6
v6

u4 u3 v5 v4
G1 G2
Hai ñ th G1 và G2 là ñ ng c u vì hai ma tr n li n k c a G1 theo th t các ñ nh
u1, u2, u3, u4, u5, u6 và c a G2 theo th t các ñ nh v6, v3, v4, v5, v1, v2 là như nhau và
b ng:
 0 1 0 1 0 0
 
1 0 1 0 0 1 
 0 1 0 1 0 0
 
1 0 1 0 1 0 
 0 0 0 1 0 1
 
 0 1 0 0 1 0
 

3.5. CÁC ð TH M I T ð TH CŨ.
3.5.1. ð nh nghĩa: Cho hai ñ th G1=(V1,E1) và G2=(V2,E2). Ta nói G2 là ñ th con
c a G1 n u V2 ⊂ V1 và E2 ⊂ E1. Trong trư ng h p V1=V2 thì G2 g i là con bao trùm c a
G1 .

46
http://ebook.here.vn T i mi n phí ð thi, eBook, Tài li u h c t p

Thí d 14:
a d a a d a d
e e

b c b c b c b c
G G1 G2 G3
a d a d
e

b c b c
G4 G5
G1, G2, G3 và G4 là các ñ th con c a G, trong ñó G2 và G4 là ñ th con bao
trùm c a G, còn G5 không ph i là ñ th con c a G.
3.5.2. ð nh nghĩa: H p c a hai ñơn ñ th G1=(V1,E1) và G2=(V2,E2) là m t ñơn ñ th
có t p các ñ nh là V1 ∪ V2 và t p các c nh là E1 ∪ E2, ký hi u là G1 ∪ G2.
Thí d 15:

x y z x y z x y z



u v u w u v w
G1 G2 G1∪G2
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: x x
x y x y
v y v y


u v u v u z u z
G’ G G1 ’ G1
Hai ñ th G’ và G là bù nhau và hai ñ th G1 và G1’ là bù nhau.
3.6. TÍNH LIÊN THÔNG.
3.6.1. ð nh nghĩa: ðư ng ñi ñ dài n t ñ nh u ñ n ñ nh v, v i n là m t s nguyên
dương, trong ñ th (gi ñ th vô hư ng ho c ña ñ th có hư ng) G=(V,E) là m t dãy
các c nh (ho c cung) e1, e2, ..., en c a ñ th sao cho e1=(x0,x1),e2=(x1,x2), ...,en=(xn-1,xn),
v i x0=u và xn=v. Khi ñ th không có c nh (ho c cung) b i, ta ký hi u ñư ng ñi này

47
http://ebook.here.vn T i mi n phí ð thi, eBook, Tài li u h c t p

b ng dãy các ñ nh x0, x1, ..., xn. ðư 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:
x y z



w v u
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:
x y z a b g k

u

t v w d c h i l

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
ñư c g i là ñ nh c t hay ñi m kh p. Vi c xoá ñ nh c t kh i m t ñ th liên thông s t o
ra m t ñ th con không liên thông. Hoàn toàn tương t , m t c nh mà khi ta b nó ñi s
t o ra m t ñ th có nhi u thành ph n liên thông hơn so v i ñ th xu t phát ñư c g i là
c nh c t hay là c u.
Thí d 19: x y z u


v w s t

48
http://ebook.here.vn T i mi n phí ð thi, eBook, Tài li u h c t p

Trong ñ th trên, các ñ nh c t là v, w, s và các c u là (x,v), (w,s).
3.6.4. M nh ñ : Gi a m i c p ñ nh phân bi t c a m t ñ th liên thông luôn có ñư 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 x0, x1, ..., xn, v i x0=u và xn=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 ñó xi=xj 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 x0, x1, ..., xi-1, xj, ..., xn nh n
ñư c b ng cách xoá ñi các c nh tương ng v i dãy các ñ nh xi, ..., xj-1.
3.6.5. M nh ñ : M i ñơn ñ th n ñ nh (n ≥ 2) có t ng b c c a hai ñ nh tuỳ ý không
nh hơn n ñ u là ñ th liên thông.
Ch ng minh: Cho ñơn ñ th G=(V,E) có n ñ nh (n ≥ 2) và tho mãn yêu c u c a bài
toán. Gi s G không liên thông, t c là t n t i hai ñ nh u và v sao cho không có ñư ng
ñi nào n i u và v. Khi ñó trong ñ th G t n t i hai thành ph n liên thông là G1 có n1
ñ nh và ch a u, G2 ch a ñ nh v và có n2 ñ nh. Vì G1, G2 là hai trong s các thành ph n
liên thông c a G nên n1+n2 ≤ n. ta có:
deg(u)+deg(v) ≤ (n1 −1)+(n2 − 1) = n1+n2−2 ≤ n−2 1 (*).
N u ta thay Gi và Gj b ng ñ th ñ y ñ v i ni+1 và nj−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à:
 ( ni + 1)ni ni (ni − 1)   n j (n j − 1) (n j − 1)(n j − 2) 
 − − −  = ni − n j + 1 .
 2 2   2 2 
Th t c này ñư c l p l i khi hai thành ph n nào ñó có s ñ nh tho (*). Vì v y m1 là l n
nh t (n, k là c ñ nh) khi ñ th g m k-1 ñ nh cô l p và m t ñ th ñ y ñ v i n-k+1
ñ nh. T ñó suy ra b t ñ ng th c c n tìm.
3.6.10. ð nh nghĩa: ð th có hư ng G ñư c g i là liên thông m nh n u v i hai ñ nh
phân bi t b t kỳ u và v c a G ñ u có ñư ng ñi t u t i v và ñư ng ñi t v t i u.
ð th có hư ng G ñư c g i là liên thông y u n u ñ th vô hư ng n n c a nó là
liên thông.
ð th có hư ng G ñư c g i là liên thông m t chi u n u v i hai ñ nh phân bi t
b t kỳ u và v c a G ñ u có ñư ng ñi t u t i v ho c ñư ng ñi t v t i u.
Thí d 20:
u v w u v w

x x
y s t y s t
G G’

50
http://ebook.here.vn T i mi n phí ð thi, eBook, Tài li u h c t p

ð th G là liên thông m nh nhưng ñ th G’ là liên thông y u (không có ñư ng
ñi t u t i x cũng như t x t i u).
3.6.11. M nh ñ : Cho G là m t ñ th (vô hư ng ho c có hư ng) v i ma tr n li n k A
theo th t các ñ nh v1, v2, ..., vn. Khi ñó s các ñư ng ñi khác nhau ñ dài r t vi t i vj
r
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 .
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 vi t i vj là s các c nh (ho c cung) t vi t i vj, ñó 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.
r
Gi s m nh ñ ñúng ñ n r; nghĩa là, ph n t dòng i c t j c a A là s các ñư ng
ñi khác nhau ñ dài r t vi t i vj. Vì Ar+1=Ar.A nên ph n t dòng i c t j c a Ar+1 b ng
bi1a1j+bi2a2j+ ... +binanj,
trong ñó bik là ph n t dòng i c t k c a Ar. Theo gi thi t quy n p bik là s ñư ng ñi
khác nhau ñ dài r t vi t i vk.
ðư ng ñi ñ dài r+1 t vi t i vj s ñư c t o nên t ñư ng ñi ñ dài r t vi t i ñ nh
trung gian vk nào ñó và m t c nh (ho c cung) t vk t i vj. 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 vi t i vk, t c là bik, và s các c nh
(ho c cung) t vk t i vj, t c là akj. C ng các tích này l i theo t t c các ñ nh trung gian vk
ta có m nh ñ ñúng ñ n r+1.

BÀI T P CHƯƠNG III:

1. Cho G là ñ th có v ñ nh và e c nh, còn M, m tương ng là b c l n nh t và nh nh t
c a các ñ nh c a G. Ch ng t r ng
2e
m≤ ≤ M.
v
2. Ch ng minh r ng n u G là ñơn ñ th phân ñôi có v ñ nh và e c nh, khi ñó
e ≤ v2/4.
3. Trongm t phương án m ng ki u lư i k t n i n=m2 b x lý song song, b x lý P(i,j)
ñư c k t n i v i 4 b x lý (P(i±1) mod m, j), P(i, (j±1) mod m), sao cho các k t n i
bao xung quanh các c nh c a lư i. Hãy v m ng ki u lư i có 16 b x lý theo 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:
0 1 3 0 4
1 2 0 1  
1 2 3    1 2 1 3 0
  2 0 3 0
a)  2 0 4 , b) 
0 , c)  3 1 1 0 1 .
  3 1 1  
 3 4 0   0 3 0 0 2
1 0 1 0  
4 0 1 2 3


51
http://ebook.here.vn T i mi n phí ð thi, eBook, Tài li u h c t p

5. Nêu ý nghĩa c a t ng các ph n t trên m t hàng (t.ư. c t) c a m t ma tr n li n k ñ i
v i m t ñ th vô hư ng ? ð i v i ñ th có hư ng ?
6. Tìm ma tr n li n k cho các ñ th sau:
a ) Kn , b) Cn, c) Wn , d) Km,n , e) Qn.
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?
 0 1 0 1  0 1 1 1 
   
1 0 0 1 1 0 0 1
 0 0 0 1  , 1 0 0 1  .
   
1 1 1 0  1 1 1 0 
   
9. Hai ñơn ñ th v i ma tr n li n k sau ñây có là ñ ng c u không?
1 1 0 0 0   0 1 0 0 1 
   
1 0 1 0 1   0 1 1 1 0 
 0 0 0 1 1  , 1 0 0 1 0  .
   
 0 1 1 1 0  1 0 1 0 1 
   
10. Các ñ th G và G’ sau có ñ ng c u v i nhau không?
a) u1 v1 v2

u2
v5 v6
u3

u4
u6 v4 v3
u5
b)
u1 u2 u3 v1 v2

v6 v3

u4 u5 u6 v5 v4
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
Đề thi vào lớp 10 môn Toán |  Đáp án đề thi tốt nghiệp |  Đề thi Đại học |  Đề thi thử đại học môn Hóa |  Mẫu đơn xin việc |  Bài tiểu luận mẫu |  Ôn thi cao học 2014 |  Nghiên cứu khoa học |  Lập kế hoạch kinh doanh |  Bảng cân đối kế toán |  Đề thi chứng chỉ Tin học |  Tư tưởng Hồ Chí Minh |  Đề thi chứng chỉ Tiếng anh
Theo dõi chúng tôi
Đồng bộ tài khoản