Bài giảng Toán rời rạc - Chương 6: Cây và cây khung đồ thị

Chương 6Cây và cây khung đồ thịCây và các tính chấtĐịnh nghĩa:Cây là đơn đồ thị vô hướng, liên thông và không có chu trình.Ví dụ:Cây và các tính chất (tt)Định lý: Cho đồ thị vô hướng T(V,E) với n đỉnh. Khi đó các phát biểu sau đây là tương đương:1. T là một cây.2. T không có chu trình và có đúng (n-1) cạnh.3. T liên thông và có đúng (n-1) cạnh.4. T liên thông và mọi cạnh đều là cầu.5. Giữa 2 đỉnh bất kỳ (phân biệt) có đúng 1 đường đi đơn.6. T không có chu trình nhưng nếu bổ sung vào T đúng 1 cạnh thì thu được đúng 1 chu trình.Cây khung đồ thịĐịnh nghĩa: Cho đồ thị vô hướng liên thông G(V,E). Khi đó: nếu T(Vt,Et) với:là một cây thì T sẽ được gọi là cây khung của đồ thị G.Cây khung đồ thị (tt)Ví dụ:Đồ thị GCây khung T1Cây khung T2Bài toán cây khung cực tiểuTrong trường hợp G(V,E) là đồ thị vô hướng liên thông có trọng số thì với mỗi cây khung T của nó ta tính được c(T) là tổng trọng số của cây khung T. Bài toán đặt ra là:Cho đồ thị G(V,E) vô hướng liên thông, có trọng số. Hãy tìm cây khung T*(V,Et) của nó sao cho:Cây khung thỏa mãn (*) được gọi là cây khung cực tiểu của G.Cây khung cực tiểu (tt)Ví dụ:Đồ thị GCây khung cực tiểu T* với c(T*)min = 18Giải thuật KruskalBước 1:Sắp xếp danh sách cạnh DS của G tăng dần theo trọng số.Khởi tạo:Bước 2: while(|T|<n&&	) doChọn (u,v) là cạnh có trọng số nhỏ nhất trong DS.Nếu 	không tạo chu trình thì:Loại (u,v) khỏi DS:Bước 3:Nếu DS rỗng thì ĐT không liên thông.Ngược lại thì T là cây khung cực tiểu.Giải thuật Kruskal (tt)Ví dụ: tìm cây khung cực tiểu của ĐT sau:CạnhTrọng sốChọn(2,4)1X(2,5)1X(4,5)1(5,6)2X(4,6)3(3,4)5X(1,3)11X(1,2)12Giải thuật Kruskal (tt)Vậy cây khung cực tiểu tìm được là:Với tổng trọng số c(T*) = 20Giải thuật PrimĐịnh nghĩa khoảng cách từ 1 đỉnh v đến cây T:nếu từ v không có bất kỳ cạnh nào nối đến TGiải thuật Prim (tt)Tư tưởng: Cho ĐT G(V,E).Khởi đầu từ cây nhỏ nhất: T chỉ gồm 1 đỉnh và 0 cạnh.Trong mỗi bước lặp, một đỉnh mới v “gần” T nhất sẽ được kết nạp vào T (cùng với cạnh nối v đến đỉnh của T).Quá trình sẽ kết thúc khi T có n đỉnh và n-1 cạnh.Giải thuật Prim (tt)Giải thuật Prim (tt)Ví dụ: tìm cây khung cực tiểu của ĐT sau, chọn đỉnh xuất phát là 1.Giải thuật Prim (tt)12345 600,112,111,1 ,1 ,1 ,11--5,3----21,41,43,431,4--42,55Bảng nhãn thể hiện giải thuật Prim