Bài giảng Toán rời rạc - Bài 5: Cây - Trần Vĩnh Đức

Cây Trần Vĩnh Đức HUST Ngày 24 tháng 7 năm 2018 1 / 46 Tài liệu tham khảo ▶ Norman L. Biggs, Discrete Mathematics, Oxford University Press, 2002. ▶ L. Lovász, J. Pelikán, K. Vesztergombi, Discrete Mathematics: Elementary and Beyond, Springer-Verlag New York, 2003. ▶ K. H. Rosen, Toán học rời rạc ứng dụng trong tin học. 2 / 46 Nội dung Một số tính chất của cây Đếm cây gán nhãn Định nghĩa Ta nói rằng đồ thị T là một cây nếu nó có hai tính chất: (T1) T liên thông; (T2) T không có chu trình. Ví dụ 4 / 46 Các cây với 1, 2 hoặc 3 đỉnh 5 / 46 Có hai cây với 4 đỉnh 6 / 46 Có ba cây với 5 đỉnh 7 / 46 Bài tập Ta biết rằng có sáu cây (đôi một không đẳng cấu) với sáu đỉnh; hãy vẽ chúng. 8 / 46 Mệnh đề Nếu T = (V,E) là một cây với ít nhất hai đỉnh, thì với mỗi cặp đỉnh x, y có duy nhất một đường đi từ x tới y. Chứng minh. Vì T liên thông nên có đường đi từ x tới y. Nếu có đường đi khác từ x tới y, vậy thì ta có chu trình x y Mâu thuẫn với định nghĩa của cây. 9 / 46 Bài tập Hãy chứng minh rằng tính chất: (T3) với mỗi cặp đỉnh x, y có duy nhất một đường đi từ x tới y; kéo theo cả hai tính chất: (T1) T liên thông; và (T2) T không có chu trình. 10 / 46 Mệnh đề Nếu T = (V,E) là một cây với ít nhất hai đỉnh, thì đồ thị thu được từ T bằng cách xóa đi một cạnh bất kỳ sẽ có hai thành phần liên thông, mỗi thành phần là một cây. 11 / 46 Mệnh đề Nếu T = (V,E) là một cây thì |E| = |V| − 1. 1 2 3 4 5 6 7 8 9 12 / 46 Chứng minh bằng quy nạp mạnh Đặt P(n) = “Cây với n đỉnh có n− 1 cạnh” Bước cơ sở: P(1) đúng. Tại sao? Bước quy nạp: Giả sử P(1), · · · ,P(k) đều đúng để chứng minh P(k+ 1). ▶ Xét T là cây với |V| = k+ 1 và xét uv là một cạnh của T. ▶ Xóa cạnh uv khỏi T ta được hai cây T1 = (V1,E1) và T2 = (V2,E2), ta có |V1|+ |V2| = |V|, |E1|+ |E2| = |E| − 1. ▶ Áp dụng giả thiết quy nạp ta được |E| = |E1|+ |E2|+ 1 = (|V1| − 1) + (|V2| − 1) + 1 = |V| − 1. 13 / 46 Định lý Nếu T = (V,E) là một cây với ít nhất hai đỉnh, vậy thì: (T3) với mỗi cặp đỉnh x, y có duy nhất một đường đi từ x tới y; (T4) đồ thị thu được từ T bằng cách xóa đi một cạnh bất kỳ sẽ có hai thành phần liên thông, mỗi thành phần là một cây; (T5) |E| = |V| − 1. 14 / 46 Bài tập Xét cây T = (V,E) với |V| ≥ 2. Hãy chứng minh rằng T có ít nhất hai đỉnh bậc 1. 15 / 46 Bài tập Xét T = (V,E) là cây với |V| ≥ 2. Hãy dùng tính chất (T5) |E| = |V| − 1; để chứng minh rằng T có ít nhất hai đỉnh bậc 1. 16 / 46 Bài tập Ta nói rằng đồ thị F là một rừng nếu nó có tính chất: (T2) F không có chu trình. Hãy chứng minh rằng nếu F = (V,E) là một rừng với c thành phần liên thông thì |E| = |V| − c. 17 / 46 Định lý Xét đồ thị T = (V,E). Các khẳng định sau đây là tương đương nhau: 1. T là cây; 2. T không chứa chu trình và |E| = |V| − 1; 3. T liên thông và |E| = |V| − 1; 4. T là đồ thị liên thông, nhưng nếu xóa đi một cạnh bất kỳ thì đồ thị thu được là không liên thông; 5. Hai đỉnh khác nhau bất kỳ của T được nối với nhau bởi đúng một đường; 6. T không chứa chu trình, nhưng nếu ta thêm một cạnh nối hai đỉnh không kề nhau trong T thì đồ thị nhận được có đúng một chu trình. 18 / 46 Bài tập Hãy chứng minh định lý trước. 19 / 46 Nội dung Một số tính chất của cây Đếm cây gán nhãn Câu hỏi Có bao nhiêu cây với n đỉnh? 21 / 46 Câu hỏi Hai cây này có trùng nhau? 22 / 46 Cây gán nhãn ▶ Ta cố định các đỉnh của cây, mỗi đỉnh được gán một nhãn. ▶ Hai cây là giống nhau nếu và chỉ nếu chúng có cùng tập cạnh. 23 / 46 Ví dụ Hoán đổi nhãn 2 và 4 của cây gán nhãn dưới đây cho ta một cây gán nhãn khác. 24 / 46 Bài tập Tìm số cây gán nhãn với 2, 3, 4, và 5 đỉnh? 25 / 46 Định lý (Cayley) Số cây gán nhãn với n đỉnh là nn−2. Trong phần còn lại của mục này, ta sẽ đi chứng minh định lý Cayley. 26 / 46 Lưu trữ cây: dùng ma trận kề 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 1 0 27 / 46 Mệnh đề Số lượng cây gán nhãn với n đỉnh phải không nhiều hơn 2(n2−n)/2. Tại sao? 28 / 46 Lưu trữ cây: dùng danh sách cạnh 7 8 9 6 3 0 2 6 6 9 9 2 2 0 2 4 1 5 29 / 46 Mệnh đề Số lượng cây gán nhãn với n đỉnh phải ít hơn 22n log2 n. Tại sao? 30 / 46 Lưu trữ cây: dùng Father code ▶ Cố định một đỉnh làm gốc (ví dụ đỉnh có nhãn nhỏ nhất). ▶ Liệt kê các cạnh giống như lưu trữ dùng danh sách cạnh (theo hai dòng); tuy nhiên ▶ với mỗi cạnh, đỉnh ở dòng dưới luôn là đỉnh gần gốc hơn (hay còn gọi là cha của) đỉnh ở dòng trên, và ▶ các đỉnh ở trên được sắp thứ tự. 31 / 46 Father code: Ví dụ 1 2 3 4 5 6 7 8 9 6 0 0 2 6 2 9 9 2 Câu hỏi Tại sao dòng đầu tiên lại là các số 1, 2, 3, 4, 5, 6, 7, 8, 9? 32 / 46 Father code ▶ Nếu cây có n đỉnh thì dòng đầu tiên luôn là 1, 2, . . . ,n− 1. ▶ Tại sao số 0 không xuất hiện ở dòng đầu tiên? ▶ Vậy ta có thể xóa dòng đầu tiên. ▶ Father code là dòng thứ 2. 33 / 46 Bài tập Xét các ”mã” sau: 1. (0, 1, 2, 3, 4, 5, 6, 7); 2. (7, 6, 5, 4, 3, 2, 1, 0); 3. (0, 0, 0, 0, 0, 0, 0, 0); 4. (2, 3, 1, 2, 3, 1, 2, 3). Những mã nào ở trên có thể là ”father codes” của cây? 34 / 46 Mệnh đề Số lượng cây gán nhãn với n đỉnh phải không nhiều hơn nn−1. 35 / 46 Lưu trữ cây: dùng Prüfer code mở rộng Thuật toán tính Prüfer code mở rộng từ cây 1. Nếu cây không có cạnh nào thì thuật toán dừng. 2. Tìm đỉnh u có bậc 1 và có nhãn nhỏ nhất khác 0. 3. Gọi cạnh có đầu mút u là {u, v}. Ghi ra uv . 4. Xóa đỉnh u và cạnh {u, v} khỏi cây. 5. Quay lại bước 1. 8.4 How to Store Trees 151 0 15 2 6 3 7 4 FIGURE 8.5. A tree reconstructed from its Pru¨fer code How does the first row start? Remember that this is the node that we delete in the first step; by the rule of constructing the Pru¨fer code, this is the node with degree 1 with smallest label. Could this node be node 1? No, because then we would have to delete it in the first step, and it could no longer occur, but it does. By the same token, no number occurring in the second row could be a leaf of the tree at the beginning. This rules out 2, 3, and 4. What about 5? It does not occur in the second row; does this mean that it is a leaf of the original tree? The answer is yes; otherwise, 5 would have been the father of some other node, and it would have been written in the second row when this other node was deleted. Thus 5 was a leaf with smallest label, and the first row of the extended Pru¨fer code must start with 5. Let’s try to figure out the next entry in the first row, which is, as we know, the leaf with smallest label of the tree after 5 was deleted. The node 1 is still ruled out, since it occurs later in the second row ; but 2 does not occur again, which means (by the same argument as before) that 2 was the leaf with smallest label after 5 was deleted. Thus the second entry in the first row is 2. Similarly, the third entry must be 4, since all the smaller numbers either occur later or have been used already. Continuing in a similar fashion, we get that the full array must have been 5 2 4 6 7 3 1 2 4 0 3 3 1 0 This corresponds to the tree in Figure 8.5 Proof. [of Lemma 8.4.1] The considerations above are completely general, and can be summed up as follows: Each entry in the first row of the extended Pru¨fer code is the smallest integer that does not occur in the first row before it, nor in the second row below or after it. 36 / 46 Prüfer code mở rộng 1 3 4 5 6 7 8 9 2 6 0 2 6 2 9 9 2 0 Câu hỏi Tại sao vị trí cuối ở hàng dưới luôn là 0? 37 / 46 Bổ đề Hàng đầu tiên của một Prüfer code mở rộng có thể tính được từ hàng thứ hai. 38 / 46 Ví dụ Giả sử ta có một Prüfer code mở rộng còn thiếu hàng trên như sau: x1 2 4 0 3 3 1 0 Đỉnh x1 phải thỏa mãn ba điều kiện: 1. x1 ∈ {0, 1, . . . , 7}. Tại sao? 2. x1 là đỉnh bậc 1, có nhãn nhỏ nhất khác 0. 3. khi xây dựng dãy từ cây, x1 bị xóa khỏi cây ở bước đầu tiên. Điều kiện 3 chỉ ra rằng x1 sẽ không xuất hiện trong hàng 2. Tại sao? Từ điều kiện 2, ta được x1 = 5. Tại sao? 39 / 46 Ví dụ Tiếp tục ví dụ trước, bây giờ ta có: 5 x2 2 4 0 3 3 1 0 Đỉnh x2 phải thỏa mãn ba điều kiện: 1. x2 ∈ {0, 1, . . . , 7}. Tại sao? 2. x2 là đỉnh bậc 1, có nhãn nhỏ nhất khác 0 và 5. 3. khi xây dựng dãy từ cây, x2 bị xóa khỏi cây ở bước thứ hai. Vậy x2 = 2. 40 / 46 Bài tập Hãy hoàn thành nốt hàng trên của Prüfer code mở rộng sau 5 2 2 4 0 3 3 1 0 41 / 46 Khẳng định Mỗi phần tử ở hàng đầu tiên của Prüfer code mở rộng là số nguyên nhỏ nhất thỏa mãn: ▶ ở hàng đầu tiên, số này không xuất hiện trước nó; ▶ ở hàng thứ hai, số này không xuất hiện ở dưới nó hoặc phía sau nó. Ví dụ /1 /3 /4 ? 6 0 2 /6 /2 /9 /9 /2 /0 42 / 46 Prüfer code ▶ Ta không cần lưu trữ toàn bộ Prüfer code mở rộng, mà ▶ ta chỉ cần lưu tữ dãy gồm n− 2 phần tử của hàng thứ hai. ▶ Dãy này gọi là Prüfer code của cây. ▶ Vậy thì, Prüfer code là một dãy số độ dài n− 2, với mỗi phần tử của nó là một số nguyên từ 0 đến n− 1. 43 / 46 Bổ đề Mọi dãy có độ dài n− 2 gồm các số nguyên giữa 0 và n− 1 đều là Prüfer code của một cây n đỉnh nào đó. Ta đã hoàn thành chứng minh định lý sau chưa? Định lý (Cayley) Số cây gán nhãn với n đỉnh là nn−2. 44 / 46 Bài tập (Lập trình) Viết chương trình nhập vào một dãy là mã Prüfer của một cây và in ra cây đó. Bạn có thể hiện cây ở dạng danh sách cạnh, hoặc sử dụng công cụ Graphviz để vẽ tự động. 45 / 46 Cài đặt Prufer Code 1. Version 1 2. Version 2 3. Version 3 46 / 46