Bài giảng Tin học - Chương 11: Cây Và Một Số Ứng Dụng

CHƯƠNG 11CÂY VÀ MỘT SỐ ỨNG DỤNG 1NỘI DUNGKhái niệm câyCây bao trùmCây bao trùm nhỏ nhấtCây bao trùm lớn nhấtCây phân cấpCây nhị phânCây biểu thứcCây mã tối ưu211.1. KHÁI NIỆM CÂYKhá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.3VÍ DỤ 11.1Đồ thị dưới đây là một cây.abcdefgHình 11.1. Cây 7 đỉnh411.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:T là một cây.T không có chu trình và có n - 1 cạnh.T liên thông và có n - 1 cạnh.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. 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.Chỉ có duy nhất một đường đi nối hai đỉnh bất kỳ.511.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.611.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.711.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ênthông. Trái với điều 5). 811.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).  911.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.10VÍ DỤ 11.2Đồ thị G:Một số cây bao trùm của G:adbecHình 11.2. Đồ thị có cây bao trùmadbecadbecHình 11.3. Hai cây bao trùm của đồ thị G1111.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. 1211.2. CÂY BAO TRÙM (tiếp)aD0D1D2. . . Hình 11.4. Cách xây dựng cây bao trùm 1311.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 là đường đi ngắn nhất nối a với x thì là đường đi ngắn nhất nối a với y và y  Di-1.	1411.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. 1511.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.1611.3. THUẬT TOÁN TÌM CÂY BAO TRÙMThuậ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.1711.3. THUẬT TOÁN TÌM CÂY BAO TRÙM (tiếp)Thuật toán1 procedure CBT_S (v) ;2 begin3 Duyet [v] := true ; 4 for u  DK[v] do5 if ! Duyet [u] then6 begin T := T  {(v, u)} ; CBT_S (u) end 7 end ;1811.3. THUẬT TOÁN TÌM CÂY BAO TRÙM (tiếp)8 BEGIN { Chương trình chính }9	 for u  V do Duyet [u] := false ;10	 T :=  ; CBT_S (z) ; { z là đỉnh tuỳ ý của đồ thị, sẽ trở thành gốc của cây }12 END.1911.3. THUẬT TOÁN TÌM CÂY BAO TRÙM (tiếp)Tính đúng đắn của thuật toán: :Khi ta thêm cạnh (v, u) vào tập cạnh T thì trong đồ thị	 (V, T) đã có đường đi từ z tới v. Vậy thuật toán xây dựng lên đồ thị liên thông.2. Mỗi cạnh mới (v, u) được thêm vào tập T có đỉnh v đã 	được duyệt và đỉnh u đang duyệt. Vậy đồ thị đang được xây dựng không có chu trình.Theo tính chất của phép duyệt theo chiều sâu, thủ tục CBT_S thăm tất cả các đỉnh của đồ thị liên thông G. 2011.3. THUẬT TOÁN TÌM CÂY BAO TRÙM (tiếp)Do vậy, đồ thị do thuật toán xây dựng là một cây bao trùm của đồ thị đã cho. Độ phức tạp của thật toán là: O(n+m).21VÍ DỤ 11.3Áp dụng thuật toán trên cho đồ thị (nét mảnh) ta nhận được cây bao trùm (nét đậm) như sau: 812345679 Hình 11.5. Cây bao trùm của đồ thị tìm theo phương pháp duyệt theo chiều sâu2211.3. THUẬT TOÁN TÌM CÂY BAO TRÙM (tiếp)Thuật toán 11.2 (Tìm cây bao trùm bằng phương pháp duyệt theo chiều rộng)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.2311.3. THUẬT TOÁN TÌM CÂY BAO TRÙM (tiếp)Thuật toán1 BEGIN 2 for u  V do Duyet [u] := false ;3 T :=  ; 4 Q :=  ; enqueue z into Q ; { z là đỉnh tuỳ ý của đồ thị và là gốc của cây }6 Duyet [z] := true ;2411.3.THUẬT TOÁN TÌM CÂY BAO TRÙM (tiếp)7 while Q   do8 begin deqưeue v from Q ;9 for u  DK[v] do10 if ! Duyet [u] then11 begin enqueue u into Q ; 12 Duyet [u] := true ; 13 T := T  {(v, u)} end 14 end END. 2511.3. THUẬT TOÁN TÌM CÂY BAO TRÙM (tiếp) Độ phức tạp của thuật toán: O(m+n).Ví dụ: Áp dụng thuật toán trên cho đồ thị (nét mảnh) ta nhận được cây bao trùm (nét đậm) như sau:12345679 Hình 11.6. Cây bao trùm của đồ thị tìm theo phương pháp duyệt theo chiều rộng26