›
›

Toán học - Bài 8: Cây & Cây tối đại

pdf 40 trang Đức Chiến 03/01/2024 1760
Download
Bạn đang xem 20 trang mẫu của tài liệu "Toán học - Bài 8: Cây & Cây tối đại", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pdftoan_hoc_bai_8_caycay_toi_dai.pdf

Nội dung text: Toán học - Bài 8: Cây & Cây tối đại

  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Ị