Bài giảng Toán rời rạc: Cây và một số ứng dụng của cây - ThS. Hoàng Thị Thanh Hà

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:8

Thêm vào BST

Báo xấu

16
lượt xem 4
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài giảng Toán rời rạc - Cây và một số ứng dụng của cây, được biên soạn gồm các nội dung chính sau: Khái niệm cây; Cây bao trùm; Cây bao trùm nhỏ nhất; Cây bao trùm lớn nhất; Cây phân cấp; Duyệt cây; Cây nhị phân. Mời các bạn cùng tham khảo!

Chủ đề:

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

Lưu

Nội dung Text: Bài giảng Toán rời rạc: Cây và một số ứng dụng của cây - ThS. Hoàng Thị Thanh Hà

NỘI DUNG Toán rời rạc (6): 1. Khái niệm cây 2. Cây bao trùm CÂY VÀ MỘT SỐ ỨNG 3. Cây bao trùm nhỏ nhất Cây bao trùm lớn nhất DỤNG CỦA CÂY 4. 5. Cây phân cấp 6. Duyệt cây Ts. Hoàng Thị Thanh Hà Khoa Thống kê –Tin học 7. Cây nhị phân Trường Đại học Kinh tế 1. Cây biểu thức 2. Cây mã tiền tố 30/10/2012 1 30/10/2012 2 1. KHÁI NIỆM CÂY 1. VÍ DỤ 1 Khái niệm cây do Cayley đưa ra vào năm 1857. Ví dụ: Rừng sau có 3 cây: Định nghĩa 1: Giả sử T = (V, E) là một đồ thị vô hướng. T là một cây nếu nó thỏa mãn hai tính chất sau: i m - liên thông, a d - không có chu trình. c f g h j l Cây không có chu trình nên không có khuyên, không có cạnh bội, nên ta quy ước Đồ thị vô hướng chính là b e đơn đồ vo hướng k n 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. 30/10/2012 3 30/10/2012 4 1. KHÁI NIỆM CÂY (tiếp) 1. KHÁI NIỆM CÂY (tiếp) Định lý 1: Cho T là đồ thị vô hướng có số đỉnh không Chứng minh: 1)⇒2) Chỉ cần chứng minh rằng ⇒ ít hơn 2. Khi đó các khẳng định sau là tương đương: một cây có n đỉnh thì có n−1 cạnh. Ta chứng 1) T là một cây. minh bằng quy nạp. Điều này hiển nhiên khi 2) T liên thông và có n−1 cạnh. n=2. Giả sử cây có k đỉnh thì có k−1 cạnh, ta 3) T không chứa chu trình và có n−1 cạnh. chứng minh rằng cây T có k+1 đỉnh thì có k 4) T liên thông và mỗi cạnh là cầu. cạnh. Thật vậy, trong T nếu ta xoá một đỉnh 5) Giữa hai đỉnh phân biệt bất kỳ của T luôn có duy treo và cạnh treo tương ứng thì đồ thị nhận nhất một đường đi sơ cấp. được là một cây k đỉnh, cây này có k−1 cạnh, 6) T không chứa chu trình nhưng khi thêm một cạnh theo giả thiết quy nạp. Vậy cây T có k cạnh. mới thì có được một chu trình duy nhất. 30/10/2012 5 30/10/2012 6 1
1. KHÁI NIỆM CÂY (tiếp) 1. KHÁI NIỆM CÂY (tiếp) Chứng minh: 2)⇒3) Nếu T có chu trình thì bỏ đi một cạnh ⇒ Chứng minh: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, trong chu trình này thì T vẫn liên thông. Làm lại như nhưng không thể được nối bởi hai đường đi sơ cấp vì thế cho đến khi trong T không còn chu trình nào mà nếu thế, hai đường đó sẽ tạo ra một chu trình và khi vẫn liên thông, lúc đó ta được một cây có n đỉnh 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. nhưng có ít hơn n−1 cạnh, trái với 2). 5)⇒6) Nếu T chứa một chu trình thì hai đỉnh bất kỳ ⇒ 3)⇒4) Nếu T có k thành phần liên thông T1, ..., Tk ⇒ trên chu trình này sẽ được nối bởi hai đường đi sơ lần lượt có số đỉnh là n1, ..., nk (với n1+n2+ … cấp. Ngoài ra, khi thêm một cạnh mới (u,v), cạnh này +nk=n) thì mỗi Ti là một cây nên nó có số cạnh là sẽ tạo nên với đường đi sơ cấp duy nhất nối u và v ni−1. Vậy ta có: n−1=(n1−1)+(n2−1)+ ... một chu trình duy nhất. +(nk−1)=(n1+n2+ … +nk)−k=n−k. 6)⇒1) Nếu T không liên thông thì thêm một cạnh nối ⇒ Do đó k=1 hay T liên thông. Hơn nữa, khi bỏ đi một hai đỉnh ở hai thành phần liên thông khác nhau ta cạnh thì T hết liên thông, vì nếu còn liên thông thì T không nhận được một chu trình nào. Vậy T liên là một cây n đỉnh với n−2 cạnh, trái với điều đã chứng thông, do đó nó là một cây. minh ở trên. 30/10/2012 7 30/10/2012 8 2. CÂY BAO TRÙM 2. VÍ DỤ CÂY BAO TRÙM Định nghĩa 2 Đồ thị G có cây bao trùm: Giả sử G là một đồ thị vô hướng liên thông. a b Nếu ta loại bỏ cạnh nằm trên chu trình nào đó c 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 d e 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 a b a b của G. Cây đó gọi là cây khung hay cây bao c c trùm của đồ thị G. Hay cho đồ thị G, đồ thị con T chứa tất cả các d e d e đỉnh, T là 1 cây => T là cây bao trùm của G Hai cây bao trùm của đồ thị G 30/10/2012 9 30/10/2012 10 2. CÂY BAO TRÙM (tiếp) 2. CÂY BAO TRÙM (tiếp) Định lý 2: Đồ thị vô hướng G có cây bao trùm ⇔ G Cách xây dựng cây bao trùm liên thông. Chứng minh: ⇒ Hiển nhiên, vì cây bao trùm liên thông suy ra G a liên thông. ⇐ Chọn a là một đỉnh bất kỳ trong đồ thị G. Ký hiệu: d(x) là khoảng cách giữa a và đỉnh x. D0 D1 D2 ... Xây dựng các tập đỉnh: D0 = {a}, Di = { x  d(x) = i } với i ≥ 1. Chú ý: Mỗi đỉnh x thuộc Di (i ≥ 1) đều có đỉnh y thuộc Di-1 sao cho (x, y) là một cạnh, vì nếu < a, ... , y, x > là đường đi ngắn nhất nối a với x thì < a, ... , y > là đường đi ngắn nhất nối a với y và y ∈ Di-1. 30/10/2012 11 30/10/2012 12 2
2. CÂY BAO TRÙM (tiếp) 3. CÂY BAO TRÙM NHỎ NHẤT Chứng minh (tiếp): Lập tập cạnh T như sau: Bài toán: Cho đồ thị vô hướng G liên thông với Với mỗi đỉnh x của đồ thị G, x ∈ Di với i ≥ 1, ta lấy tập cạnh E và hàm trọng số c : E → N. Tìm cây cạnh nào đó nối x với một đỉnh trong Di-1. bao trùm T của G sao cho tổng trọng số của các Tập cạnh này sẽ tạo nên một đồ thị riêng của G với n cạnh của T đạt giá trị nhỏ nhất. đỉnh và n - 1 cạnh. Đồ thị riêng này liên thông vì mỗi đỉnh đều được nối Một số thuật toán tìm cây bao trùm nhỏ nhất: với đỉnh a. Theo tính chất 2) của cây thì T là một cây. - Thuật toán Kruskal Do vậy, T là cây bao trùm của đồ thị G. - Thuật toán Prim 30/10/2012 13 30/10/2012 14 3.1. THUẬT TOÁN KRUSKAL 3.1. THUẬT TOÁN KRUSKAL Thuật toán: Đồ thị có trọng số và cây bao trùm nhỏ nhất: Đầu vào: Đồ thị G và ma trận trọng số M Đầu ra: Độ lớn của cây khung và tô đậm cây khung 2 1. Sắp xếp các cạnh tăng dần theo trọng số. Chọn 1 2 1 1 e có trọng số bé nhất, giả sử e1, đặt W= {e1}. 1 4 1 2. Giả sử đã chọn được W = {e1, e2, ... , ei}. Chọn 4 1 ei+1 là cạnh có trọng số bé nhất trong số các 5 6 5 6 5 6 cạnh còn lại trong E \ W sao cho {e1, e2, ... , ei, 5 6 ei+1} không chứa chu trình. 2 3. Bổ sung: W := W ∪ {ei+1}. 2 4. Lặp lại các bước 2, 3 chừng nào còn có thể. 30/10/2012 15 30/10/2012 16 3.1. THUẬT TOÁN KRUSKAL 3.1. THUẬT TOÁN KRUSKAL (tiếp) Đồ thị có trọng số và cây bao trùm nhỏ nhất: Định lý 3 : Tập các cạnh W tìm được theo thuật toán Kruskal tạo nên cây bao trùm nhỏ nhất của đồ thị G. 20 20 33 8 33 8 Thuật toán Kruskal chi tiết 16 16 18 9 18 9 1 procedure Kruskal ; 17 4 14 17 4 14 2 begin 3 W := ∅ ; Z := E ; 30/10/2012 17 30/10/2012 18 3
3.1. THUẬT TOÁN KRUSKAL (tiếp) 3.2. THUẬT TOÁN PRIM 4 while (|W| < n -1) and (Z ≠ ∅) do Nhận xét: Thuật toán Kruskal làm việc kém 5 begin hiệu quả đối với những đồ thị dày (đồ thị có số 6 chọn cạnh e có trọng số bé nhất trong Z ; cạnh m ≈ n(n−1)/2). Trong trường hợp đó, 7 Z := Z \ {e} ; thuật toán Prim tỏ ra hiệu quả hơn. Thuật toán 8 if W ∪ {e} không chứa chu trình then Prim còn được gọi là phương pháp lân cận gần W := W ∪ {e} nhất. 9 end ; Thuật toán Prim 10 if |W| < n -1 then writeln(″Đồ thị không liên Prim đã cải tiến thuật toán Kruskal như sau: thông″) ở mỗi vòng lặp ta chọn cạnh có trọng số bé 11 end ; nhất trong số các cạnh kề với các cạnh đã chọn mà không tạo nên chu trình. 30/10/2012 19 30/10/2012 20 3.2. THUẬT TOÁN PRIM (tiếp) 3.2. THUẬT TOÁN PRIM (tiếp) Thuật toán Prim: bắt đầu từ một đỉnh a nào đó 1 procedure Prim ; của đồ thị G ta nối nó với đỉnh “gần” nhất, 2 begin chẳng hạn b. Nghĩa là, cạnh (a, b) được chọn 3 W := {cạnh có trọng số bé nhất }; có trọng số bé nhất. Tiếp theo, trong số các 4 for i := 1 to n - 2 do cạnh kề với đỉnh a hoặc đỉnh b ta chọn cạnh 5 begin có trọng số bé nhất mà không tạo nên chu 6 e := cạnh có trọng số bé nhất kề với cạnh trong W và nếu ghép nó vào W thì không trình với cạnh (a, b). Cạnh này dẫn đến đỉnh tạo nên chu trình ; thứ ba c ... 7 W := W ∪ {e} Tiếp tục quá trình này cho đến khi nhận được 8 end cây gồm n đỉnh và n-1 cạnh. Đó chính là 9 end ; cây bao trùm nhỏ nhất. 30/10/2012 21 30/10/2012 22 4. CÂY BAO TRÙM LỚN NHẤT 4. CÂY BAO TRÙM LỚN NHẤT (tiếp) Để tìm cây bao trùm lớn nhất ta có hai cách: Trong các thuật toán Kruskal và Prim ta 1. Đổi thành dấu - cho các trọng số trên các cạnh. áp không ràng buộc về dấu của trọng số, nên có dụng một trong hai thuật toán đã trình bày ở trên thể áp dụng cho đồ thị vô hướng với trọng số để tìm cây bao trùm nhỏ nhất. Sau đó đổi dấu + trên các cạnh có cùng dấu tuỳ ý. trở lại, ta sẽ được cây bao trùm lớn nhất. 2. Sửa đổi trong các thuật toán: bước “chọn cạnh có trọng số bé nhất ... “ được thay bằng “chọn cạnh có trọng số lớn nhất ... “ còn các bước khác thì giữ nguyên. Khi thuật toán kết thúc, ta sẽ nhận được cây bao trùm lớn nhất. 30/10/2012 23 30/10/2012 24 4
5. CÂY PHÂN CẤP 5. CÂY PHÂN CẤP (tiếp) Định nghĩa 4: Cây phân cấp là một cây, trong đó có - Mức của đỉnh trong cây phân cấp: một đỉnh đặc biệt gọi là gốc, giữa các đỉnh có mối Gốc của cây có mức là 0. quan hệ phân cấp “cha-con”. Nếu mức của đỉnh cha là i thì mức của các Một số thuật ngữ: đỉnh con là i + 1. - Số các con của một đỉnh trong cây phân cấp - Chiều cao của cây là mức cao nhất của các đỉnh được gọi là bậc của đỉnh đó. trong cây. - Đỉnh không có con được gọi là lá của cây. - Đỉnh không phải là lá được gọi là đỉnh trong của cây, còn lá được gọi là đỉnh ngoài của cây. Đỉnh gốc là đỉnh duy nhất không có cha. 30/10/2012 25 30/10/2012 26 5. VÍ DỤ 5. CÂY PHÂN CẤP (tiếp) Định nghĩa 5 (đệ quy) Cây T dưới đây có đỉnh gốc a, các đỉnh lá b, g, e, - Tập rỗng là một cây phân cấp (cây rỗng). h, k. - Một đỉnh là một cây phân cấp. a - Giả sử a là một đỉnh và T1, T2, ... , Tk là các cây c phân cấp với các gốc là a1, a2, ..., ak tương ứng. b Cây T được xây dựng bằng cách cho đỉnh a làm d e f “cha” của các đỉnh a1, a2, ..., ak, sẽ là một cây phân cấp. Trong cây T này, đỉnh a là gốc và T1, g h k T2, ... , Tk là các cây con của gốc a. Hình Cây phân cấp 30/10/2012 27 30/10/2012 28 5. CÂY PHÂN CẤP (tiếp) 5. CÂY PHÂN CẤP (tiếp) Đường đi trong cây phân cấp T là một dãy các đỉnh < b1, b2, ..., bm > mà: Định lý 4 bi là “cha” của bi + 1, 1 ≤ i ≤ m -1. Giả sử T là một cây m-phân. Cây phân cấp T với bậc cao nhất của các đỉnh trong - Nếu cây T có chiều cao h thì cây có nhiều nhất mh T là m, được gọi là cây m - phân. lá. Cây m-phân đầy đủ là cây mà mọi đỉnh trong có - Nếu cây T có l lá thì cây có chiều cao h ≥ [logm l ]. đúng m con. a ... a1 a2 ak T1 T2 Tk Hình 12. Cây phân cấp tổng quát 30/10/2012 29 30/10/2012 30 5
6. CÁC CÁCH DUYỆT CÂY 6. CÁC CÁCH DUYỆT CÂY (tiếp) Duyệt cây: Định nghĩa 3. (đệ quy) Mục tiêu là đưa ra một danh sách tuyến tính liệt kê - Nếu cây T rỗng thì cả ba cách duyệt đều cho danh tất cả các đỉnh của cây, mỗi đỉnh một lần. sách rỗng. Ba cách duyệt cây hay dùng: - Nếu cây T chỉ có một đỉnh thì cả ba cách duyệt đều - Duyệt theo thứ tự trước (pre-order search) cho danh sách gồm chỉ một đỉnh này. - Duyệt theo thứ tự giữa (in-order search) - Duyệt theo thứ tự sau (post-order search) 30/10/2012 31 30/10/2012 32 6. CÁC CÁCH DUYỆT CÂY (tiếp) 6. CÁC CÁCH DUYỆT CÂY (tiếp) - Nếu cây T có gốc a và các cây con T1, T2, ..., Tk thì: 2) Duyệt theo thứ tự sau của cây T: 1) Duyệt theo thứ tự trước của cây T: danh sách (T1), (T2), … , (Tk), a bao gồm gốc a sau đó là các đỉnh của cây con T1 được duyệt theo thứ tự trước, rồi đến các đỉnh của cây con T2 được duyệt theo thứ tự trước .... cho đến 3) Duyệt theo thứ tự giữa của cây T: các đỉnh của cây con Tk được duyệt theo thứ tự (T1), a, (T2), … , (Tk) trước: a, (T1), (T2), … , (Tk) 30/10/2012 33 30/10/2012 34 6. CÁC CÁCH DUYỆT CÂY (tiếp) 6. CÁC CÁCH DUYỆT CÂY (tiếp) Ví dụ : Cho cây T Thủ tục duyệt cây theo thứ tự giữa 1 procedure D_GIUA (a) ; 1. begin 2 3 4 2. if a là lá then write(a) 3. else 5 6 7 8 4. begin 9 10 5. D_GIUA (con bên trái nhất của a ) ; 6. write(a) ; 7. for mỗi một con c của a, trừ con bên trái Duyệt theo thứ tự trước: 1, 2, 5, 6, 3, 4, 7, 9, 10, 8 nhất, từ trái sang phải do D_GIUA (c) 8. end Duyệt theo thứ tự giữa: 5, 2, 6, 1, 3, 9, 7, 10, 4, 8 9. end ; Duyệt theo thứ tự sau: 5, 6, 2, 3, 9, 10, 7, 8, 4, 1. 30/10/2012 35 30/10/2012 36 6
7. CÂY NHỊ PHÂN 7. CÂY NHỊ PHÂN (tiếp) Định nghĩa 6 Một số ứng dụng của cây nhị phân Cây nhị phân là cây phân cấp mà mỗi đỉnh của nó có - Cây biểu thức không quá hai con. - Cây mã tiền tố Các cây con của một đỉnh của cây nhị phân được phân biệt là cây con trái và cây con phải. Định lý 5: Số các cây nhị phân n đỉnh là cn = C2nn / (2n +1). Dãy số {cn} được gọi là dãy số Catalan. 30/10/2012 37 30/10/2012 38 7.1. CÂY BIỂU THỨC 7.1. VÍ DỤ CÂY BIỂU THỨC Cây biểu thức: Là cây nhị phân mà mỗi đỉnh của nó Xét biểu thức sau: E = (a + b) * (c - d). được gán nhãn theo quy tắc: Cây biểu thức tương ứng là: - Các lá được gán các đại lượng - Các đỉnh trong được gán các dấu phép toán của một biểu thức nào đó. 30/10/2012 39 30/10/2012 40 7.1. CÂY BIỂU THỨC (tiếp) 7.1. STACK TÍNH GIÁ TRỊ BIỂU THỨC d Duyệt cây biểu thức trên theo thứ tự sau, ta được danh sách: a b + c d - * b c c c-d Đây là dạng Ba lan ngược của biểu thức E, giúp máy a a a+b a+b a+b a+b E tính tính được giá trị của biểu thức một cách nhanh chóng nhờ một stack lưu giữ các đại lượng. a b + c d - * 30/10/2012 41 30/10/2012 42 7
7.2. CÂY MÃ TIỀN TỐ 7.2. CÂY MÃ TIỀN TỐ (tiếp) Cách thực hiện Xây dựng một cây nhị phân sao cho: Bài toán - Mỗi ký hiệu tương ứng với một lá, Cho một tập các ký hiệu. Hãy mã hóa các ký hiệu này - Cạnh xuống con trái của một đỉnh được gán nhãn 0 bằng dãy các chữ số 0, 1 thoả mãn tính chất tiền tố, - Cạnh đi xuống con phải được gán nhãn 1. nghĩa là không có mã của ký hiệu nào lại là tiền tố Khi đó, dãy các nhãn trên đường đi từ gốc đến lá sẽ cho của mã của ký hiệu khác. mã tiền tố của ký hiệu tương ứng. Cây nhị phân xây dựng như trên được gọi là cây mã tiền tố. 30/10/2012 43 30/10/2012 44 7.2. VÍ DỤ Các cây mã tiền tố: 0 1 0 1 1 0 1 0 0 1 0 c d e 1 0 0 1 0 0 1 a b c d e a b Các bộ mã tiền tố nhận được là: Ký hiệu Bộ mã 1 Bộ mã 2 a 000 000 b 001 11 c 010 01 d 011 001 e 100 10 30/10/2012 45 8