Bài giảng Lý thuyết đồ thị: Chương 11 - PGS.TS. Hoàng Chí Thành

Bài giảng Lý thuyết đồ thị: Chương 11 Cây và một số ứng dụng, cung cấp cho người đọc những kiến thức như: 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; Cây nhị phân; Cây biểu thức; Cây mã tối ưu. 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 Lý thuyết đồ thị: Chương 11 - PGS.TS. Hoàng Chí Thành CHƯƠNG 11 CÂY VÀ MỘT SỐ ỨNG DỤNG 1 NỘI DUNG 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 Cây nhị phân Cây biểu thức Cây mã tối ưu 2 11.1. KHÁI NIỆM CÂY Khái niệm cây do Cayley đưa ra vào năm 1857. Định nghĩa: 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: - liên thông, - không có chu trình. 3 VÍ DỤ 11.1 Đồ thị dưới đây là một cây. b a c d e f g Hình 11.1. Cây 7 đỉnh 4 11.1. KHÁI NIỆM CÂY (tiếp) Định lý 11.1: Cho T là đồ thị vô hướng có số đỉnh không ít hơn 2. Khi đó các khẳng định sau là tương đương: 1. T là một cây. 2. T không có chu trình và có n - 1 cạnh. 3. T liên thông và có n - 1 cạnh. 4. T không có chu trình nhưng nếu thêm một cạnh bất kỳ nối hai đỉnh không kề nhau thì có chu trình. 5. T liên thông nhưng nếu bớt đi một cạnh bất kỳ thì sẽ mất tính liên thông. 6. Chỉ có duy nhất một đường đi nối hai đỉnh bất kỳ. 5 11.1. KHÁI NIỆM CÂY (tiếp) Chứng minh: Chú ý rằng đồ thị T không có chu trình khi và chỉ khi chu số của nó bằng 0, nghĩa là: m = n - p. 1)  2) : Vì p = 1 và m = n - p suy ra: m = n - 1. 2)  3) : m = n - p, m = n - 1 cho nên p = 1. 3)  4) : p = 1, m = n - 1 suy ra: m = n - p. Vậy thì c(T) = 0, đồ thị T không có chu trình. Thêm một cạnh vào thì m tăng thêm 1 còn n, p không đổi. Khi đó chu số c(T) = m - n + p = 1. Đồ thị có một chu trình. 6 11.1. KHÁI NIỆM CÂY (tiếp) Chứng minh: 4)  5) : c(T) = 0 nên m = n - p. Phản chứng: đồ thị T không liên thông, có ít nhất hai đỉnh a, b không liên thông. Thêm cạnh (a, b) vào đồ thị vẫn không có chu trình. Mâu thuẫn với điều 4). Vậy đồ thị phải liên thông, nghiã là p = 1. Suy ra: m = n - 1. Khi bớt đi một cạnh bất kỳ, đồ thị vẫn không có chu trình. Do đó m - 1 = n - p'. Suy ra p' = 2 và đồ thị mất tính liên thông. 7 11.1. KHÁI NIỆM CÂY (tiếp) Chứng minh: 5)  6) : Đồ thị T liên thông nên có đường đi đơn nối mỗi cặp đỉnh. Giả sử cặp đỉnh a, b được nối bằng hai đường đi đơn khác nhau. Khi đó có cạnh e thuộc đường đi này nhưng không thuộc đường đi kia. Ta bỏ cạnh e này đi, đồ thị vẫn liên thông. Trái với điều 5). 8 11.1. KHÁI NIỆM CÂY (tiếp) Chứng minh: 6)  1) : Suy ra đồ thị T liên thông. Phản chứng: T có chu trình. Vậy thì giữa hai đỉnh của chu trình có thể nối bằng hai đường đơn khác nhau. Mâu thuẫn với điều 6). 9 11.2. CÂY BAO TRÙM Định nghĩa 11.2 Giả sử G là một đồ thị vô hướng. Cây T được gọi là cây bao trùm của đồ thị G nếu T là một đồ thị riêng của G. 10 VÍ DỤ 11.2 Đồ thị G: a b c d e Hình 11.2. Đồ thị có cây bao trùm Một số cây bao trùm của G: a b a b c c d e d e Hình 11.3. Hai cây bao trùm của đồ thị G 11 11.2. CÂY BAO TRÙM (tiếp) Định lý 11.2: Đồ thị vô hướng G có cây bao trùm  G liên thông. Chứng minh: : Hiển nhiên, vì cây bao trùm liên thông suy ra G liên thông. : Chọn a là một đỉnh bất kỳ trong đồ thị G. Ký hiệu: d(x) là khoảng cách giữa a và đỉnh x. Xây dựng các tập đỉnh: D0 = {a}, Di = { x  d(x) = i } với i  1. 12 11.2. CÂY BAO TRÙM (tiếp) a D0 D1 D2 ... Hình 11.4. Cách xây dựng cây bao trùm 13 11.2. CÂY BAO TRÙM (tiếp) Chú ý: Mỗi đỉnh x thuộc Di (i  1) đều có đỉnh y thuộc Di-1 sao cho (x, y) là một cạnh, vì nếu < a, ... , y, x > là đường đi ngắn nhất nối a với x thì < a, ... , y > là đường đi ngắn nhất nối a với y và y  Di-1. 14 11.2. CÂY BAO TRÙM (tiếp) Chứng minh: Lập tập cạnh T như sau: Với mỗi đỉnh x của đồ thị G, x  Di với i  1, ta lấy cạnh nào đó nối x với một đỉnh trong Di-1. Tập cạnh này sẽ tạo nên một đồ thị riêng của G với n đỉnh và n - 1 cạnh. Đồ thị riêng này liên thông vì mỗi đỉnh đều được nối với đỉnh a. Theo tính chất 3) của cây thì T là một cây. Do vậy, T là cây bao trùm của đồ thị G. 15 11.2. CÂY BAO TRÙM (tiếp) Định lý 11.3 (Borchardt): Số cây bao trùm của một đồ thị vô hướng đầy đủ n đỉnh là nn – 2. Một số thuật toán tìm cây bao trùm: - Thuật toán sử dụng phương pháp duyệt theo chiều sâu. - Thuật toán sử dụng phương pháp duyệt theo chiều rộng. 16 11.3. THUẬT TOÁN TÌM CÂY BAO TRÙM Thuật toán 11.1 (Tìm cây bao trùm bằng phương pháp duyệt theo chiều sâu) Dữ liệu: Biểu diễn mảng DK các danh sách kề của đồ thị vô hướng G. Kết quả: Cây bao trùm (V, T) của đồ thị G. 17 11.3. THUẬT TOÁN TÌM CÂY BAO TRÙM (tiếp) Thuật toán 1 procedure CBT_S (v) ; 2 begin 3 Duyet [ ...