Bài toán rời rạc: Cây

Chia sẻ: Hân Bá | Ngày: | Loại File: DOC | Số trang:24

1
497
lượt xem
230
download

Bài toán rời rạc: Cây

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

Tài liệu tham khảo về vẽ cây trong toán rời rạc. Đề: Tìm tối đa các đỉnh của một cây m-phân có chiều cao h. Giải: Cây m-phân có chiều cao h. Vậy trong cây này, các đỉnh sẽ được xếp vào h+1 mức ...

Chủ đề:
Lưu

Nội dung Text: Bài toán rời rạc: Cây

  1. BÀI TẬP TOÁN RỜI RẠC ---&0&--- CHƯƠNG 5: CÂY Giảng viên : Nguyễn Mậu Hân Sinh viên thực hiện : Nguyễn Thị Diệu Hằng Lớ p : TinK30D
  2. * Bài 1: Vẽ tất cả các cây ( không đẳng cấu ) có: a) 4 đỉnh b) 5 đỉnh c) 6 đỉnh Lời giải: a) b) * Bài 2: Một cây có n2 đỉnh bậc 2, n3 đỉnh bậc 3, ..., nk đỉnh bậc k. Hỏi có bao nhiêu đỉnh bậc 1?
  3. Lời giải: Gọi n1: số đỉnh bậc 1 của cây. Ta có: - Số đỉnh của cây: n1+n2+n3+...+nk - Số cạnh của cây: n1+n2+n3+...+nk-1 - Số bậc của cây: n1+2.n2+3.n3+...+k.nk Cây là một đồ đơn đồ thị, do vậy, nó sẽ có tổng bậc bằng 2 lần số cạnh. Tức là: n1+2.n2+3.n3+...+k.nk=2(n1+n2+n3+...+nk-1) n1= n3+2n4+...+(k-2)nk+2 * Bài 3: Tìm số tối đa các đỉnh của một cây m-phân có chiều cao h. Lời giải: Cây m-phân có chiều cao h. Vậy trong cây này, các đỉnh sẽ được xếp vào h+1mức(từ mức 0đến mức h).Số đỉnh của cây chính là tổng các đỉnh trong các mức này . Ta có: Giá trị max của: - Số đỉnh thuộc mức 0: 1 =m0 (do chỉ có 1 đỉnh gốc) - Số đỉnh thuộc mức 1: m = m1 - Số đỉnh thuộc mức 2: m.m= m2 - Số đỉnh thuộc mức 3: m.m.m= m3 - ... - Số đỉnh thuộc mức h: mh Suy ra: Số đỉnh tối đa của cây m-phân có chiều cao h là: h 1+m +m +m +...+m = ∑mi 1 2 3 h i=0 * Bài 4: Có thể tìm được một cây có 8 đỉnh và thỏa điều kiện dưới đây hay không? Nếu có, vẽ ra, nếu không, giải thích tại sao: a) Mọi đỉnh đều có bậc 1. b) Mọi đỉnh đều có bậc 2. c) Có 6 đỉnh bậc 2 và 2 đỉnh bậc 1. d) Có đỉnh bậc 7 và 7 đỉnh bậc 1. Lời giải: a) Không có. Giải thích: Cây là một đơn đồ thị liên thông, không chứa chu trình và có ít nhất 2 đỉnh. Trong đơn đồ thị liên thông, giữa 2 đỉnh bất kì
  4. luôn tồn tại đường đi giữa chúng nên trong cây sẽ chứa một số đỉnh có bậc khác 1. b) Không có. Giải thích: Ta có: Nếu T là một cây có n đỉnh thì T có ít nhất 2 đỉnh treo( có bậc 1). Vậy, không thể tìm ra một cây có mọi đỉnh đều có bậc 2. c) Có. Ví dụ: d) Có. Ví dụ: * Bài 5: Chứng minh hoặc bác bỏ các mệnh đề sau: a) Trong một cây, đỉnh nào cũng là đỉnh cắt b) Một cây có số đỉnh không nhỏ hơn 3 thì có nhiều đỉnh cắt hơn là cầu. Lời giải: a) Trong một cây, đỉnh nào cũng là đỉnh cắt. Mệnh đề trên sai. Trong một cây luôn có ít nhất 2 đỉnh treo và đỉnh treo không phải là đỉnh cắt(do khi xóa nó và cạnh liền kề với nó thì không tạo ra nhiều thành phần lên thông hơn). b) Một cây có số đỉnh không nhỏ hơn 3 thì có nhiều đỉnh cắt hơn là cầu. Mệnh đề trên sai. Cho một cây T có n đỉnh. Trong một cây, mỗi cạnh đều là cầu. Như vậy, số cầu của T là n-1( do trong T có n-1 cạnh).
  5. Mặt khác, trong một cây, ngoài các đỉnh treo thì tất cả các đỉnh còn lại đều là đỉnh cắt.Một cây chứa ít nhất 2 đỉnh treo, do đó số đỉnh cắt lớn nhất có thể có là n-2 Số cầu = n-1 Số đỉnh cắt ≤ n-2 Vậy, trong một cây, cầu có nhiều hơn đỉnh cắt. * Bài 6: Có 4 đội bóng đá A, B, C, D lọt vào vòng bán kết giải đội mạnh khu vực. Có mấy dự đoán xếp hạng như sau: - Đội B vô địch, đội D nhì. - Đội B nhì, đội C ba. - Đội A nhì, đội C tư. Biết rằng mỗi dự đoán trên đúng về một đội. Hãy cho biết kết quả xếp hạng của các đội. Lời giải: Theo đề ra thì mỗi dự đoán đúng về một đội. Giả sử ở dự đoán đầu tiên: B vô địch, D nhì thì dự đoán về D đúng.Vậy D nhì. Ở dự đoán 2: B nhì, C ba.Do D nhì nên dự đoán B nhì không đúng → C ba đúng. Ở dự đoán 3: A nhì, C tư.Do C đứng thứ ba nên dự đoán C tư sai → A nhì( vô lý, do dự đoán D nhì là đúng) Vậy ở dự đoán đầu tiên, dự đoán B vô địch đúng.B vô địch nên ở dự đoán 2, dự đoán đội C ba đúng, và ở dự đoán thứ 3 đội A nhì đúng, và cuối cùng, đội D đứng thứ tư. Xếp hạng các đội là: Vô địch :B Nhì :A Ba :C Tư :D
  6. B vô địch C ba A nhì Dự đoán D nhì C ba A nhì Vô lí * Bài 7: Cây Fibonacci có gốc Tn được định nghĩa bằng hồi quy như sau: T1 và T2 đều là cây có gốc chỉ gồm 1 đỉnh; với n=2, 3, 4... thì cây có gốc Tn được xây dựng từ gốc với Tn-1 như là cây con bên trái và Tn-2 như cây con bên phải. a) Hãy vẽ 7 cây Fibonacci có gốc đầu tiên b) Cây Fibonacci Tn có bao nhiêu đỉnh, lá và bao nhiêu đỉnh trong. Chiều cao của nó bằng bao nhiêu? Lời giải: a) 7 cây Fibonacci có gốc đầu tiên:
  7. T1 T2 T3 T4 T5 T6
  8. T7 b) Gọi li, ni và ti lần lượt là số lá, đỉnh và đỉnh trong của cây Fibonacci Ti(i≥3), hi là chiều cao. Ta có: li = li-1 + li-2 ni = ni-1 + ni-2 + 1 t i = ni - l i hi = hi-1 + 1 Trường hợp riêng: l1 = l2 = 1 n1 = n2 = 1 h1 = h2 = 0 * Bài 8: Hãy tìm cây khung của đồ thị sau bằng cách xóa đi các cạnh trong các chu trình đơn: a) a b c d e f g h i j
  9. a b c d e g f i j h k l Lời giải: Có nhiều cây khung có thể được tạo ra bằng cách xóa đi các cạnh trong các chu trình đơn. Sau đây là một số ví dụ: a) a b c d e f g h i j a b c d e f g h i j
  10. a b c d e f g h i j b) a b c d e g f i j h k l a b c d e g f i j h k l
  11. * Bài 9: Hãy tìm cây khung cho mỗi đồ thị sau: a) K5 b) K4,4 c) K1,6 d) Q3 e) C5 f) W5 Lời giải: a) K5 b) K4,4
  12. c) K1,6 K1,6 Bản thân K1,6 là một cây khung. d) Q3 e) C5
  13. f) W5 * Bài 10: Đồ thị Kn với n=3, 4, 5 có bao nhiêu cây khung không đẳng cấu Lời giải: K3: có 1 cây khung K4: có 2 cây khung( không đẳng cấu ) K5:
  14. * Bài 11: Tìm cây khung nhỏ nhất của đồ thị sau theo thuật toán Kruskal và Prim: 42 a b 4 10 14 3 3 1 11 c d e f 5 20 9 15 7 g h Lời giải: + Giải theo thuật toán Kruskal: Thứ tự của các cạnh sắp xếp theo thứ tự không giảm: (d,e), (b,f), (c,d), (a,c), (d,g), (g,h), (h,f), (a,e), (e,f), (b,e), (c,g), (d,h), (a,b) Bắt đầu từ đồ thị rỗng T có 6 đỉnh. - Thêm vào T cạnh (d,e)→ số cạnh của T là 1
  15. + Giải theo thuật toán Prim: Ta có ma trận trọng số của đồ thị trên là: a b c d e f g h a ∞ 42 4 ∞ 10 ∞ ∞ ∞ b 42 ∞ ∞ ∞ 14 3 ∞ ∞ c 4 ∞ ∞ 3 ∞ ∞ 15 ∞ d ∞ ∞ 3 ∞ 1 ∞ 5 20 e 10 14 ∞ 1 ∞ 11 ∞ ∞ f ∞ 3 ∞ ∞ 11 ∞ ∞ 9 g ∞ ∞ 15 5 ∞ ∞ ∞ 7 h ∞ ∞ ∞ 20 ∞ 9 7 ∞ V.lặp a b c d e f g h VT ET K.Tạ - [a,42 [a,4 ∞ [a,10 ∞ ∞ ∞ a Ø o ] ] ] 1 - [a,42 - [c,3] [a,10 ∞ [c,15] ∞ a, c (a,c) ] ] 2 - [a,42 - - [d,1] ∞ [d,5] [d,20] a,c,d (a,c),(c,d) ] 3 - [e,14] - - - [e,11] [d,5] [d,20] a,c,d,e (a,c),(c,d) (d,e) 4 - [e,14] - - - [e,11] - [g,7] a,c,d,e,g (a,c),(c,d) (d,e),(d,g) 5 - [e,14] - - - [h,9] - - a,c,d,e,g,h (a,c),(c,d) (d,e),(d,g), (g,h) 6 - [f,3] - - - - - - a,c,d,e,g,h,f (a,c),(c,d) (d,e),(d,g), (g,h),(h,f) 7 - - - - - - - - a,c,d,e,g,h,f,b (a,c),(c,d) (d,e),(d,g), (g,h),(h,f), (f,b) Vậy cây khung nhỏ nhất của đồ thị trên có độ dài là: 4+3+1+5+7+9+3=32 Cây khung với tập cạnh: E={(a,c),(c,d)(d,e),(d,g),(g,h),(h,f),(f,b)} * Bài 12:
  16. Tìm cây khung nhỏ nhất bằng thuật toán Prim của đồ thị gồm các đỉnh A, B, C, D, E, F, H, I được cho bởi ma trận trọng số sau: A B C D E F H I A ∞ 16 15 23 19 18 32 20 B 16 ∞ 13 33 24 20 19 11 C 15 13 ∞ 13 29 21 20 19 D 23 33 13 ∞ 22 30 21 12 E 19 24 29 22 ∞ 34 23 21 F 18 20 21 30 34 ∞ 17 14 H 32 19 20 21 23 17 ∞ 18 I 20 11 19 12 21 14 18 ∞ Yêu cầu viết kết quả trung gian trong từng bước lặp, kết quả cuối cùng cần đưa ra tập cạnh và độ dài của cây khung nhỏ nhất. Lời giải: A B C D E F H I VT ET - [A,16] [A,15] [A,23] [A,19] [A,18] [A,32] [A,20] A Ø - [C,13] - [C,13] [A,19] [A,18] [C,20] [C,19] A,C (A,C) - - - [C,13] [A,19] [A,18] [B,19] [B,11] A,C,B (A,C),(C,B) - - - [I,12] [A,19] [I,14] [I,18] - A,C,B,I (A,C),(C,B) (B,I) - - - - [A,19] [I,14] [I,18] - A,C,B,I,D (A,C),(C,B) (B,I),(I,D) - - - - [A,19] - [F,17] - A,C,B,I,D,F (A,C),(C,B) (B,I),(I,D), (I,F) - - - - [A,19] - - - A,C,B,I,D,F,H (A,C),(C,B) (B,I),(I,D), (I,F),(F,H) - - - - - - - - A,C,B,I,D,F,H,E (A,C),(C,B) (B,I),(I,D), (I,F),(F,H), (A,E) Độ dài cây khung nhỏ nhất tìm được: 15+13+11+12+14+17+19=101 Tập cạnh của cây khung nhỏ nhất: E={(A,C),(C,B)(B,I),(I,D),(I,F),(F,H),(A,E)} * Bài 13: Duyệt các cây sau đây lần lượt bằng các thuật toán tiền thứ tự, trung thứ tự và hậu thứ tự:
  17. a) a b c f d e h g i j b) a b c d e f g h i j k l m n o p q Lời giải: a) * Duyệt theo tiền thứ tự: 1. Thăm a. 2. Duyệt T(b): 2.1. Thăm b. 2.2. Duyệt T(d): Thăm d. 2.3. Duyệt T(e): 2.3.1. Duyệt T(g): Thăm g. 3. Duyệt c:
  18. 3.1. Thăm c 3.2. Duyệt T(f): 3.2.1. Thăm f 3.2.2. Duyệt T(h): 3.2.2.1. Thăm h 3.2.2.2. Duyệt T(i): Thăm i 3.2.2.3. Duyệt T(j): Thăm j Kết quả duyệt cây theo tiền thứ tự là: a, b, d, e, g, c, f, h, i, j * Duyệt theo trung thứ tự: 1. Duyệt T(b): 1.1. Duyệt T(d): Thăm d 1.2. Thăm b 1.3. Duyệt T(e): 1.3.1. Duyệt T(g): Thăm g 1.3.2. Thăm e 2.Thăm a 3. Duyệt T(c): 3.1. Thăm c 3.2 Duyệt T(f): 3.1.1. Duyệt T(h): 3.1.1.1. Duyệt T(i): Thăm i 3.1.1.2. Thăm h 3.1.1.3. Duyệt T(j): Thăm j Kết quả duyệt cây theo trung thứ tự: d, b, g, e, a, c, i, h, j, f * Duyệt theo hậu thứ tự: 1. Duyệt T(b): 1.1. Duyệt T(d): Thăm d 1.2. Duyệt T(e): 1.2.1. Duyệt T(g): Thăm g 1.2.2. Thăn e 1.3. Thăm b 2. Duyệt T(c): 2.1.Duyệt T(f): 2.1.1. Duyệt T(h): 2.1.1.1. Duyệt T(i): Thăm i 2.1.1.2. Duyệt T(j): Thăm j
  19. 2.1.1.3.Thăm h 2.1.2.Thăm f 2.2. Thăm c 3. Thăm a Kết quả duyệt cây theo hậu thứ tự: d,g, e, b, i, j, h, f, c, a b) * Duyệt theo tiền thứ tự: 1. Thăm a 2. Duyệt T(b): 2.1. Thăm b 2.2. Duyệt T(d): Thăm d 2.3. Duyệt T(e): 2.3.1. Thăm e 2.3.2. Duyệt T(g): Thăm g 3. Duyệt T(c): 3.1. Thăm c 3.2. Duyệt T(f): 3.2.1. Thăm f 3.2.2. Duyệt T(h): 3.2.2.1. Thăm h 3.2.2.2. Duyệt T(i): Thăm i 3.2.2.3. Duyệt T(j): Thăm j Kết quả duyệt cây theo tiền thứ tự: a, b, d, e, g, c, f, h, i, j * Duyệt cây theo trung thứ tự: 1. Duyệt T(b): 1.1. Duyệt T(d): 1.1.1. Duyệt T(h): Thăm h 1.1.2. Thăm d 1.1.3. Duyệt T(i): 1.1.3.1. Duyệt T(m): Thăm m 1.1.3.2. Thăm i 1.1.3.3. Duyệt T(n): 1.1.3.3.1. Duyệt T(p): Thăm p 1.1.3.3.2. Thăm n 1.1.3.3.3. Duyệt T(q): Thăm q 1.2. Thăm b
  20. 1.3. Duyệt T(e): Thăm e 2.Thăm a 3. Duyệt T(c): 3.1. Duyệt T(f): 3.1.1. Duyệt T(j): Thăm j 3.1.2. Thăn f 3.1.3. Duyệt T(k): 3.1.3.1. Duyệt T(o): Thăm o 3.1.3.2. Thăm k 3.2. Thăm c 3.3. Duyệt T(g): 3.3.1. Thăm g 3.3.2. Duyệt T(l): Thăm l Kết quả duyệt cây theo trung thứ tự: h, d, m, i, p, n, q, b, e, a, j, f, o, k, c, g, l * Duyệt cây theo hậu thứ tự: 1. Duyệt T(b): 1.1. Duyệt T(d): 1.1.1. Duyệt T(h): Thăm h 1.1.2. Duyệt T(i): 1.1.2.1. Duyệt T(m): Thăm m 1.1.2.2. Duyệt T(n): 1.1.2.2.1. Duyệt T(p): Thăm p 1.1.2.2.2. Duyệt T(q): Thăm q 1.1.2.2.3.Thăm n 1.1.2.3. Thăm i 1.1.3. Thăm d 1.2. Duyệt T(e): Thăm e 1.3. Thăm b 2. Duyệt T(c): 2.1. Duyệt T(f): 2.1.1. Duyệt T(j): Thăm j 2.1.2. Duyệt T(k): 2.1.2.1. Duyệt T(o): Thăm o 2.1.2.2. Thăm k 2.1.3. Thăm f 2.2. Duyệt T(g): 2.2.1. Duyệt T(l): Thăm l 2.2.2. Thăm g
Đồng bộ tài khoản