Bài toán rời rạc: Câ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 ...
Nội dung trích xuất từ tài liệu:
Bài toán rời rạc: Cây 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 * 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ó baonhiêu đỉnh bậc 1? 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ẽ đượcxế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 haykhô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 chutrình và có ít nhất 2 đỉnh. Trong đơn đồ thị liên thông, giữa 2 đỉnh bất kì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ànhphầ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). Mặt khác, trong một cây, ngoài các đỉnh treo thì tất cả các đỉnh cònlại đều là đỉnh cắt.Một cây chứa ít nhất 2 đỉnh treo, do đó số đỉnh cắt lớnnhấ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 khuvự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ốicùng, đội D đứng thứ tư. Xếp hạng các đội là: Vô địch :B Nhì :A Ba :C Tư :D 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à ...