BÀI 18_Chương 11: Cây và một số ứng dụng

Trong chương này ta xét một dạng đặc biệt nhưng có nhiều ứng dụng của đồ thị vô hướng. Đó là khái niệm cây. 11.1. Cây Khái niệm cây được Cayley đưa ra đầu tiên vào năm 1857. Định nghĩa 11.1: Giả sử T = (V, E) là đồ thị vô hướng. Ta nói rằng đồ thị T là một cây nếu nó liên thông và không có chu trình. Ví dụ 11.2: Đồ thị dưới đây là một cây. Kết quả dưới đây sẽ cho chúng ta một số tính chất lý thú và có thể dùng làm...
Nội dung trích xuất từ tài liệu:
BÀI 18_Chương 11: Cây và một số ứng dụng BÀI 18 Chương 11 Cây và một số ứng dụng Trong chương này ta xét một dạng đặc biệt nhưng có nhiều ứng dụng của đồthị vô hướng. Đó là khái niệm cây.11.1. Cây Khái niệm cây được Cayley đưa ra đầu tiên vào năm 1857.Định nghĩa 11.1: Giả sử T = (V, E) là đồ thị vô hướng. Ta nói rằng đồ thị T làmột cây nếu nó liên thông và không có chu trình.Ví dụ 11.2: Đồ thị dưới đây là một cây. Hình 11.1. Cây 7 đỉnh Kết quả dưới đây sẽ cho chúng ta một số tính chất lý thú và có thể dùng làmđịnh nghĩa cho cây.Định lý 11.1. Với đồ thị vô hướng T có số đỉnh không ít hơn 2, các tính chất sauđây 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 nối hai đỉnh bất kỳ không kềnhau thì xuất hiện một 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. Mỗi cặp đỉnh được nối với nhau bằng đúng một đường đi đơn.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ì chu số của đồ thị 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 = m - n + p = 1. Đồ thị có một chu trình.4) ⇒ 5) : c = 0 nên m = n - p. Giả sử ngược lại, đồ thị T không liên thông. Thế thì có ít nhất hai đỉnh a, bkhông liên thông. Khi thêm cạnh (a, b) vào đồ thị vẫn không làm xuất hiện chutrì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.Thế thì p = 2 và đồ thị mất tính liên thông.5) ⇒ 6) : Vì đồ thị T liên thông nên mỗi cặp đỉnh đều có đường đi đơn nối chúng.Giả sử cặp đỉnh a, b được nối bằng hai đường đi đơn khác nhau. Khi đó có cạnh ethuộ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).6) ⇒ 1) : Suy ra đồ thị T liên thông.Giả sử 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). 11.2. Cây bao trùm của đồ thị Giả sử G là một đồ thị vô hướng.11.2.1. Cây bao trùmĐịnh nghĩa 11.3: 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.Ví dụ 11.4: Đồ thị G được cho như hình vẽ dưới đây. Hình 11.2. Đồ thị có cây bao trùmvà một số cây bao trùm của G là: Hình 11.3. Hai cây bao trùm của đồ thị trên Cây bao trùm có nhiều ứng dụng trong các bài toán điều khiển giao thông, nốicác mạng điện …Định lý 11.2: Đồ thị vô hướng G có cây bao trùm khi và chỉ khi 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à độ dài của đường đi ngắn nhất nối đỉnh a với đỉnh x.Lần lượt xây dựng các tập hợp D0 = {a} Di = {x⏐d(x) = i} với i ≥ 1. Hình 11.4. Cách xây dựng cây bao trùmChú ý: Mỗi đỉnh x thuộc Di (i ≥ 1) đều có đỉnh y thuộc Di-1 sao cho (x, y) là mộtcạ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. Ta lập tập cạnh T như sau: Với mỗi đỉnh x của đồ thị G, thì x ∈ Di với i ≥ 1,ta lấy một 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. Định lý 11.3 (Cayley): Số cây bao trùm của đồ thị vô hướng đầy đủ n đỉnh là nn-2. Kết quả trên cho ta thấy số lượng cây bao trùm của một đồ thị nói chung làrất lớn. Các thuật toán duyệt đồ thị theo chiều rộng và chiều sâu là những công cụ tốtđể tìm cây bao trùm của đồ thị liên thông.Thuật toán 11.4 (Tìm cây bao trùm của đồ thị liên thông bằng phương pháp duyệttheo 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.1 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 ;8 BEGIN { Chương trình chính }9 for u ∈ V do Duyet [u] := false ;10 T := ∅ ;11 CBT_S (z) ; { z là đỉnh tuỳ ý của đồ thị, sẽ trở thành gốc của cây }12 END.Tính đúng đắn của thuật toán được suy từ 3 tính chất sau đây: Khi ta thêm cạnh (v,u) vào tập ...