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ương6 - Tree

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

Thêm vào BST
Báo xấu
243
lượt xem 36
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ương6 - Tree " 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ương6 - Tree

  1. http://ebook.here.vn T i mi n phí ð thi, eBook, Tài li u h c t p CHƯƠNG VI CÂY M t ñ th liên thông và không có chu trình ñư c g i là cây. Cây ñã ñư c dùng t năm 1857, khi nhà toán h c Anh tên là Arthur Cayley dùng cây ñ xác ñ nh nh ng d ng khác nhau c a h p ch t hoá h c. T ñó cây ñã ñư c dùng ñ gi i nhi u bài toán trong nhi u lĩnh v c khác nhau. Cây r t hay ñư c s d ng trong tin h c. Ch ng h n, ngư i ta dùng cây ñ xây d ng các thu t toán r t có hi u qu ñ ñ nh v các ph n t trong m t danh sách. Cây cũng dùng ñ xây d ng các m ng máy tính v i chi phí r nh t cho các ñư ng ñi n tho i n i các máy phân tán. Cây cũng ñư c dùng ñ t o ra các mã có hi u qu ñ lưu tr và truy n d li u. Dùng cây có th mô hình các th t c mà ñ thi hành nó c n dùng m t dãy các quy t ñ nh. Vì v y cây ñ c bi t có giá tr khi nghiên c u các thu t toán s p x p. 6.1. ð NH NGHĨA VÀ CÁC TÍNH CH T CƠ B N. 6.1.1. ð nh nghĩa: Cây là m t ñ th vô hư ng liên thông, không ch a chu trình và có ít nh t hai ñ nh. M t ñ th vô hư ng không ch a chu trình và có ít nh t hai ñ nh g i là m t r ng. Trong m t r ng, m i thành ph n liên thông là m t cây. Thí d 1: R ng sau có 3 cây: i m a d c f g h j l b e k n 6.1.2. M nh ñ : N u T là m t cây có n ñ nh thì T có ít nh t hai ñ nh treo. Ch ng minh: L y m t c nh (a,b) tuỳ ý c a cây T. Trong t p h p các ñư ng ñi sơ c p ch a c nh (a,b), ta l y ñư ng ñi t u ñ n v dài nh t. Vì T là m t cây nên u ≠ v. M t khác, u và v ph i là hai ñ nh treo, vì n u m t ñ nh, u ch ng h n, không ph i là ñ nh treo thì u ph i là ñ u mút c a m t c nh (u,x), v i x là ñ nh không thu c ñư ng ñi t u ñ n v. Do ñó, ñư ng ñi sơ c p t x ñ n v, ch a c nh (a,b), dài hơn ñư ng ñi t u ñ n v, trái v i tính ch t ñư ng ñi t u ñ n v ñã ch n. 6.1.3. ð nh lý: Cho T là m t ñ th có n ≥ 2 ñ nh. Các ñi u sau là tương ñương: 1) T là m t cây. 2) T liên thông và có n−1 c nh. 3) T không ch a chu trình và có n−1 c nh. 4) T liên thông và m i c nh là c u. 5) Gi a hai ñ nh phân bi t b t kỳ c a T luôn có duy nh t m t ñư ng ñi sơ c p. 87
  2. http://ebook.here.vn T i mi n phí ð thi, eBook, Tài li u h c t p 6) T không ch a chu trình nhưng khi thêm m t c nh m i thì có ñư c m t chu trình duy nh t. ⇒ Ch ng minh: 1)⇒2) Ch c n ch ng minh r ng m t cây có n ñ nh thì có n−1 c nh. Ta ch ng minh b ng quy n p. ði u này hi n nhiên khi n=2. Gi s cây có k ñ nh thì có k−1 c nh, ta ch ng minh r ng cây T có k+1 ñ nh thì có k c nh. Th t v y, trong T n u ta xoá m t ñ nh treo và c nh treo tương ng thì ñ th nh n ñư c là m t cây k ñ nh, cây này có k−1 c nh, theo gi thi t quy n p. V y cây T có k c nh. ⇒ 2)⇒3) N u T có chu trình thì b ñi m t c nh trong chu trình này thì T v n liên thông. Làm l i như th cho ñ n khi trong T không còn chu trình nào mà v n liên thông, lúc ñó ta ñư c m t cây có n ñ nh nhưng có ít hơn n−1 c nh, trái v i 2). ⇒ 3)⇒4) N u T có k thành ph n liên thông T1, ..., Tk l n lư t có s ñ nh là n1, ..., nk (v i n1+n2+ … +nk=n) thì m i Ti là m t cây nên nó có s c nh là ni−1. V y ta có n−1=(n1−1)+(n2−1)+ ... +(nk−1)=(n1+n2+ … +nk)−k=n−k. Do ñó k=1 hay T liên thông. Hơn n a, khi b ñi m t c nh thì T h t liên thông, vì n u còn liên thông thì T là m t cây n ñ nh v i n−2 c nh, trái v i ñi u ñã ch ng minh trên. ⇒ 4)⇒5) Vì T liên thông nên gi a hai ñ nh phân bi t b t kỳ c a T luôn có m t ñư ng ñi sơ c p, nhưng không th ñư c n i b i hai ñư ng ñi sơ c p vì n u th , hai ñư ng ñó s t o ra m t chu trình và khi b m t c nh thu c chu trình này, T v n liên thông, trái v i gi thi t. ⇒ 5)⇒6) N u T ch a m t chu trình thì hai ñ nh b t kỳ trên chu trình này s ñư c n i b i hai ñư ng ñi sơ c p. Ngoài ra, khi thêm m t c nh m i (u,v), c nh này s t o nên v i ñư ng ñi sơ c p duy nh t n i u và v m t chu trình duy nh t. ⇒ 6)⇒1) N u T không liên thông thì thêm m t c nh n i hai ñ nh hai thành ph n liên thông khác nhau ta không nh n ñư c m t chu trình nào. V y T liên thông, do ñó nó là m t cây. 6.2. CÂY KHUNG VÀ BÀI TOÁN TÌM CÂY KHUNG NH NH T. 6.2.1. ð nh nghĩa: Trong ñ th liên thông G, n u ta lo i b c nh n m trên chu trình nào ñó thì ta s ñư c ñ th v n là liên thông. N u c lo i b các c nh các chu trình khác cho ñ n khi nào ñ th không còn chu trình (v n liên thông) thì ta thu ñư c m t cây n i các ñ nh c a G. Cây ñó g i là cây khung hay cây bao trùm c a ñ th G. T ng quát, n u G là ñ th có n ñ nh, m c nh và k thành ph n liên thông thì áp d ng th t c v a mô t ñ i v i m i thành ph n liên thông c a G, ta thu ñư c ñ th g i là r ng khung c a G. S c nh b lo i b trong th t c này b ng m−n+k, s này ký hi u là ν(G) và g i là chu s c a ñ th G. 6.2.2. Bài toán tìm cây khung nh nh t: Bài toán tìm cây khung nh nh t c a ñ th là m t trong s nh ng bài toán t i ưu trên ñ th tìm ñư c ng d ng trong nhi u lĩnh 88
  3. http://ebook.here.vn T i mi n phí ð thi, eBook, Tài li u h c t p v c khác nhau c a ñ i s ng. Trong ph n này ta s có hai thu t toán cơ b n ñ gi i bài toán này. Trư c h t, n i dung c a bài toán ñư c phát bi u như sau. Cho G=(V,E) là ñ th vô hư ng liên thông có tr ng s , m i c nh e∈E có tr ng s m(e)≥0. Gi s T=(VT,ET) là cây khung c a ñ th G (VT=V). Ta g i ñ dài m(T) c a cây khung T là t ng tr ng s c a các c nh c a nó: m(T)= ∑ m(e) . e∈ E T Bài toán ñ t ra là trong s t t c các cây khung c a ñ th G, hãy tìm cây khung có ñ dài nh nh t. Cây khung như v y ñư c g i là cây khung nh nh t c a ñ th và bài toán ñ t ra ñư c g i là bài toán tìm cây khung nh nh t. ð minh ho cho nh ng ng d ng c a bài toán cây khung nh nh t, dư i ñây là hai mô hình th c t tiêu bi u cho nó. Bài toán xây d ng h th ng ñư ng s t: Gi s ta mu n xây d ng m t h th ng ñư ng s t n i n thành ph sao cho hành khách có th ñi t b t c m t thành ph nào ñ n b t kỳ m t trong s các thành ph còn l i. M t khác, trên quan ñi m kinh t ñòi h i là chi phí v xây d ng h th ng ñư ng ph i là nh nh t. Rõ ràng là ñ th mà ñ nh là các thành ph còn các c nh là các tuy n ñư ng s t n i các thành ph tương ng, v i phương án xây d ng t i ưu ph i là cây. Vì v y, bài toán ñ t ra d n v bài toán tìm cây khung nh nh t trên ñ th ñ y ñ n ñ nh, m i ñ nh tương ng v i m t thành ph v i ñ dài trên các c nh chính là chi phí xây d ng h th ng ñư ng s t n i hai thành ph . Bài toán n i m ng máy tính: C n n i m ng m t h th ng g m n máy tính ñánh s t 1 ñ n n. Bi t chi phí n i máy i v i máy j là m(i,j) (thông thư ng chi phí này ph thu c vào ñ dài cáp n i c n s d ng). Hãy tìm cách n i m ng sao cho t ng chi phí là nh nh t. Bài toán này cũng d n v bài toán tìm cây khung nh nh t. Bài toán tìm cây khung nh nh t ñã có nh ng thu t toán r t hi u qu ñ gi i chúng. Ta s xét hai trong s nh ng thu t toán như v y: thu t toán Kruskal và thu t toán Prim. 6.2.3. Thu t toán Kruskal:Thu t toán s xây d ng t p c nh ET c a cây khung nh nh t T=(VT, ET) theo t ng bư c. Trư c h t s p x p các c nh c a ñ th G theo th t không gi m c a tr ng s . B t ñ u t ET=∅, m i bư c ta s l n lư t duy t trong danh sách c nh ñã s p x p, t c nh có ñ dài nh ñ n c nh có ñ dài l n hơn, ñ tìm ra c nh mà vi c b sung nó vào t p ET không t o thành chu trình trong t p này. Thu t toán s k t thúc khi ta thu ñư c t p ET g m n−1 c nh. C th có th mô t như sau: 1. B t ñ u t ñ th r ng T có n ñ nh. 2. S p x p các c nh c a G theo th t không gi m c a tr ng s . 3. B t ñ u t c nh ñ u tiên c a dãy này, ta c thêm d n các c nh c a dãy ñã ñư c x p vào T theo nguyên t c c nh thêm vào không ñư c t o thành chu trình trong T. 89
  4. http://ebook.here.vn T i mi n phí ð thi, eBook, Tài li u h c t p 4. L p l i Bư c 3 cho ñ n khi nào s c nh trong T b ng n−1, ta thu ñư c cây khung nh nh t c n tìm. Thí d 2: Tìm cây khung nh nh t c a ñ th cho trong hình dư i ñây: 20 v2 v4 v2 v4 33 8 v1 18 16 9 v6 v1 v6 17 4 14 v3 v5 v3 v5 B t ñ u t ñ th r ng T có 6 ñ nh. S p x p các c nh c a ñ th theo th t không gi m c a tr ng s : {(v3, v5), (v4, v6), (v4, v5), (v5, v6), (v3, v4), (v1, v3), (v2, v3), (v2, v4), (v1, v2)}. Thêm vào ñ th T c nh (v3, v5). Do s c nh c a T là 1
  5. http://ebook.here.vn T i mi n phí ð thi, eBook, Tài li u h c t p 6.2.4. Thu t toán Prim: Thu t toán Kruskal làm vi c kém hi u qu ñ i v i nh ng ñ th dày (ñ th có s c nh m ≈ n(n−1)/2). Trong trư ng h p ñó, thu t toán Prim t ra hi u qu hơn. Thu t toán Prim còn ñư c g i là phương pháp lân c n g n nh t. 1. VT:={v*}, trong ñó v* là ñ nh tuỳ ý c a ñ th G. ET:=∅. 2. V i m i ñ nh vj∉VT, tìm ñ nh wj∈VT sao cho m(wj,vj) = min m(xi, vj)=:βj xi∈VT và gán cho ñ nh vj nhãn [wj, βj]. N u không tìm ñu c wj như v y (t c là khi vj không k v i b t c ñ nh nào trong VT) thì gán cho vj nhãn [0, ∞]. 3. Ch n ñ nh vj* sao cho βj* = min βj vj∉VT VT := VT ∪ {vj*}, ET := ET ∪ {(wj*, vj*)}. N u |VT| = n thì thu t toán d ng và (VT, ET) là cây khung nh nh t. N u |VT| < n thì chuy n sang Bư c 4. 4. ð i v i t t c các ñ nh vj∉VT mà k v i vj*, ta thay ñ i nhãn c a chúng như sau: N u βj > m(vj*, vj) thì ñ t βj:=m(vj*, vj) và nhãn c a vj là [vj*, βj]. Ngư c l i, ta gi nguyên nhãn c a vj. Sau ñó quay l i Bư c 3. Thí d 3: Tìm cây khung nh nh t b ng thu t toán Prim c a ñ th g m các ñ nh A, B, C, D, E, F, H, I ñư c cho b i ma tr n tr ng s sau. A B C D E F H I A ∞ 15 16 19 23 20 32 18   B  15 ∞ 33 13 34 C19 20 12  16 33 ∞ 13 29 D 20 19  21   19 13 13 ∞ 22 E 30 21 11   23 34 29 22 ∞ F 34 23 21  .    20 19 21 30 34 ∞ 17 18  H    32 20 20 21 23 17 ∞ 14  I 18 12 19 11 21 18 14 ∞    Yêu c u vi t các k t qu trung gian trong t ng bư c l p, k t qu cu i cùng c n ñưa ra t p c nh và ñ dài c a cây khung nh nh t. 91
  6. http://ebook.here.vn T i mi n phí ð thi, eBook, Tài li u h c t p V.l p A B C D E F H I VT ET K.t o − [A,15] [A,16] [A,19] [A,23] [A,20] [A,32] [A,18] A ∅ 1 − − [A,16] [B,13] [A,23] [B,19] [B,20] [B,12] A, B (A,B) 2 − − [A,16] [I,11] [I,21] [I,18] [I,14] − A, B, I (A,B), (B,I) 3 − − [D,13] − [I,21] [I,18] [I,14] − A, B, I, D (A,B), (B,I), (I,D) 4 − − − − [I,21] [I,18] [I,14] − A, B, I, D, C (A,B), (B,I), (I,D), (D,C) 5 − − − − [I,21] [H,17] − − A, B, I, D, C, (A,B), (B,I), (I,D), H (D,C), (I,H) 6 − − − − [I,21] − − − A, B, I, D, C, (A,B), (B,I), (I,D), H, F (D,C), (I,H), (H,F) 7 − − − − − − − − A, B, I, D, C, (A,B), (B,I), (I,D), H, F, E (D,C), (I,H), (H,F), (I,E) V y ñ dài cây khung nh nh t là: 15 + 12 + 11 + 13 + 14 + 17 + 21 = 103. Tính ñúng ñ n c a thu t toán: ð ch ng minh thu t toán Prim là ñúng, ta ch ng minh b ng quy n p r ng T(k) (k=1, 2, ...,n), ñ th nh n ñư c trong vòng l p th k, là m t ñ th con c a cây khung nh nh t c a G, do ñó T(n) chính là m t cây khung nh nh t c a G. T(1) ch g m ñ nh v* c a G, do ñó T(1) là ñ th con c a m i cây khung c a G. Gi s T(i) (1≤i
  7. http://ebook.here.vn T i mi n phí ð thi, eBook, Tài li u h c t p 6.3. CÂY CÓ G C. 6.3.1. ð nh nghĩa: Cây có hư ng là ñ th có hư ng mà ñ th vô hư ng n n c a nó là m t cây. Cây có g c là m t cây có hư ng, trong ñó có m t ñ nh ñ c bi t, g i là g c, t g c có ñư ng ñi ñ n m i ñ nh khác c a cây. Thí d 4: k e a h o l b r d i p f m c j g n q Trong cây có g c thì g c r có b c vào b ng 0, còn t t c các ñ nh khác ñ u có b c vào b ng 1. M t cây có g c thư ng ñư c v v i g c r trên cùng và cây phát tri n t trên xu ng, g c r g i là ñ nh m c 0. Các ñ nh k v i r ñư c x p phía dư i và g i là ñ nh m c 1. ð nh ngay dư i ñ nh m c 1 là ñ nh m c 2, ... T ng quát, trong m t cây có g c thì v là ñ nh m c k khi và ch khi ñư ng ñi t r ñ n v có ñ dài b ng k. M c l n nh t c a m t ñ nh b t kỳ trong cây g i là chi u cao c a cây. Cây có g c hình trên thư ng ñư c v như trong hình dư i ñây ñ làm rõ m c c a các ñ nh. r a b c d e f g h i j k l m n o p q 93
  8. http://ebook.here.vn T i mi n phí ð thi, eBook, Tài li u h c t p Trong cây có g c, m i cung ñ u có hư ng t trên xu ng, vì v y v mũi tên ñ ch hư ng ñi là không c n thi t; do ñó, ngư i ta thư ng v các cây có g c như là cây n n c a nó. 6.3.2. ð nh nghĩa: Cho cây T có g c r=v0. Gi s v0, v1, ..., vn-1, vn là m t ñư ng ñi trong T. Ta g i: − vi+1 là con c a vi và vi là cha c a vi+1. − v0, v1, ..., vn-1 là các t tiên c a vn và vn là dòng dõi c a v0, v1, ..., vn-1. − ð nh treo vn là ñ nh không có con; ñ nh treo cũng g i là lá hay ñ nh ngoài; m t ñ nh không ph i lá là m t ñ nh trong. 6.3.3. ð nh nghĩa: M t cây có g c T ñư c g i là cây m-phân n u m i ñ nh c a T có nhi u nh t là m con. V i m=2, ta có m t cây nh phân. Trong m t cây nh phân, m i con ñư c ch rõ là con bên trái hay con bên ph i; con bên trái (t.ư. ph i) ñư c v phía dư i và bên trái (t.ư. ph i) c a cha. Cây có g c T ñư c g i là m t cây m-phân ñ y ñ n u m i ñ nh trong c a T ñ u có m con. 6.3.4. M nh ñ : M t cây m-phân ñ y ñ có i ñ nh trong thì có mi+1 ñ nh và có (m−1)i+1 lá. Ch ng minh: M i ñ nh trong c a cây m-phân ñ y ñ ñ u có b c ra là m, còn lá có b c ra là 0, v y s cung c a cây này là mi và do ñó s ñ nh c a cây là mi+1. G i l là s lá thì ta có l+i=mi+1, nên l=(m−1)i+1. 6.3.5. M nh ñ : 1) M t cây m-phân có chi u cao h thì có nhi u nh t là mh lá. 2) M t cây m-phân có l lá thì có chi u cao h ≥ [logml]. Ch ng minh: 1) M nh ñ ñư c ch ng minh b ng quy n p theo h. M nh ñ hi n nhiên ñúng khi h=1. Gi s m i cây có chi u cao k ≤ h−1 ñ u có nhi u nh t mk-1 lá (v i h≥2). Xét cây T có chi u cao h. B g c kh i cây ta ñư c m t r ng g m không quá m cây con, m i cây con này có chi u cao ≤ h−1. Do gi thi t quy n p, m i cây con này có nhi u nh t là mh-1 lá. Do lá c a nh ng cây con này cũng là lá c a T, nên T có nhi u nh t là m.mh-1=mh lá. 2) l ≤ mh ⇔ h ≥ [logml]. 6.4. DUY T CÂY NH PHÂN. 6.4.1. ð nh nghĩa: Trong nhi u trư ng h p, ta c n ph i “ñi m danh” hay “thăm” m t cách có h th ng m i ñ nh c a m t cây nh phân, m i ñ nh ch m t l n. Ta g i ñó là vi c duy t cây nh phân hay ñ c cây nh phân. Có nhi u thu t toán duy t cây nh phân, các thu t toán ñó khác nhau ch y u th t thăm các ñ nh. Cây nh phân T có g c r ñư c ký hi u là T(r). Gi s r có con bên trái là u, con bên ph i là v. Cây có g c u và các ñ nh khác là m i dòng dõi c a u trong T g i là cây 94
  9. http://ebook.here.vn T i mi n phí ð thi, eBook, Tài li u h c t p con bên trái c a T, ký hi u T(u). Tương t , ta có cây con bên ph i T(v) c a T. M t cây T(r) có th không có cây con bên trái hay bên ph i. Sau ñây là ba trong các thu t toán duy t cây nh phân T(r). Các thu t toán ñ u ñư c trình bày ñ quy. Chú ý r ng khi cây T(x) ch là môt ñ nh x thì “duy t T(x)” có nghĩa là “thăm ñ nh x”. Thí d 5: a b c d e f g h i j k l m n o p q s 6.4.2. Các thu t toán duy t cây nh phân: 1) Thu t toán ti n th t : 1. Thăm g c r. 2. Duy t cây con bên trái c a T(r) theo ti n th t . 3. Duy t cây con bên ph i c a T(r) theo ti n th t . Duy t cây nh phân T(a) trong hình trên theo ti n th t : 1. Thăm a 2. Duy t T(b) 2.1. Thăm b 2.2. Duy t T(d) 2.2.1. Thăm d 2.2.2. Duy t T(g) 2.2.2.1. Thăm g 2.2.2.3. Duy t T(l): Thăm l 2.2.3. Duy t T(h): Thăm h 2.3. Duy t T(e) 2.3.1. Thăm e 2.3.2. Duy t T(i) 2.3.2.1. Thăm i 2.3.2.2. Duy t T(m): Thăm m 2.3.2.3. Duy t T(n): Thăm n 3. Duy t T(c) 95
  10. http://ebook.here.vn T i mi n phí ð thi, eBook, Tài li u h c t p 3.1. Thăm c 3.3. Duy t T(f) 3.3.1.Thăm f 3.3.2. Duy t T(j) 3.3.2.1. Thăm j 3.3.2.2. Duy t T(o): Thăm o 3.3.2.3. Duy t T(p): Thăm p 3.3.3. Duy t T(k) 3.3.3.1. Thăm k 3.3.3.2. Duy t T(q): Thăm q 3.3.3.3. Duy t T(s): Thăm s K t qu duy t cây T(a) theo ti n th t là: a, b, d, g, l, h, e, i, m, n, c, f, j, o, p, k, q, s. 2) Thu t toán trung th t : 1. Duy t cây con bên trái c a T(r) theo trung th t . 2. Thăm g c r. 3. Duy t cây con bên ph i c a T(r) theo trung th t . Duy t cây nh phân T(a) trong hình trên theo trung th t : 1. Duy t T(b) 1.1. Duy t T(d) 1.1.1. Duy t T(g) 1.1.1.2. Thăm g 1.1.1.3. Duy t T(l): thăm l 1.1.2. Thăm d 1.1.3. Duy t T(h): Thăm h 1.2. Thăm b 1.3. Duy t T(e) 1.3.1. Duy t T(i) 1.3.1.1. Duy t T(m): Thăm m 1.3.1.2. Thăm i 1.3.1.3. Duy t T(n): Thăm n 1.3.2. Thăm e 2. Thăm a 3. Duy t T(c) 3.2. Thăm c 3.3. Duy t T(f) 3.3.1. Duy t T(j) 96
  11. http://ebook.here.vn T i mi n phí ð thi, eBook, Tài li u h c t p 3.3.1.1. Duy t T(o): Thăm o 3.3.1.2. Thăm j 3.3.1.3. Duy t T(p): Thăm p 3.3.2. Thăm f 3.3.3. Duy t T(k) 3.3.3.1. Duy t T(q): Thăm q 3.3.3.2. Thăm k 3.3.3.3. Duy t T(s): Thăm s K t qu duy t cây T(a) theo trung th t là: g, l, d, h, b, m, i, n, e, a, c, o, j, p, f, q, k, s. 3) Thu t toán h u th t : 1. Duy t cây con bên trái c a T(r) theo h u th t . 2. Duy t cây con bên ph i c a T(r) theo h u th t . 3. Thăm g c r. Duy t cây nh phân T(a) trong hình trên theo h u th t : 1. Duy t T(b) 1.1. Duy t T(d) 1.1.1. Duy t T(g) 1.1.1.2. Duy t T(l): thăm l 1.1.1.3. Thăm g 1.1.2. Duy t T(h): thăm h 1.1.3. Thăm d 1.2. Duy t T(e) 1.2.1. Duy t T(i) 1.2.1.1. Duy t T(m): Thăm m 1.2.1.2. Duy t T(n): Thăm n 1.2.1.3. Thăm i 1.2.3. Thăm e 1.3. Thăm b 2. Duy t T(c) 2.2. Duy t T(f) 2.2.1. Duy t T(j) 2.2.1.1. Duy t T(o): Thăm o 2.2.1.2. Duy t T(p): Thăm p 2.2.1.3. Thăm j 2.2.2. Duy t T(k) 2.2.2.1. Duy t T(q): Thăm q 97
  12. http://ebook.here.vn T i mi n phí ð thi, eBook, Tài li u h c t p 2.2.2.2. Duy t T(s): Thăm s 2.2.2.3. Thăm k 2.2.3. Thăm f 2.3. Thăm c 3. Thăm a K t qu duy t cây T(a) theo trung th t là: l, g, h, d, m, n, i, e, b, o, p, j, q, s, k, f, c, a. 6.4.3. Ký pháp Ba Lan: Xét bi u th c ñ i s sau ñây: d (a+b)(c− ) (1) 2 Ta v m t cây nh phân như hình dư i ñây, trong ñó m i ñ nh trong mang d u c a m t phép tính trong (1), g c c a cây mang phép tính sau cùng trong (1), ñây là d u nhân, ký hi u là ∗ , m i lá mang m t s ho c m t ch ñ i di n cho s . ∗ + − a b c / d 2 Duy t cây nh phân trong hình trên theo trung th t là: a+b ∗ c−d/2 (2) và ñây là bi u th c (1) ñã b ñi các d u ngo c. Ta nói r ng bi u th c (1) ñư c bi u di n b ng cây nh phân T( ∗ ) trong hình trên, hay cây nh phân T( ∗ ) này tương ng v i bi u th c (1). Ta cũng nói: cách vi t (ký pháp) quen thu c trong ñ i s h c như cách vi t bi u th c (1) là ký pháp trung th t kèm theo các d u ngo c. Ta bi t r ng các d u ngo c trong (1) là r t c n thi t, vì (2) có th hi u theo nhi u cách khác (1), ch ng h n là (a + b ∗ c) − d / 2 (3) ho c là a + (b ∗ c − d) / 2 (4) Các bi u th c (3) và (4) có th bi u di n b ng cây nh phân trong các hình sau. Hai cây nh phân tương ng là khác nhau, nhưng ñ u ñư c duy t theo trung th t là (2). 98
  13. http://ebook.here.vn T i mi n phí ð thi, eBook, Tài li u h c t p − + / a ∗ d 2 b c + a / − 2 ∗ d b c ð i v i cây trong hình th nh t, n u duy t theo ti n th t , ta có ∗ +ab−c/d2 (5) và n u duy t theo h u th t , ta có: ab+cd2/− ∗ (6) Có th ch ng minh ñư c r ng (5) ho c (6) xác ñ nh duy nh t cây nh phân trong hình th nh t, do ñó xác ñ nh duy nh t bi u th c (1) mà không c n d u ngo c. Ch ng h n cây nh phân trên hình th hai ñư c duy t theo ti n th t là − + a ∗ b c / d 2 khác v i (5). và ñư c duy t theo h u th t là a b c ∗ + d 2 / − khác v i (6). Vì v y, n u ta vi t các bi u th c trong ñ i s , trong lôgic b ng cách duy t cây tương ng theo ti n th t ho c h u th t thì ta không c n dùng các d u ngo c mà không s hi u nh m. Ngư i ta g i cách vi t bi u th c theo ti n th t là ký pháp Ba Lan, còn cách vi t theo h u th t là ký pháp Ba Lan ñ o, ñ ghi nh ñóng góp c a nhà toán h c và lôgic h c Ba Lan Lukasiewicz (1878-1956) trong v n ñ này. 99
  14. http://ebook.here.vn T i mi n phí ð thi, eBook, Tài li u h c t p Vi c chuy n m t bi u th c vi t theo ký pháp quen thu c (có d u ngo c) sang d ng ký pháp Ba Lan hay ký pháp Ba Lan ñ o ho c ngư c l i, có th th c hi n b ng cách v cây nh phân tương ng, như ñã làm ñ i v i bi u th c (1). Nhưng thay vì v cây nh phân, ta có th xem xét ñ xác ñ nh d n các công th c b ph n c a công th c ñã cho. Ch ng h n cho bi u th c vi t theo ký pháp Ba Lan là − ∗ ↑/−−ab ∗ 5c23↑−cd2 ∗ −−acd/↑−b ∗ 3d35 Trư c h t, chú ý r ng các phép toán +, −, *, /, ↑ ñ u là các phép toán hai ngôi, vì v y trong cây nh phân tương ng, các ñ nh mang d u các phép toán ñ u là ñ nh trong và có hai con. Các ch và s ñ u ñ t lá. Theo ký pháp Ba Lan (t.ư. Ba Lan ñ o) thì T a b (t.ư. a b T) có nghĩa là a T b, v i T là m t trong các phép toán +, −, *, /, ↑. −*↑ / − − a b*5c 23↑ − c d 2*− − a c d / ↑ − b*3d 35 13 { 2 13 2 13 2 { a −b 5c c −d a −c 3d − * ↑ / − (a − b) 5c 2 3 ↑ (c − d ) 2 * − (a − c) d / ↑ − b (3d ) 3 5 14243 14 42 3 14 4 2 3 1 24 4 3 a −b −5c (c −d ) 2 a −c − d b − 3d − * ↑ / (a − b − 5c) 2 3 (c − d ) 2 * (a − c − d ) / ↑ (b − 3d ) 3 5 14 244 4 3 14243 a −b −5 c ( b −3 d ) 3 2 a − b − 5c −*↑ 3 (c − d ) 2 * (a − c − d ) / (b − 3d ) 3 5 14243 4 4 42 3 14 244 3 3 ( b −3d )  a −b −5c    5  2  3  a − b − 5c  2 (b − 3d ) 3 −*  (c − d ) * ( a − c − d ) 1442 4  444 1444 2445 4 4 24 3 4 43  a −b −5 c  3 ( b − 3d ) 3   (c−d ) 2 ( a −c − d )  2  5 3 3  a − b − 5c  2 (b − 3d )   (c − d ) − ( a − c − d )  2  5 100
  15. http://ebook.here.vn T i mi n phí ð thi, eBook, Tài li u h c t p BÀI T P CHƯƠNG VI: 1. V t t c các cây (không ñ ng c u) có: a) 4 ñ nh b) 5 ñ nh c) 6 ñ nh 2. M t cây có n2 ñ nh b c 2, n3 ñ nh b c 3, …, nk ñ nh b c k. H i có bao nhiêu ñ nh b c 1? 3. Tìm s t i ña các ñ nh c a m t cây m-phân có chi u cao h. 4. Có th tìm ñư c m t cây có 8 ñ nh và tho ñi u ki n dư i ñây hay không? N u có, v cây ñó ra, n u không, gi i thích t i sao: a) M i ñ nh ñ u có b c 1. b) M i ñ nh ñ u có b c 2. c) Có 6 ñ nh b c 2 và 2 ñ nh b c 1. d) Có ñ nh b c 7 và 7 ñ nh b c 1. 5. Ch ng minh ho c bác b các m nh ñ sau ñây. a) Trong m t cây, ñ nh nào cũng là ñ nh c t. b) M t cây có s ñ nh không nh hơn 3 thì có nhi u ñ nh c t hơn là c u. 6. Có b n ñ i bóng ñá A, B, C, D l t vào vòng bán k t trong gi i các ñ i m nh khu v c. Có m y d ñoán x p h ng như sau: a) ð i B vô ñ ch, ñ i D nhì. b) ð i B nhì, ñ i C ba. c) ð i A nhì, ñ i C tư. Bi t r ng m i d ñoán trên ñúng v m t ñ i. Hãy cho bi t k t qu x p h ng c a các ñ i. 7. Cây Fibonacci có g c Tn ñu c d nh nghĩa b ng h i quy như sau. T1 và T2 ñ u là cây có g c ch g m m t ñ nh và v i n=3,4, … cây có g c Tn ñư c xây d ng t g c v i Tn-1 như là cây con bên trái và Tn-2 như là cây con bên ph i. a) Hãy v 7 cây Fibonacci có g c ñ u tiên. b) Cây Fibonacci Tn có bao nhiêu ñ nh, lá và bao nhiêu ñ nh trong. Chi u cao c a nó b ng bao nhiêu? 8. Hãy tìm cây khung c a ñ th sau b ng cách xoá ñi các c nh trong các chu trình ñơn. a) a b c d e f g h i j 101
  16. http://ebook.here.vn T i mi n phí ð thi, eBook, Tài li u h c t p b) a b c d e g f i j h k l 9. Hãy tìm cây khung cho m i ñ th sau. a) K5 b) K4,4 c) K1,6 d) Q3 e) C5 f) W5. 10. ð th Kn v i n=3, 4, 5 có bao nhiêu cây khung không ñ ng c u? 11. Tìm cây khung nh nh t c a ñ th sau theo thu t toán Kruskal và Prim. 42 a b 4 10 14 3 3 1 11 c d e f 5 20 9 15 7 g h 12. Tìm cây khung nh nh t b ng thu t toán Prim c a ñ th g m các ñ nh A, B, C, D, E, F, H, I ñư c cho b i ma tr n tr ng s sau. A B C D E F G H A ∞ 16 15 23 19 18 32 20    B 16 ∞ 13 33 24 20 19 11  C 15 13 ∞ 13 29 21 20 19    D  23 33 13 ∞ 22 30 21 12   . E 19 24 29 22 ∞ 34 23 21 F 18 20 21 30 34 ∞ 17 14    G  32 19 20 21 23 17 ∞ 18  H  20 11 19 12 21 14 18 ∞    Yêu c u vi t các k t qu trung gian trong t ng bư c l p, k t qu cu i cùng c n ñưa ra t p c nh và ñ dài c a cây khung nh nh t. 102
  17. http://ebook.here.vn T i mi n phí ð thi, eBook, Tài li u h c t p 13. Duy t các cây sau ñây l n lư t b ng các thu t toán ti n th t , trung th t và h u th t . a) b) a a b c b c d e f d e f g g h h i j k l i j m n o p q 14. Vi t các bi u th c sau ñây theo ký pháp Ba Lan và ký pháp Ba Lan ñ o. ( A + B )(C + D) A 2 + BD a) + . ( A − B)C + D C 2 − BD 2 4  a − d  (3a + 4b − 2d ) 3  c  b) (a − b) − − 5d  +  4  .  3   3  5 15. Vi t các bi u th c sau ñây theo ký pháp quen thu c. a) x y + 2 ↑ x y − 2 ↑ − x y * /. b) − ∗ ↑ / − − a b ∗ 3 c 2 4 ↑ − c d 5 ∗ − − a c d / ↑ − b ∗ 2 d 4 3. 103
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