Bài giảng Toán rời rạc - Bài 8: Cây và cây tối đại - Nguyễn Văn Hiệu

Nội dung text: Bài giảng Toán rời rạc - Bài 8: Cây và cây tối đại - Nguyễn Văn Hiệu

1. BÀI 8 CÂY & CÂY TỐI ĐẠI Giáo viên: TS. Nguyễn Văn Hiệu Email: nvhieuqt@dut.udn.vn Nguyễn Văn Hiệu, 2012, Discrete Mathematics 1
2. Nội dung 8.1. Cây 8.2. Cây tối đại 8.3. Cây tối đại ngắn nhất 8.4. Xác định cây tối đại ngắn nhất 8.5. Cây có gốc Nguyễn Văn Hiệu, 2012, Discrete Mathematics 2
3. 8.1. Cây Định nghĩa Ví dụ Cây là một đơn đồ thị vô hướng, liên thông và không chứa chu trình. Nguyễn Văn Hiệu, 2012, Discrete Mathematics 3
4. 8.1. Cây Đồ thị nào sau đây là cây? Nguyễn Văn Hiệu, 2012, Discrete Mathematics 4
5. 8.1. Cây Định nghĩa Ví dụ Rừng là một đồ thị gồm p thành phần liên thông, trong đó mỗi thành phần liên thông là một cây. Lưu ý: cây không chứa khuyên và cạnh song song 5
6. 8.1. Cây Tính chất Ví dụ Một cây T gồm N đỉnh với N 2 chứa ít nhất hai đỉnh treo 6
7. 8.1. Cây Tính chất Tính chất Cho T là một đồ thị vô hướng 3. T liên thông và mỗi cạnh có n đỉnh. Có các mệnh đề của T đều là cạnh cắt tương đương sau: (cầu). 1. T là cây. 4. Hai đỉnh bất kỳ của T được 2. T không chứa chu trình và nối với nhau bằng đúng 1 có n – 1 cạnh. đường đi đơn. 3. T liên thông và có n – 1 5. T không chứa chu trình cạnh. nhưng nếu thêm 1 cạnh bất kỳ vào T thì ta sẽ được thêm đúng 1 chu trình. Nguyễn Văn Hiệu, 2012, Discrete Mathematics 7
8. 8.2. Cây tối đại a Định nghĩa Cho G=(X, E) là một đồ thị c liên thông và T=(X, F) là một b đồ thị bộ phận của G. Nếu T là d cây thì T được gọi là một cây tối đại của G. e a  Các tên gọi khác: a  cây khung, c b c b  cây bao trùm,  cây phủ e d e d Nguyễn Văn Hiệu, 2012, Discrete Mathematics 8
9. 8.2. Cây tối đại Tính chất Ví dụ  Mọi đồ thị liên thông đều có chứa ít nhất một cây tối đại D A B E C F Nguyễn Văn Hiệu, 2012, Discrete Mathematics 9
10. 8.2. Cây tối đại Xác định cây tối đại Thuật toán Thuật toán tựa PRIM 1. Chọn tùy ý v X và khởi tạo Input: V := { v }; U := ; 2. Chọn w X \ V sao cho e Đồ thị liên thông G=(X, E), E, e nối w với một đỉnh X gồm N đỉnh trong V Output: 3. V := V  {w}; U := U  {e} Cây tối đại T=(V, U) của G 4. Nếu U đủ N-1 cạnh thì dừng, ngược lại lặp từ bước 2. Nguyễn Văn Hiệu, 2012, Discrete Mathematics 10
11. 8.2. Cây tối đại Xác định cây tối đại Xác định cây tối đại  V = {F, A, B, E, C, D} D  U = {FA, AB, BE, FC, ED} A B F E C Nguyễn Văn Hiệu, 2012, Discrete Mathematics 11
12. 8.2. Cây tối đại Cài đặt Graph Graph::SpanningTree() { //Tìm cây khung của đồ thị } Nguyễn Văn Hiệu, 2012, Discrete Mathematics 12
13. 8.3. Cây tối đại ngắn nhất Định nghĩa Định nghĩa Cho G=(X, E)  TRỌNG LƯỢNG của một cây  G được gọi là ĐỒ THỊ CÓ T của G bằng với tổng trọng TRỌNG nếu mỗi cạnh của lượng các cạnh trong cây: G được tương ứng với một L(T) = (e T)L(e) số thực, nghĩa là có một ánh xạ như sau:  CÂY TỐI ĐẠI NGẮN NHẤT L: E  |R là cây tối đại có trọng lượng nhỏ nhất của G. e | L(e)  Các tên gọi khác: cây khung bé nhất, cây bao trùm nhỏ nhất, cây phủ bé nhất Nguyễn Văn Hiệu, 2012, Discrete Mathematics 13
14. 8.3. Cây tối đại ngắn nhất Ứng dụng Ứng dụng  Bài toán xây dựng hệ thống  Bài toán nối mạng máy tính đường sắt Cần nối mạng một hệ thống Cần xây dựng hệ thống đường gồm n máy vi tính. Biết chi phí sắt nối n thành phố sao cho nối máy i với máy j là c[i,j] khách hàng có thể đi bất cứ (chi phí phụ thuộc vào độ dài một thành phố nào đến bất kỳ cáp). Hãy tìm cách nối mạng một trong số các thành phố còn sao cho tổng chi phí nối mạng lại. Mặt khác, đòi hỏi chi phí là bé nhất. để xây dựng hệ thống đường sắt là nhỏ nhất. Nguyễn Văn Hiệu, 2012, Discrete Mathematics 14
15. 8.3. Cây tối đại ngắn nhất Chú ý Nhắc lại • Trong các thuật toán tìm cây  MA TRẬN TRỌNG SỐ: tối đại ngắn nhất chúng ta LNxN : có thể bỏ đi – Lij = trọng lượng cạnh nhỏ  các khuyên; nhất nối i đến j (nếu có)  hướng các cạnh; – Lij = nếu không có cạnh  đối với các cạnh song song thì nối i đến j có thể bỏ đi và chỉ để lại một cạnh trọng lượng nhỏ nhất trong chúng. Nguyễn Văn Hiệu, 2012, Discrete Mathematics 15
16. 8.3. Cây tối đại ngắn nhất Ví dụ Ma trận trọng số 5 12 7 5 16 D 12 12 15 16 6 A B 6 7 15 10 7 5 15 5 16 5 E C 10 6 10 5 Nguyễn Văn Hiệu, 2012, Discrete Mathematics 16
17. 8.4. Xác định cây tối đại ngắn nhất Tiếp cạnh truyền thống Tiếp cạnh truyền thống  Liệt kê tất cả các cây khung  Số cây khung của đồ thị đầy đủ n-2 của G Kn là n  TÍNH TRỌNG LƯỢNG của mỗi cây tối đại của G  Chọn cây tối đại có trọng thời gian cỡ nn-2 lượng bé nhất Nguyễn Văn Hiệu, 2012, Discrete Mathematics 17
18. 8.4. Xác định cây tối đại ngắn nhất KRUSKAL KRUSKAL Input: đồ thị G=(X, E) liên 1. Sắp xếp các cạnh trong G thông, X gồm N đỉnh tăng dần theo trọng lượng; Output: cây tối đại ngắn nhất khởi tạo T := . T=(V, U) của G 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ì kết nạp e vào T: T := T+{e}. 3. Nếu T đủ N-1 cạnh thì dừng; ngược lại, lặp bước 2. Nguyễn Văn Hiệu, 2012, Discrete Mathematics 18
19. 8.4. Xác định cây tối đại ngắn nhất KRUSKAL Mã giả Input: đồ thị G=(X, E) liên KRUSKAL( ){ thông, X gồm N đỉnh T = ʘ; Output: cây tối đại ngắn nhất while(|T| } Nguyễn Văn Hiệu, 2012, Discrete Mathematics 19
20. 8.4. Xác định cây tối đại ngắn nhất Trọng số Cạnh Chọn 2 4 4 (3,5) 33 20 Chọn 8 8 (4,6) Chọn 1 18 16 9 6 9 (4,5) 14 (5,6) Không 17 14 16 (3,4) Không 3 4 5 17 (1,3) Chọn 18 (2,3) Chọn. Dừng vì đã 20 (2,4) đủ cạnh. 33 (1,2) 20
21. 8.4. Xác định cây tối đại ngắn nhất 2 4 2 4 33 20 8 8 1 18 9 6 1 18 16 9 6 17 17 14 3 5 3 4 5 21
22. 8.4. Xác định cây tối đại ngắn nhất  E = {AD, DE, EB, AC, CC, FC, AF, CE, AB, BC, 5 DB} 16 D  Trọng lượng: 32 12 B 10 A 5 6 7 F 15 9 E C 10 8 Nguyễn Văn Hiệu, 2012, Discrete Mathematics 22
23. 8.4. Xác định cây tối đại ngắn nhất  E = ? 8 5  Trọng lượng = ? 10 2 3 18 12 30 16 14 4 26 Nguyễn Văn Hiệu, 2012, Discrete Mathematics 23
24. 8.4. Xác định cây tối đại ngắn nhất Cài đặt Graph Graph::MST_Kruskal() { //Tìm cây tối đại ngắn nhất của đồ thị có trọng } Nguyễn Văn Hiệu, 2012, Discrete Mathematics 24
25. 8.4. Xác định cây tối đại ngắn nhất Nhược điểm thuật toán Hướng tiếp cạnh  Thuật toán Kruskal làm việc  Sử dụng thuật toán Prim kém hiệu quả đối với những đồ thị dày.  Đồ thị có số cạnh m n(n 1)/2. Nguyễn Văn Hiệu, 2012, Discrete Mathematics 25
26. 8.4. Xác định cây tối đại ngắn nhất Prim Prim Input: 1. Chọn tùy ý v X và khởi tạo Đồ thị liên thông G=(X, E), V := { v }; U := ; X gồm N đỉnh 2. Chọn cạnh e có trọng lượng nhỏ nhất trong các cạnh (w, Output: v) mà w X\V và v V Cây tối đại ngắn nhất 3. V := V  {w}; U := U  {e} T=(V, U) của G 4. Nếu U đủ N-1 cạnh thì dừng, ngược lại lặp từ bước 2. Nguyễn Văn Hiệu, 2012, Discrete Mathematics 26
27. 8.4. Xác định cây tối đại ngắn nhất • 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. Nguyễn Văn Hiệu, 2012, Discrete Mathematics 27
28. 8.4. Xác định cây tối đại ngắn nhất f f 10 20 10 20 15 e 15 e a 9 a 9 3 3 15 b 15 10 d b 10 5 d 8 5 8 c c Nguyễn Văn Hiệu, 2012, Discrete Mathematics
29. 8.4. Xác định cây tối đại ngắn nhất  E = ?  Trọng lượng = ? 8 5 10 2 3 18 12 30 16 14 4 26 Nguyễn Văn Hiệu, 2012, Discrete Mathematics 29
30. 8.4. Xác định cây tối đại ngắn nhất Cài đặt Graph Graph::MST_Prim() { //Tìm cây tối đại ngắn nhất của đồ thị có trọng } Nguyễn Văn Hiệu, 2012, Discrete Mathematics 30
31. Bài tập 1. Chứng minh các định lý tương đương 2. Xác định số lượng cây tối đại của đồ thị dạng CÂY, CHU TRÌNH SƠ CẤP, ĐỦ, 3. Chứng minh tính đúng đắn của các giải thuật PRIM, KRUSKAL Nguyễn Văn Hiệu, 2012, Discrete Mathematics 31
32. Bài tập - Kruskal
33. Bài tập - Prim
34. 8.5. Cây có gốc Định nghĩa  CÂY CÓ HƯỚNG là đồ thị có hướng mà đồ thị nền của nó là một cây. G1  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. G2  Chú ý: Trong cây có gốc thì gốc 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. Nguyễn Văn Hiệu, 2012, Discrete Mathematics 34
35. 8.5. Cây có gốc  Trong một cây có gốc  Cây có gốc thường được thì v là đỉnh mức k khi vẽ như trong hình dưới và chỉ khi đường đi từ đây để làm rõ mức của gốc đến v có độ dài các đỉnh. 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. Nguyễn Văn Hiệu, 2012, Discrete Mathematics 35
36. 8.5.Cây có gốc Định nghĩa Định nghĩa  Cây T có gốc v0. Giả sử v0,  Một cây có gốc T gọi là CÂY m- PHÂN nếu mỗi đỉnh của T v1, , vn là một đường đi trong T. Ta gọi: có nhiều nhất là m con.  Cây có gốc T gọi là CÂY m- . vi+1 là con của vi và vi là cha PHÂN ĐẦY ĐỦ nếu mỗi đỉnh . v0, v1, , vn-1 là các tổ tiên của trong của T đều có m con. vn . Đỉnh treo vn là đỉnh không có con; đỉnh treo cũng gọi là lá hay đỉnh ngoài; . Đỉnh không là lá gọi đỉnh trong. Nguyễn Văn Hiệu, 2012, Discrete Mathematics 36
37. 8.5. Cây có gốc Mệnh đề 1 Ví dụ  Một cây m-phân đầy đủ có t  Minh họa bài toán chuyển đỉnh trong thì có m*t+1 thư đỉnh và có (m 1)*t +1 lá.  Gọi T là một cây nhị phân đủ với N nút trong và có chiều cao h. Chứng minh rằng: h ≥ log2(N + 1) • Hướng dẫn: ai (0 ≤ i ≤ h) là số nút 0 trong ở mức i. Ta có: a0 ≤ 2 ; ai ≤ 2ai-1 Nguyễn Văn Hiệu, 2012, Discrete Mathematics 37
38. 8.5. Cây có gốc Mệnh đề 1 Mệnh đề 2  Một cây m-phân đầy đủ có t  Một cây m-phân có chiều đỉnh trong thì có m*t+1 cao h thì có nhiều nhất là đỉnh và có (m 1)*t +1 lá. mh lá.  Minh họa bài toán chuyển  Một cây m-phân có l lá thì thư có chiều cao h [logml]. Nguyễn Văn Hiệu, 2012, Discrete Mathematics 38
39. Tóm lại Các khái niệm và tính chất về cây và cây tối đại Thuật toán Kruskal Thuật toán Prim Khái niệm và tính chât về cây có gốc Nguyễn Văn Hiệu, 2012, Discrete Mathematics 39
40. THAT’S ALL; THANK YOU What NEXT? BÀI TOÁN TỐI ƯU TRÊN ĐỒ THỊ