Bài giảng Toán học tổ hợp và cấu trúc rời rạc - Chương 5: Cây

Nội dung text: Bài giảng Toán học tổ hợp và cấu trúc rời rạc - Chương 5: Cây

1. Chương 5 CÂY
2. Nội dung . Định nghĩa và tính chất . Cây khung ngắn nhất . Cây có gốc . Phép duyệt cây 2
3. 1. Định nghĩa và tính chất Định nghĩa. Cây (tree) là đồ thị vô hướng, liên thông và không cóchu trình B E B E F F A A C D C D G1 G2 G1 là cây, G2 không phải cây 3
4. Rừng Định nghĩa. Rừng (forest) là đồthị vô hướng không cóchu trình B G I L J A C F K D E H Nhận xét. Rừng là đồ thị mà mỗi thành phần liên thông của nó là một cây. 5
5. Rừng 6
6. Tính chất của cây Định lý: Cho đồ thị vô hướng T cón đỉnh. Khi đó các phát biểu sau là tương đương: 1) T là 1 cây 2) T không chứa chu trình và có n-1 cạnh 3) T liên thông và có n-1 cạnh 4) T liên thông và mỗi cạnh của nó đều là cầu 5) Giữa hai đỉnh bất kỳ của T có đúng một đường đi nối chúng với nhau 6) T không chứa chu trình nhưng khi thêm vào một cạnh ta thu được đúng một chu trình 7
7. Hệ quả. a) Một cây có ít nhất 2 đỉnh treo b) Nếu G là một rừng có n đỉnh và có p cây thì số cạnh của G là m=n-p 8
8. Cây khung của đồ thị Định nghĩa: Một cây T được gọi là cây khung (hay cây tối đại, cây bao trùm) của đồ thị G=(V, E) nếu T là đồ thị con của G và chứa tất cả các đỉnh của G. Ví dụ. Cho đồ thị C D A F B E Hãy tìm cây khung của G? 9
9. Cây khung của đồ thị C D Đáp án. Một số cây khung của G A F B E C D C D A F A F B E B E Nhận xét. Với 1 đồthị cho trước, có thể có vài cây khung của đồthị đó 10
10. Định lý. Mọi đồ thị liên thông đều có cây khung n-2 Định lý (Cayley) Số cây khung của đồ thị Kn là n a Số cây khung 44-2=16 d f b Ví dụ: abc, bcd, cda, dab, abf, acf, bdf, c e A B C Số cây khung 55-2=125 D E 11
11. Tìm một cây khung của đồ thị Bài toán: Cho G là đồ thị vô hướng liên thông, hãy tìm 1 cây khung của đồ thị G. Lời giải • Thuật toán tìm kiếm theo chiều rộng (BFS) • Thuật toán tìm kiếm theo chiều sâu (DFS) 12
12. Tìm kiếm theo chiều rộng (BFS) Cho G là đồ thị liên thông với tập đỉnh {v1, v2, , vn}  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 và các cạnh nối v1 với chúng. Những đỉnh này là đỉnh mức 1 trong cây.  Bước 2: đối với mọi đỉnh v mức 1, thêm vào các cạnh kề với v vào cây sao cho không tạo nên chu trình. Ta thu được các đỉnh mức 2. . 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ây T có được là cây khung của đồ thị. 13
13. Ví dụ. Tìm một cây khung của đồ thị G. b c l e a e f d d b f g i h i j Chọn e làm gốc m k Chọn các đỉnh kề với e. Các đỉnh mức 1 là: b, d, f, i 14
14. b c l e a e f d f d b g i c h a k h g j i j . Thêm a và c làm con của b, m k . h là con duy nhất của d, . g và j là con của f, . k là con duy nhất của i, Các đỉnh mức 2 là: a, c, h, g, j, k 15
15. b c l e a e f d f d b g i c h a k h i j g j m k l m Cuối cùng thêm l và m là con của g và k tương ứng Các đỉnh mức 3 là: l, m Ta có được cây khung cần tìm 16
16. Ví dụ. Tìm cây khung của đồ thị bằng thuật toán BFS với D là đỉnh bắt đầu B E I D H K A F J C G 17
17. Đáp án. 18
18. Tìm kiếm theo chiều sâu (DFS) Cho G là đồ thị liên thông với tập đỉnh {v1, v2, , vn}  Chọn một đỉnh tùy ý của đồ thị làm gốc.  Xây dựng đường đi từ đỉnh này bằng cách lần 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 đường đi với một đỉnh còn chưa thuộc đường đi. Tiếp tục 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. 19
19.  Nếu chưa 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 còn chưa thuộc đường đi. Nếu điều đó không thể làm đượ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. d i j a Ví dụ. Tìm một cây khung của đồ thị với f f là đỉnh gốc c e h k b g 20
20. d i j f a g f c h e h k b k g j Thêm các hậu duệ của f : g, h, k, j Lùi về k không thêm được cạnh nào, tiếp tục lùi về h 21
21. d i j f a g d f c h e e h k b k c i g j b a Thêm i làm con thứ hai của h và lùi về f. Lại thêm các hậu duệ của f : d, e, c, a Lùi về c và thêm b làm con thứ hai của nó . Cây thu được là cây khung của đồ thị đã cho 22
22. Ví dụ. Tìm một cây khung của đồ thị bằng thuật toán DFS với A là đỉnh bắt đầu B E I D H K A F J C G 23
23. Đồ thị có trọng số Định nghĩa. Đồ thị G = (V,E) gọi là đồ thị có trọng số (hay chiều dài, trọng lượng) nếu mỗi cạnh e được gán với một số thực w(e). Ta gọi w(e) là trọng lượng của e. . Độ dài của đường đi từ u đến v bằng tổng độ dài các cạnh mà đường đi qua. . Trọng lượng của một cây T của G bằng với tổng trọng lượng các cạnh trong cây . Cây khung ngắn nhất là cây khung có trọng lượng nhỏ nhất của G. 24
24. Ma trận khoảng cách (trọng số) Định nghĩa. Cho G = (V, E), V = {v1,v2, ,vn} là đơn đồ thị có trọng số. Ma trận khoảng cách của G là ma trận D= (dij) xác định như sau: 0 khi i j dij w() vij v khi v i v j E khi vij v E 25
25. Ma trận khoảng cách Ví dụ. Tìm ma trận khoảng cách của đồ thị sau 5 16 D 0 12 7 5 12 A B 12 0 15 16 6 6 7 5 15 7 15 0 10 E C 10 5 16 0 5 6 10 5 0 26
26. Thuật toán tìm cây khung ngắn nhất Có nhiều thuật toán xây dựng cây khung ngắn nhất: – Thuật toán Boruvka – Thuật toán Kruskal – Thuật toán Jarnik – Prim – Phương pháp Dijkstra – Thuật toán Cheriton – Tarjan – Thuật toánChazelle – 27
27. Thuật toán Kruskal Input: Đồ thị G=(X, E) liên thông, X gồm n đỉnh Output: Cây khung ngắn nhất T=(V, U) của G Bước 1. Sắp xếp các cạnh trong G tăng dần theo trọng lượng; khởi tạo T := . Bước 2. Lần lượt lấy từng cạnh e thuộc danh sách đã sắp xếp. Nếu T+{e} không chứa chu trình thì thêm e vào T: T := T+{e}. Bước 3. Nếu T đủ n-1 cạnh thì dừng; ngược lại, lặp bước 2. 28
28. Thuật toán Kruskal Ví dụ. Tìm cây khung ngắn nhất của đồ thị sau 1 A 8 B 3 5 C F 1 4 3 1 6 E 2 D Giải. Sắp xếp các cạnh AE AC CD DE BD AF AD BC EF AB 1 1 1 2 3 3 4 5 6 8 29
29. Thuật toán Kruskal 1 A 8 B 3 5 C F 1 4 3 1 6 E 2 D AE AC CD DE BD AF AD BC EF AB 1 1 1 2 3 3 4 5 6 8 30
30. Thuật toán Kruskal 1 A 8 B 3 5 C F 1 4 3 1 6 E 2 D AE AC CD DE BD AF AD BC EF AB 1 1 1 2 3 3 4 5 6 8 31
31. Thuật toán Kruskal 1 A 8 B 3 5 C F 1 4 3 1 6 E 2 D AE AC CD DE BD AF AD BC EF AB 1 1 1 2 3 3 4 5 6 8 32
32. Thuật toán Kruskal 1 A 8 B 3 5 C F 1 4 3 1 6 E 2 D AE AC CD DE BD AF AD BC EF AB 1 1 1 2 3 3 4 5 6 8 33
33. Thuật toán Kruskal 1 A B 3 C F 1 3 1 E D Như vậy T = { AE, CD, AC, BD, AF } là khung ngắn nhất với trọng lượng: 9 34
34. Thuật toán Kruskal Ví dụ. Tìm cây khung ngắn nhất của đồ thị sau 5 16 D 12 10 A B 6 7 15 F 15 9 E C 10 8 35
35. Thuật toán Kruskal Ví dụ. Tìm cây khung ngắn nhất của đồ thị sau 36
36. Thuật toán Kruskal Ví dụ. Dùng thuật toán Kruskal để tìm cây khung nhỏ nhất của đồ thị sau: 7 H C 6 6 G 6 2 9 B 3 8 6 2 F K D 1 4 5 A 3 9 5 6 J 5 7 E I 4 37
37. Thuật toán Prim Input: Đồ thị liên thông G=(X, E), X gồm n đỉnh Output: Cây khung ngắn nhất T=(V, U) của G Bước 1. Chọn tùy ý v X và khởi tạo V := { v }; U := ; Bước 2. Chọn cạnh e có trọng lượng nhỏ nhất trong các cạnh wv mà w X\V và v V Bước 3. V := V  {w}; U := U  {e} Bước 4. Nếu U đủ n-1 cạnh thì dừng, ngược lại lặp từ bước 2. 38
38. Thuật toán Prim Ví dụ. Tìm cây khung ngắn nhất của đồ thị sau 5 16 D 12 10 A B 6 7 5 F 15 9 E C 10 8 V = {F, C, A, D, E, B} U = {FC, CA, AD, DE, EB} Trọng lượng: 32 39
39. Ví dụ. Tìm cây khung ngắn nhất của đồ thị sau 41
40. Ví dụ. Dùng thuật toán Prim để tìm cây khung nhỏ nhất của đồ thị sau: 7 H C 6 6 G 6 2 9 B 3 8 6 2 F K D 1 4 5 A 3 9 5 6 J 5 7 E I 4 42
41. 3. Cây có gốc Định nghĩa. Cho T là một cây. Chọn một đỉnh r của cây gọi là gốc. Vì có đường đi sơ cấp duy nhất từ gốc tới mỗi đỉnh của đồ thị nên ta định hướng mỗi cạnh là hướng từ gốc đi ra. Cây cùng với gốc sinh ra một đồ thị có hướng gọi là cây có gốc 0 4 1 0 4 3 1 5 0 2 4 7 6 3 1 6 5 2 3 5 7 2 7 6 43 Cây T Cây gốc 0 Cây gốc 4 43
42. Ví dụ Một số ví dụ về cây có gốc • Cấu trúc thư mục trên đĩa • Gia phả của một họ tộc • Một biểu thức số học (7+2/3) x (7-2) x + - 7 / 7 2 2 3 44
43. Một số khái niệm Định nghĩa. Cho cây có gốc r.  Gốc r được gọi là đỉnh mức 0 (level 0).  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).  Đỉ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(v) = k đường đi từ gốc r đến v qua k cung.  Độ cao của cây là mức cao nhất của các đỉnh. 45 45
44. level 0 level 1 level 2 level 3 level 4 46
45. Một số khái niệm Định nghĩa. Cho cây có gốc r  Nếu uv là một cung của T thì u được gọi là cha của v, còn v gọi là con của u.  Đỉnh không có con gọi là lá (hay đỉnh ngoài). Đỉnh không phải là lá gọi là đỉnh trong.  Hai đỉnh có cùng cha gọi là anh em.  Nếu có đường đi v1v2 vk thì v1, v2, , vk-1 gọi là tổ tiên của vk. Còn vk gọi là hậu duệ của v1, v2, , vk-1.  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à hậu duệ của v trong cây T đã cho. 47 47
46. Định nghĩa. Cho T là cây có gốc. a) T được gọi là cây k-phân nếu mỗi đỉnh của T có nhiều nhất là k con. b) Cây 2-phân được gọi là cây nhị phân. c) Cây k-phân đủ là cây mà mọi đỉnh trong có đú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. 48 48
47. Một số khái niệm 49
48. Định nghĩa. Cho T là cây nhị phân có gốc là r. Ta có thể biểu diễn T như hình vẽ dưới với hai cây con tại r là 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. r TL TR 50 50
49. Biểu diễn cây . Chúng ta cóthê ̉ biểu diễn cây như 1 đồ thị • Ma trận • Danh sách Nhận xét: Vì số cạnh của cây rất thưa (n-1 cạnh) nên dùng ma trận để biểu diễn cây là không hiệu quả 51
50. Biểu diễn cây Biểu diễn cây bằng danh sách kề Đỉnh Đỉnh kề 0 1 9 4 1 3 6 0 2 Ø 3 Ø 1 9 4 4 7 5 2 5 Ø 3 6 8 7 5 2 6 Ø 7 Ø 8 Ø 9 8 52
51. Một số bài toán liên quan tới cây . Bài toán 1: Kiểm tra xem đồ thị G có phải là 1 cây không . Bài toán 2: Tìm gốc của cây . Bài toán 3: Tính độ cao của cây với gốc là đỉnh r 53
52. 4. Phép duyệt cây Định nghĩa. Duyệt cây là liệt kê tất các đỉnh của cây 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. Có 2 phép duyệt cây - Phép duyệt tiền thứ tự (Preorder traversal) - Phép duyệt hậu thứ tự (Posorder traversal). 54 54
53. Phép duyệt tiền thứ tự  Đến gốc r.  Dùng phép duyệt tiền thứ tự để duyệt các cây con T1 rồi cây con T2 từ trái sang phải. Ví dụ. Duyệt cây sau 14 84 43 35 13 16 33 97 53 99 72 64 55
54. . Push the root onto the stack. . While the stack is not empty • pop the stack and visit it • push its two children 14 8844 43 35 13 16 33 97 53 99 7272 6644 Do đó các đỉnh lần lượt được duyệt là: 14, 84, 35, 13, 53, 16, 99, 72, 43, 33, 64, 97 56
55. Phép duyệt hậu thứ tự  Dùng phép duyệt hậu thứ tự để lần lượt duyệt cây con T1, T2, . từ trái sang phải.  Đến gốc r. Ví dụ. Duyệt cây sau 14 84 43 35 13 16 33 97 53 99 72 64 57
56. . Push the root onto the stack. . While the stack is not empty • pop the stack and visit it • push its two children 14 8844 43 35 13 16 33 97 53 99 7272 6644 Do đó các đỉnh lần lượt được duyệt là: 35, 53, 13, 16, 99, 72, 43, 33, 64, 97 58
57. Duyệt cây nhị phân Đối với cây nhị phân, ta có thêm phép duyệt trung thứ tự cho cây nhị phân (Inorder traversal)  Duyệt cây con bên trái TL theo trung thứ tự.  Đến gốc r.  Duyệt cây con bên phải theo trung thứ tự. Ví dụ. Duyệt cây sau 14 84 43 13 16 33 97 53 99 72 64 59 59
58. . Push the root onto the stack. . While the stack is not empty • pop the stack and visit it • push its two children 14 8844 43 13 16 33 97 53 99 7272 6644 Do đó các đỉnh lần lượt được duyệt là: 53, 13, 84, 99, 16, 72, 14, 33, 64, 43, 97 60
59. Cây nhị phân biểu thức Xét cây như sau Gốc + 8 5 Khi đó, theo phép duyệt - Tiền thứ tự: + 8 5 - Hậu thứ tự: 8 5 + - Trung thứ tự: 8 + 5 61
60. Cây nhị phân 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à - Mỗi biến số được biểu diễn bởi một lá. - 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. 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. 62
61. Tính giá trị của biểu thức được biểu diễn bằng đồ thị sau ++ 33 44 2 Kết quả? ( 4 + 2 ) * 3 = 18 63
62. Định nghĩa. Ta gọi kết quả có được khi duyệt cây nhị phân của biểu thức theo phép duyệt - Trung thứ tự là trung tố - Tiền thứ tự là tiền tố và được gọi là ký pháp Ba Lan - Hậu thứ tự là hậu tố và được gọi là ký pháp Ba Lan ngược 64
63. * + 3 4 2 Khi đó . Trung tố: 4 + 2 * 3 . Tiền tố: * + 4 2 3 Ký pháp Ba lan . Hậu tố: 4 2 + 3 * Ký pháp Ba lan ngược 65
64. Ví dụ. Cho cây nhị + phân T của biểu thức - / * 9 3 ^ 2 5 2 3 Hãy tìm tiền tố, trung tố, hậu tố của G? 66
65. Nhận xét. Để tính biểu thức khi có ký pháp Ba Lan ta tính từ phải sang trái: 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ố ngay bên phải nó, kết quả này là thành tố cho phép toán tiếp theo. Ví dụ. Tính giá trị của ký pháp Ba Lan sau: a) − ∗ 2 / 8 4 3 b) ^ − ∗ 3 3 ∗ 4 2 5 c) + − ^ 3 2 ^ 2 3 / 6 − 4 2 d) ∗ + 3 + 3 ^ 3 + 3 3 3 67
66. Giải. a) − ∗ 2 / 8 4 3 b) ^ − ∗ 3 3 ∗ 4 2 5  − ∗ 2 2 3  ^ − ∗ 3 3 8 5  − 4 3  ^ − 9 8 5  1  ^ 1 5  1 c) + − ^ 3 2 ^ 2 3 / 6 − 4 2 ? d) ∗ + 3 + 3 ^ 3 + 3 3 3 ? 68
67. Nhận xét. Để tính biểu thức khi có ký pháp Ba Lan ngược, ta tính từ bên trá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ố ngay bên trái nó, kết quả này là thành tố cho phép toán tiếp theo. Ví dụ. Tính giá trị của ký pháp Ba Lan ngược sau: a) 5 2 1−−3 1 4 ++ ∗ b) 9 3 / 5 + 7 2 − ∗ c) 3 2 ∗ 2 ^ 5 3 − 8 4 / ∗ − 69