Bài giảng Toán rời rạc - Phần VIII: Cây - Nguyễn Viết Đông

Nội dung text: Bài giảng Toán rời rạc - Phần VIII: Cây - Nguyễn Viết Đông

1. Cây Cây 1. ĐN và tính chất Biên soạn: TS.Nguyễn Viết Đông 2. Cây khung ngắn nhất 3. Cây có gốc 4. Phép duyệt cây 2 Định nghĩa và tính chất Định nghĩa và tính chất Định nghĩa Cây. 1 a) Cho G là đồ thị vô hướng. G được gọi là một 2 4 cây nếu G liên thông và không có chu trình 3 10 sơ cấp. 5 9 8 b) Rừng là đồ thị mà mỗi thành phần liên 6 7 15 thông của nó là một cây. 11 12 13 14 16 17 3 4 1
2. Định nghĩa và tính chất Định nghĩa và tính chất Điều kiện cần và đủ. 1 Cho T là đồ thị vô hướng có n đỉnh. Các phát biểu sau đây là tương đương: 2 4 3 i. T là cây. 10 ii. T liên thông và có n-1 cạnh. 5 9 8 iii. T không có chu trình sơ cấp và có n-1 cạnh . 6 7 15 iv. T liên thông và mỗi cạnh là một cầu. 11 12 13 14 16 17 v. Giữa hai đỉnh bất kỳ có đúng một đường đi sơ cấp nối chúng với nhau. vi. T không có chu trình sơ cấp và nếu thêm vào một cạnh giữa hai đỉnh không kề nhau thì có một chu trình sơ cấp duy nhất. 5 6 Breadth-first Search Algorithm .Thuật toán ưu tiên Định nghĩa và tính chất chiều rộng Cho G là đồ thị liên thông với tập đỉnh {v1, v2, , vn} Định nghĩa cây khung. Bước 0:thêm v1 như là gốc của cây rỗng. Bước 1: thêm vào các đỉnh kề v1 làm con của nó và các Cho G = (V,E) là đồ thị vô hướng. cạnh nối v1 với chúng. T là đồ thị con khung của G. Những đỉnh này là đỉnh mức 1 trong cây. Bước 2: đối với mọi đỉnh v mức1, thêm vào các cạnh Nếu T là một cây thì T được gọi là cây khung(hay kề với v vào cây sao cho không tạo nên chu trình đơn. cây tối đại, hay cây bao trùm) của đồ thị G. Thu được các đỉnh mức 2. . Thuật toán tìm cây khung. Tiếp tục quá trình này cho tới khi tất cả các đỉnh của đồ thị được ghép vào cây. CâyT thu được là cây khung của đồ thị. 7 2
3. Ví dụ. Xét đồ thị liên thông G. b c l a e b c l a e e f f d b d e f g i d b d f g i c h k h a i j g j h i j Chọn e làm gốc m k . Thêm a và c làm con của b, m k . h là con duy nhất của d, Các đỉnh kề với e là con của nó. . g và j là con của f, Các đỉnh mức 1 là: b, d, f, i . k là con duy nhất của i, Các đỉnh mức 2 là: a, c, h, g, j, k Depth-first Search Algorithm b c l (Thuật toán ưu tiên chiều sâu) a e Cho G là đồ thị liên thông với tập đỉnh{v1, v2, , vn} e f f Chọn một đỉnh tùy ý của đồ thị làm gốc. Xây dựng d b d g i đường đi từ đỉnh này bằng cách lượt ghép các cạnh sao cho mỗi cạnh mới ghép sẽ nối đỉnh cuối cùng trên c h đường đi với một đỉnh còn chưa thuộc đường đi.Tiếp tục h a k i j g j ghép thêm cạnh vào đường đi chừng nào không thể thêm được nữa. Nếu đường đi qua tất cả các đỉnh của đồ thị thì cây do đường đi này tạo nên là cây khung. Nếu chưa m k l m thì lùi lại đỉnh trước đỉnh cuối cùng của đường đi và xây dựng đường đi mới xuất phát từ đỉnh này đi qua các đỉnh  Cuối cùng thêm l và m là con của g và k tương còn chưa thuộc đường đi. Nếu điều đó không thể làm ứng được thì lùi thêm một đỉnh nữa trên đường đi, tức là lùi hai đỉnh trên đường đi và thử xây dựng đường đi mới. Các đỉnh mức 3 là: l, m 3
4. Ví dụ. Tìm cây bao trùm của đồ thị G. d i j f a d i j f a g d f g c h e f e h k c h b k c e h k i b k g j b a g j . Thêm i làm con thứ hai của h và lùi về f. Giải. Bắt đầu chọn đỉnh f làm gốc và . Lại thêm các hậu duệ của f : d, e, c, a Thêm các hậu duệ của f : g, h, k, j . Lùi về c và thêm b làm con thứ hai của nó . Lùi về k không thêm được cạnh nào, tiếp tục lùi về h .Cây thu được là cây khung của đồ thị đã cho Định nghĩa và tính chất Cây khung ngắn nhất Định nghĩa Cây khung ngắn nhất. Thuật toán tìm cây khung ngắn nhất a)Thuật toán Kruscal Cho G là đồ thị có trọng số. Cây khung T của G được gọi là cây khung ngắn nhất (cây tối Cho G là đồ thị liên thông, có trọng số, n đỉnh. đại ngắn nhất,cây bao trùm ngắn nhất, cây Bước 1.Trước hết chọn cạnh ngắn nhất e1 trong các cạnh khung tối tiểu) nếu nó là cây khung của G mà của G. có trọng lượng nhỏ nhất. Bước 2. Khi đã chọn k cạnh e1,e2, ek thì chọn tiếp cạnh ek+1 ngắn nhất trong các cạnh còn lại của G sao cho không tạo thành chu trình với các cạnh đã chọn trước. 15 Bước 3. Chọn đủ n-1 cạnh thì dừng. 16 4
5. Cây khung ngắn nhất Cây khung ngắn nhất 6 3 a u d a 1 4 S1 1 4 6 b b a u 3 d 6 1 4 8 b 4 6 8 c 17 c 18 Cây khung ngắn nhất Cây khung ngắn nhất 3 3 a u d a u d 1 4 1 6 6 a u 3 d b a u 3 d b 4 4 1 1 b 4 b 4 6 6 S2 8 S3 8 c 19 c 20 5
6. Cây khung ngắn nhất Thuật toán Krusal 1 A 8 B 3 5 3 C 3 a u d F 1 4 1 6 1 4 D 6 E 2 b a u 3 d 6 AE DC AC ED BD AF AD BC FE AB 1 4 b 4 1 1 1 2 3 3 4 5 6 8 6 S 8 0. S0={} 4 c c 21 22 Thuật toán Krusal Thuật toán Krusal 1 1 A 8 B A 8 B 3 5 3 5 C C F 1 4 3 F 1 4 3 1 1 6 6 E 2 D E 2 D AE DC AC ED BD AF AD BC FE AB AE DC AC ED BD AF AD BC FE AB 1 1 1 2 3 3 4 5 6 8 1 1 1 2 3 3 4 5 6 8 0. S0={} 1. S1= {AE} 1. S1=S0 + AE = {AE} 2. S =S + DC = {AE,DC} 23 2 1 24 6
7. Thuật toán Krusal Thuật toán Krusal 1 1 A 8 B A 8 B 3 5 3 5 C C F 1 4 3 F 1 4 3 1 1 6 6 E 2 D E 2 D AE DC AC ED BD AF AD BC FE AB AE DC AC ED BD AF AD BC FE AB 1 1 1 2 3 3 4 5 6 8 1 1 1 2 3 3 4 5 6 8 3. S3= {AE,DC,AC} 4. S4= {AE,DC,AC,BD} 4. S =S + BD= {AE,DC,AC,BD} 5. S =S + AF= {AE,DC,AC,BD,AF} 4 3 25 5 4 26 Thuật toán Krusal Ví dụ 1 A A B 11 3 7 10 C B 3 8 G D F 1 9 1 3 5 D E E 10 12 8 4 Kết luận: S5= {AE,DC,AC,BD,AF} là cây bao trùm tối tiểu cần tìm C 10 F Trọng lượng: 9 28 27 7
8. Cây khung ngắn nhất Cây khung ngắn nhất Thuật toán tìm cây khung ngắn nhất Thuật toán tìm cây khung ngắn nhất b)Thuật toán Prim. 6 3 a u d Bước 1. Chọn 1 đỉnh bất kỳ v1 để có cây T1 chỉ gồm 1 đỉnh. 1 4 4 Bước 2. Khi đã chọn cây Tk thì chọn tiếp cây b 6 Tk+1 = Tk ek+1. Trong đó ek+1 là cạnh ngắn nhất trong các cạnh có một đầu mút thuộc Tk và đầu mút kia 8 không thuộc Tk c Bước 3. Chọn được cây Tn thì dừng. 29 30 Cây khung ngắn nhất Cây khung ngắn nhất d a 6 u 3 d a 6 u 3 d 6 4 4 1 4 1 4 b b 6 6 8 8 T1 c T2 c c 31 c 32 8
9. Cây khung ngắn nhất Cây khung ngắn nhất 3 3 u d u d 4 a 6 u 3 d a 6 u 3 d 6 b 6 4 4 1 4 1 4 b b 6 6 8 8 T3 c T4 c c 33 c 34 Cây khung ngắn nhất Thuật toán Prim 1 A 8 B 3 5 3 C a u d F 1 4 3 1 1 4 6 E 2 D a 6 u 3 d b 6 4 1 4 b 6 8 T5 c c 35 36 9
10. Thuật toán Prim Thuật toán Prim 1 1 A 8 B A 8 B 3 5 3 5 C C F 1 4 3 F 1 4 3 1 1 6 6 E 2 D E 2 D 37 38 Thuật toán Prim Thuật toán Prim 1 1 A 8 B A 8 B 3 5 3 5 C C F 1 4 3 F 1 4 3 1 1 6 6 E 2 D E 2 D 39 40 10
11. Thuật toán Prim Thuật toán Prim 1 1 A 8 B A 8 B 3 5 3 5 C C F 1 4 3 F 1 4 3 1 1 6 6 E 2 D E 2 D Cây T5 = {AC, AE,CD,AF,DB} là cây bao trùm tối tiểu cần tìm với w(T5) = 9 41 42 Ví dụ Cây khung ngắn nhất A Đề thi 2004 11 7 10 Hãy trình bày thuật toán tìm cây khung ngắn nhất B 8 G D 9 của G chứa cạnh 58 nhưng không chứa cạnh 26 3 5 2 9 2 E 1 3 10 12 8 3 14 7 11 4 4 1 4 5 6 5 6 8 12 C 10 F 7 8 9 13 10 43 44 11
12. Cây khung ngắn nhất Cây có gốc Giải Định nghĩa. .Đặt G’= G -26 thì cây khung phải tìm là ở trong Cho T là một cây. Chọn một đỉnh r của cây gọi là G’. Đầu tiên chọn cạnh 58 sau đó áp dụng Kruscal như thông thường gốc . Vì có đường đi sơ cấp duy nhất từ gốc tới 2 9 mỗi đỉnh của đồ thị nên ta định hướng mỗi cạnh là 1 2 3 7 2 9 hướng từ gốc đi ra . Cây cùng với gốc sinh ra một 1 2 3 4 1 4 5 6 14 7 11 đồ thị có hướng gọi là cây có gốc 4 4 5 1 6 - 6 8 Trong một cây có gốc r thì deg (r) = 0, 5 6 8 12 9 7 7 8 9 deg-(v) =1với mọi đỉnh không phải là gốc. 10 13 10 45 46 Cây có gốc Cây có gốc Định nghĩa Cho cây có gốc r. level 0 . Gốc r được gọi là đỉnh mức 0 (level 0). level 1 . Các đỉnh kề với gốc r được xếp ở phía dưới gốc và gọi là đỉnh mức 1(level 1). level 2 . Đỉnh sau của đỉnh mức 1(xếp phía dưới đỉnh mức1)gọi là đỉnh mức 2. level 3 . Level (v) = k đường đi từ gốc r đến v qua k cung. level 4 .Độ cao của cây là mức cao nhất của các đỉnh. 47 48 12
13. Cây có gốc Cây có gốc Định nghĩa Định nghĩa Cho cây có gốc r Cho cây có gốc r a) Nếu uv là một cung của T thì u được gọi là cha d) Nếu có đường đi v1v2 vk thì v1, v2, , vk-1 gọi là của v, còn v gọi là con của u. tổ tiên của vk. Còn vk gọi là hậu duệ của v1, v , , v . b) Đỉnh không có con gọi là lá(hay đỉnh ngoài). 2 k-1 Đỉnh không phải là lá gọi là đỉnh trong. e) Cây con tại đỉnh v là cây có gốc là v và tất cả các đỉnh khác là mọi hậu duệ của v trong cây T c) Hai đỉnh có cùng cha gọi là anh em. đã cho. 49 50 Cây có gốc Cây có gốc Định nghĩa 1 Cho T là cây có gốc. 2 4 a) T được gọi là cây k-phân nếu mỗi đỉnh của T có 3 nhiều nhất là k con. 10 5 9 8 b) Cây 2-phân được gọi là cây nhị phân. 6 7 15 c) Cây k-phân đủ là cây mà mọi đỉnh trong có 11 12 13 14 16 17 đúng k con. d) Cây k- phân với độ cao h được gọi là cân đối nếu các lá đều ở mức h hoặc h – 1 . 51 52 13
14. Cây có gốc Cây có gốc Định nghĩa Định nghĩa Cho T là cây nhị phân có gốc là r. Ta có thể biểu Độ dài đường đi trong và độ dài đường đi ngoài diễn T như hình vẽ dưới với hai cây con tại r là Cho T là cây nhị phân đủ. TL và TR ,chúng lần lượt được gọi là cây con bên trái và cây con bên phải của T. a) Độ dài đường đi trong là tổng tất cả các mức r của các đỉnh trong, ký hiệu IP(T). b) Độ dài đường đi ngoài là tổng tất cả các mức của các lá, ký hiệu EP(T). TL TR 53 54 Cây có gốc Cây có hướng Định lí IP(T) = ? 1 EP(T) = ? 2 3 Cho T là cây nhị phân đủ với k đỉnh trong và s lá. 7 4 5 Ta có: 6 8 9 10 11 s = k+1 và EP=IP+2k 55 56 14
15. Cây có hướng Phép duyệt cây(Tree travesal) Định nghĩa Định nghĩa Cho T là cây nhị phân không đủ. Lập T’ là cây có Duyệt cây là liệt kê tất các đỉnh của cây được bằng cách sau: theo một thứ tự nào đó thành một dãy, mỗi đỉnh chỉ xuất hiện một lần . i. Thêm vào mỗi lá của T hai con. ii. Thêm vào v một con nếu v là đỉnh trong của T mà chỉ có một con. Ta đặt: IP(T) :=IP(T’)& EP(T):=EP(T’) 57 58 Phép duyệt cây Preorder Traversal: J E A H T M Y Phép duyệt tiền thứ tự Visit first. (Preoder traversal) ROOT ‘J’ 1. Đến gốc r. ‘T’ ‘E’ 2. Dùng phép duyệt tiền thứ tự để duyệt các ‘M’ ‘Y’ cây con T1 rồi cây con T2 từ trái sang ‘A’ ‘H’ phải. Visit left subtree second Visit right subtree last 59 60 15
16. Phép duyệt cây Preorder Traversal: J E A H T M Y Phép duyệt hậu thứ tự Visit first. ROOT (Posoder traversal). ‘J’ 1. Dùng phép duyệt hậu thứ tự để lần lượt ‘T’ duyệt cây con T1, T2, . từ trái sang phải. ‘E’ 2. Đến gốc r. ‘A’ ‘H’ ‘M’ ‘Y’ Visit left subtree Visit right subtree in Preorder in Preorder 61 62 Postorder Traversal: A H E M Y T J Postorder Traversal: A H E M Y T J ROOT Visit last ROOT Visit last ‘J’ ‘J’ ‘T’ ‘T’ ‘E’ ‘E’ ‘M’ ‘Y’ ‘M’ ‘Y’ ‘A’ ‘H’ ‘A’ ‘H’ Visit left subtree first Visit right subtree second Visit left subtree Visit right subtree 63 in Postorder in Postorder 64 16
17. Phép duyệt cây Inorder Traversal: A E H J M T Y Phép duyệt trung thứ tự cho cây nhị Visit second phân (Inorder traversal) ROOT ‘J’ 1. Duyệt cây con bên trái TL theo trung thứ ‘T’ tự. ‘E’ ‘M’ ‘Y’ 2. Đến gốc r. ‘A’ ‘H’ 3. Duyệt cây con bên phải theo trung thứ tự. Visit left subtree first Visit right subtree last 65 66 Inorder Traversal: A E H J M T Y Phép duyệt cây Visit second 1 ROOT preoder 2 4 3 ‘J’ 10 5 9 8 ‘T’ 6 7 ‘E’ 15 11 12 13 14 16 17 ‘M’ ‘Y’ ‘A’ ‘H’ Visit left subtree Visit right subtree Preoder:1,2,5,11,12,13,14,3,6,7,4,8,9,10,15,16,17 in Inorder in Inorder 67 68 17
18. Phép duyệt cây Phép duyệt cây r 1 a b posoder Inoder c d e 2 4 3 f g i 10 h 5 9 j m n 6 7 8 p k 15 11 12 13 14 15 16 17 t 14 q s u Inoder :p,j,q,f,c,k,g,a,d,r,b,h,s,m,e,i,t,n,u Posoder:11,12,13,14,5,2,6,7,3,8,9,15,16,17,10,4,1 69 70 Cây nhị phân của biểu thức Định nghĩa Cây nhị phân của biểu thức là cây nhị phân mà Gốc 1. Mỗi biến số được biểu diễn bởi một lá. ‘-’ 2. Mỗi đỉnh trong biểu diễn một phép toán với các thành tố là cây con tại đỉnh ấy. ‘8’ ‘5’ 3. Cây con bên trái và bên phải của một đỉnh trong biểu diễn cho biểu thức con, giá trị của chúng là thành tố mà ta áp dụng cho phép toán tại gốc của cây con. INORDER TRAVERSAL: 8 - 5 có giá trị 3 PREORDER TRAVERSAL: - 8 5 POSTORDER TRAVERSAL: 8 5 - 71 72 18
19. Cây nhị phân của biểu thức Cây nhị phân của biểu thức ‘*’ ‘*’ ‘+’ ‘3’ ‘+’ ‘3’ ‘4’ ‘2’ ‘4’ ‘2’ Kết quả? Dạng trung tố, tiền tố, hậu tố? ( 4 + 2 ) * 3 = 18 73 74 Cây nhị phân của biểu thức Giải thích Để có biểu thức theo ký pháp Ba lan, ta duyệt ‘*’ cây nhị phân của biểu thức bằng phép duyệt ‘+’ ‘3’ tiền thứ tự. Thực hiện biểu thức từ phải sang trái: ‘4’ ‘2’ Bắt đầu từ bên phải, khi gặp một phép toán thì phép toán này được thực hiện cho 2 thành tố Infix: ( ( 4 + 2 ) * 3 ) ngay bên phải nó, kết quả này là thành tố cho Prefix: * + 4 2 3 Ký pháp Ba lan : từ phải sang trái phép toán tiếp theo. Postfix: 4 2 + 3 * Ký pháp BL đảo : từ trái sang phải 75 76 19
20. Giải thích Ví dụ Để có biểu thức theo ký pháp Ba lan ngược, ta ‘*’ duyệt cây nhị phân của biểu thức bằng phép duyệt hậu thứ tự. ‘-’ ‘/’ Thực hiện biểu thức từ trái sang phải: Bắt đầu từ bên trái, khi gặp một phép toán thì ‘8’ ‘5’ ‘+’ ‘3’ phép toán này được thự hiện cho 2 thành tố ngay bên trái nó, kết quả này là thành tố cho ‘4’ ‘2’ phép toán tiếp theo. Kết quả của infix, prefix, postfix? 77 78 ‘*’ ‘*’ ‘-’ ‘/’ ‘-’ ‘/’ ‘8’ ‘5’ ‘+’ ‘3’ ‘8’ ‘5’ ‘+’ ‘3’ ‘4’ ‘2’ ‘4’ ‘2’ Infix: ( ( 8 - 5 ) * ( ( 4 + 2 ) / 3 ) ) Infix: ( ( 8 - 5 ) * ( ( 4 + 2 ) / 3 ) ) Prefix: * - 8 5 / + 4 2 3 Prefix: * - 8 5 / + 4 2 3 Thực hiện từ phải sang Postfix: 8 5 - 4 2 + 3 / * Postfix: 8 5 - 4 2 + 3 / * Thực hiện từ trái sang 79 80 20
21. Inorder Traversal: (5 + 1) / (4 - 2) = 3 Preorder Traversal: / + 5 1 – 4 2 =/+51 2 = /62 Print second Print first ROOT ROOT =3 ‘/’ ‘/’ ‘+’ ‘-’ ‘+’ ‘-’ 5 1 4 2 5 1 4 2 Print left subtree first Print right subtree last Print left subtree second Print right subtree last 81 82 Postorder Traversal: 5 1 + 4 2 – /= Cây khung có hướng = 6 4 2 –/ =6 2 / Định nghĩa Print last =3 ROOT Cho G =(V,E) là đồ thị có hướng và ‘/’ T = (V,F) là đồ thị con khung của G. Nếu T là cây có hướng thì T gọi là cây khung có ‘+’ ‘-’ hướng(hay cây có hướng tối đại) của G. 5 1 4 2 Print left subtree first Print right subtree second 83 84 21
22. Cây khung có hướng 1 2 Matrận Kirchhoff ( G không khuyên) a) Nếu G là đồ thị có hướng thì K(G) =(kij) 5 4 3 deg (i ) khi i j trong đó B là số kij ij B khi i j cung đi từ i đến j 2 1 0 1 0 ij 0 2 1 1 0 b) Nếu G là đồ thị vô hướng thì K(G) =(kij) 0 0 1 1 0 1 1 0 3 1 deg(i ) khi i j trong đó B là số k ij ij cung đi từ i đến j 1 0 0 0 1 Bij khi i j 85 86 Cây khung có hướng Đề thi Định lý Đề thi 2003 Cho đồ thị có hướng G = (V,E) với Cho G là đồ thị không khuyên. Đặt Kq(G) là phần V={1,2,3,4,5} xác định bởi ma trận kề sau: phụ của kqq(Ma trận có được từ K(G) bằng cách xoá dòng q và cột q). 0 1 0 1 0 a) Tìm số liên thông đỉnh của G Số cây khung có hướng trong G có gốc là đỉnh q 0 0 1 1 0 b) G có là đồ thị Euler không? 0 0 0 1 0 Tại sao? bằng detKq(G). c) Tìm số cây có hướng tối đại 1 1 0 0 1 của G có gốc là đỉnh 1 1 0 0 0 0 d) Vẽ các cây trong câu c) 87 88 22
23. Đề thi Đề thi Giải a) Với A  V ký hiệu G-A để chỉ đồ thị có được 1 2 từ G bằng cách xoá các đỉnh thuộc A và các cung kề với nó.Ta thấy G - A vẫn liên thông nếu A chỉ gồm một đỉnh. G - A không liên thông nếu 5 4 3 A ={1,4}. Vậy v(G) = 2 b) G liên thông và cân bằng nên G là Euler. 89 90 Đề thi Đề thi Giải c)Ma trận Kirchhoff của G là ma trận sau 2 1 1 0 2 1 0 1 0 0 1 1 0 0 2 1 1 0 KG1() 0 0 1 1 0 1 0 3 1 1 1 0 3 1 0 0 0 1 1 0 0 0 1 91 92 23
24. Đề thi Đề thi 2 1 1 1 2 detKG1 ( ) 0 1 1 4 1 0 3 5 4 3 Vậy G có 4 cây có hướng tối đại . Đó là các cây sau đây 93 94 Đề thi Đề thi 1 2 1 2 5 4 3 5 4 3 95 96 24
25. Đề thi Đề thi Đề thi 2001 Xét cây nhị phân 7 1 2 5 12 4 6 11 15 2 9 5 4 3 1 3 8 10 97 98 Đề thi Đề thi Đề thi 2001 Giải a) Hãy duyệt cây theo thứ tự giữa (trung thứ tự). a) Duyệt theo thứ tự giữa các khoá sẽ có giá trị Có nhận xét gì về giá trị của các khoá khi duyệt tăng dần 1,2,3,4,5,6,7,8,9,10,11,12,15. theo thứ tự giữa. b) Khoá 13 được chèn thành nút con bên trái của b) Hãy chèn lần lượt các khoá 13,14 vào cây mà nút 15 và khoá 14 được chèn thành nút con bên vẫn duy trì được nhận xét trên. phải của nút 13. 99 100 25
26. Đề thi Đề thi Đề thi 2002 Đề thi 2002 G a) Tìm độ dài đường đi trong và độ dài đường đi ngoài của cây. C K b) Cho biết kết quả duyệt cây theo thứ tự sau. A E I M c) Xây dựng cây biễu diễn cho thuật toán tìm kiếm nhị phân trên mảng a sắp thứ tự tăng gồm 14 phần tử. Suy ra số lần so sánh khoá trung bình B D F H J L N khi dùng thuật toán tìm kiếm nhị phân để tìm xem một phần tử x có nằm trong mảng a hay không. 101 102 Đề thi Đề thi Giải a) Độ dài đường đi trong IP=0+2.1+4.2+7.3=31. Số phép so sánh khoá trung bình Độ dài đường đi ngoài EP=IP+2n=31+2.14=59. Tìm thành công (dừng tại nút trong): b) Kết quả dyệt cây theo thứ tự sau: (IP+n)/n = (31 + 14) /14 3.21 B,A,D,F,E,C,H,J,I,L,N,M,K. Tìm không có (dừng tại nút ngoài): c) Là cây trong đề bài bằng cách thay tương ứng EP/(n+1) = 59/15 3,93 A,B,C, bởi 1,2,3, 103 104 26
27. Đề thi Đề thi Đề thi 2008 Giải:- Giả sử e là cầu.Khi đó G – e không liên thông.Giả sử T là một cây không chứa e.Do Bài 5.Một cạnh e của đồ thị đơn, liên T liên thông nó sẽ nằm trong một thành phần thông G được gọi là cầu nếu G liên thông của G – e , vì vậy T không phải là không còn liên thông khi ta xóa e. cây tối đại của G. Chứng minh rằng e là cầu nếu và - Đảo lại:Giả sử e nằm trong mọi cây tối đại. chỉ nếu mọi cây tối đại của G đều Nếu G – e liên thông thì nó sẽ chứa một cây tối đại T. Rõ ràng T cũng là một cây tối đại chứa e. của G, mà T không chứa e, mâu thuẫn.Vậy G – e không liên thông, do đó e là cầu. 105 106 Đề thi Đề thi .Đề 2008. K5 < K8 <K2 <K12 <K9 <K <K <K <K <K <K <K <K <K Bài 6. 3 6 1 14 7 4 11 10 13 b) Nếu tìm ngẫu nhiên một khóa K đã có trong a) Vẽ cây nhị phân có được bằng cách chèn cây thì số phép so sánh trung bình là bao lần lượt các khóa K1,K2, ,K14 sao cho khóa nhiêu? Ta giả thiết rằng xác suất để K bằng ở mỗi nút lớn hơn khóa của các nút thuộc cây một trong các khóa trong cây là như nhau. con bên trái và bé hơn khóa của các các nút thuộc cây con bên phải.Thứ tự của các khóa như sau: 107 108 27
28. K < K <K <K <K <K <K <K <K <K <K <K <K <K 5 8 2 12 9 3 6 1 14 7 4 11 10 13 Đề thi K1 .Độ dài đường đi trong : K4 K2 I = 0+2.1+4.2 + 6.3+ 4 = 2 +8+18+4 = 32 K K K10 5 K3 7 Số phép so sánh trung bình cho tìm kiếm thành công: K K8 K9 K6 K14 11 K13 (I + n)/n = 46/14 = 3,29 K12 109 110 Đề thi Appendix Thuật toán tìm kiếm nhị phân(binary search): Đề thi ĐHBK 2000. a) Xây dựng cây biểu diễn cho thuật toán tìm Tìm phần tử x trong dãy số tăng dần. kiếm nhị phân trên mảng sắp thứ tự tăng Nhập: dãy a1,a2, ,an tăng dần và phần tử x. gồm 13 phần tử. Xuất :vị trí của x trong dãy hoặc 0. b) Tìm độ dài đường đi trong và độ dài đường đi ngoài của cây. c) Cho biết kết quả duyệt cây theo thứ tự trước. 111 112 28
29. Appendix Thuật toán l:=1,r:= n repeat i:=(l+r)div2; if ai x then r : = i-1: utill(x = ai or (l >r); if(x =ai)then xuất i (tìm thấy x ở vị trí i) else xuất 0(không tìm thấy x trong dãy) 113 29