intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE
 » 
 » 

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

Chia sẻ: Trần Bá Trung5 | Ngày: | Loại File: PDF | Số trang:17

Thêm vào BST
Báo xấu
148
lượt xem 50
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

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.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

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

  1. 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
  2. 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
  3. 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
  4. 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
  5. 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
  6. 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
  7. 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
  8. 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
  9. 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
  10. 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
  11. 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
  12. 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
  13. 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
  14. http://ebook.here.vn T i mi n phí ð thi, eBook, Tài li u h c t p ði u ki n ñ : Gi s m i ñư ng ñi n i u, v ñ u ñi qua ñ nh x, nên n u b ñ nh x và các c nh liên thu c v i x thì ñ th con G1 nh n ñư c t G ch a hai ñ nh u, v không liên thông. Do ñó G1 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 ñó (n − k )(n − k + 1) n−k ≤m≤ . 2 Ch ng minh: B t ñ ng th c n − k ≤ m ñư 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 m0 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à m0−1 c nh. Theo gi thi t quy n p, ta có m0−1 ≥ n−(k+1) hay m0 ≥ n−k. V y m ≥ n-k. B sung c nh vào G ñ nh n ñư c ñ th G’’ có m1 c nh sao cho k thành ph n liên thông là nh ng ñ th ñ y ñ . Ta có m ≤ m1 nên ch c n ch ng minh (n − k )(n − k + 1) m1 ≤ . 2 Gi s Gi và Gj là hai thành ph n liên thông c a G’’ v i ni và nj ñ nh và ni ≥ nj >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
  15. 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
  16. 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
  17. http://ebook.here.vn T i mi n phí ð thi, eBook, Tài li u h c t p 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 tròn, ñ m i ngư i ng i gi a hai ngư i mà ñ i bi u ñó quen. 15. M t l p h c có ít nh t 4 sinh viên. M i sinh viên thân v i ít nh t 3 sinh viên khác. Ch ng minh r ng có th x p m t s ch n sinh viên ng i quanh m t cái bàn tròn ñ m i sinh viên ng i gi a hai sinh viên mà h thân. 16. Trong m t cu c h p có ñúng hai ñ i bi u không quen nhau và m i ñ i bi u này có m t s l ngư i quen ñ n d . Ch ng minh r ng luôn luôn có th x p m t s ñ i bi u ng i chen gi a hai ñ i bi u nói trên, ñ m i ngư i ng i gi a hai ngư i mà anh ta quen. 17. M t thành ph có n (n ≥ 2) nút giao thông và hai nút giao thông b t kỳ ñ u có s ñ u m i ñư ng ng m t i m t trong các nút giao thông này ñ u không nh hơn n. Ch ng minh r ng t m t nút giao thông tuỳ ý ta có th ñi ñ n m t nút giao thông b t kỳ khác b ng ñư ng ng m. 53
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN
TRỢ GIÚP
HỖ TRỢ KHÁCH HÀNG
Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.

 

Đồng bộ tài khoản
2=>2