Bài giảng Toán rời rạc: Cây và một số ứng dụng của cây - ThS. Hoàng Thị Thanh Hà

Bài giảng Toán rời rạc - Cây và một số ứng dụng của cây, được biên soạn gồm các nội dung chính sau: Khái niệm cây; Cây bao trùm; Cây bao trùm nhỏ nhất; Cây bao trùm lớn nhất; Cây phân cấp; Duyệt cây; Cây nhị phân. Mời các bạn cùng tham khảo!
Nội dung trích xuất từ tài liệu:
Bài giảng Toán rời rạc: Cây và một số ứng dụng của cây - ThS. Hoàng Thị Thanh Hà NỘI DUNG Toán rời rạc (6): 1. Khái niệm cây 2. Cây bao trùm CÂY VÀ MỘT SỐ ỨNG 3. Cây bao trùm nhỏ nhất Cây bao trùm lớn nhất DỤNG CỦA CÂY 4. 5. Cây phân cấp 6. Duyệt cây Ts. Hoàng Thị Thanh Hà Khoa Thống kê –Tin học 7. Cây nhị phân Trường Đại học Kinh tế 1. Cây biểu thức 2. Cây mã tiền tố 30/10/2012 1 30/10/2012 2 1. KHÁI NIỆM CÂY 1. VÍ DỤ 1Khái niệm cây do Cayley đưa ra vào năm 1857. Ví dụ: Rừng sau có 3 cây: Định nghĩa 1: Giả sử T = (V, E) là một đồ thị vô hướng. T là một cây nếu nó thỏa mãn hai tính chất sau: i m - liên thông, a d - không có chu trình. c f g h j l Cây không có chu trình nên không có khuyên, không có cạnh bội, nên ta quy ước Đồ thị vô hướng chính là b e đơn đồ vo hướng k n Một đồ thị vô hướng không chứa chu trình và có ít nhất hai đỉnh gọi là một rừng. Trong một rừng, mỗi thành phần liên thông là một cây. 30/10/2012 3 30/10/2012 4 1. KHÁI NIỆM CÂY (tiếp) 1. KHÁI NIỆM CÂY (tiếp)Định lý 1: Cho T là đồ thị vô hướng có số đỉnh không Chứng minh: 1)⇒2) Chỉ cần chứng minh rằng ⇒ít hơn 2. Khi đó các khẳng định sau là tương đương: một cây có n đỉnh thì có n−1 cạnh. Ta chứng 1) T là một cây. minh bằng quy nạp. Điều này hiển nhiên khi 2) T liên thông và có n−1 cạnh. n=2. Giả sử cây có k đỉnh thì có k−1 cạnh, ta 3) T không chứa chu trình và có n−1 cạnh. chứng minh rằng cây T có k+1 đỉnh thì có k 4) T liên thông và mỗi cạnh là cầu. cạnh. Thật vậy, trong T nếu ta xoá một đỉnh 5) Giữa hai đỉnh phân biệt bất kỳ của T luôn có duy treo và cạnh treo tương ứng thì đồ thị nhận nhất một đường đi sơ cấp. được là một cây k đỉnh, cây này có k−1 cạnh, 6) T không chứa chu trình nhưng khi thêm một cạnh theo giả thiết quy nạp. Vậy cây T có k cạnh. mới thì có được một chu trình duy nhất. 30/10/2012 5 30/10/2012 6 1 1. KHÁI NIỆM CÂY (tiếp) 1. KHÁI NIỆM CÂY (tiếp)Chứng minh: 2)⇒3) Nếu T có chu trình thì bỏ đi một cạnh ⇒ Chứng minh:4)⇒5) Vì T liên thông nên giữa hai đỉnh ⇒ phân biệt bất kỳ của T luôn có một đường đi sơ cấp, trong chu trình này thì T vẫn liên thông. Làm lại như nhưng không thể đư ...