Bài giảng Lý thuyết đồ thị - Chương 6: Cây và cây khung đồ thị

Nội dung text: Bài giảng Lý thuyết đồ thị - Chương 6: Cây và cây khung đồ thị

1. Chương 6 Cây và cây khung đồ thị
2. 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ụ:
3. 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.
4. 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: Vt V Et E là một cây thì T sẽ được gọi là cây khung của đồ thị G.
5. Cây khung đồ thị (tt) ⚫ Ví dụ: Đồ thị G Cây khung T1 Cây khung T2
6. Bài toán cây khung cực tiểu – Trong 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( u , v )→ min (*) (,)u v Et – Cây khung thỏa mãn (*) được gọi là cây khung cực tiểu của G.
7. Cây khung cực tiểu (tt) ⚫ Ví dụ: Đồ thị G Cây khung cực tiểu T* với c(T*)min = 18
8. Giải thuật Kruskal ⚫ Bướ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: T = ⚫ Bước 2: while(|T|<n&& DS ) do – Chọn (u,v) là cạnh có trọng số nhỏ nhất trong DS. – Nếu T{,} u v không tạo chu trình thì: T= T{,} u v – Loại (u,v) khỏi DS: DS= DS\{( u , v )} ⚫ 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.
9. Giải thuật Kruskal (tt) ⚫ Ví dụ: tìm cây khung Cạnh Trọng số Chọn cực tiểu của ĐT sau: (2,4) 1 X (2,5) 1 X (4,5) 1 (5,6) 2 X (4,6) 3 (3,4) 5 X (1,3) 11 X (1,2) 12
10. Giả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*) = 20
11. Giải thuật Prim – Định nghĩa khoảng cách từ 1 đỉnh v đến cây T: 0, vT dv[],= nếu từ v không có bất kỳ cạnh nào nối đến T min{c ( v , u ), u T
12. Giả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.
13. Giải thuật Prim (tt) voidPr im (int x ) { d[][,] v= a x v for() v V do truoc[] v= x U= V\{} x T = while() U  do { get v U: d [ v ] = min{ d [ u ],  u U } T= T{( truoc [ v ], v )} U= U\{} v for( u  U ke ( v )) do d[][,] u= a v u if( d [ u ] a [ v , u ]) truoc[] u= v } }
14. 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.
15. Giải thuật Prim (tt) 1 2 3 4 5 6 0 0,1 12,1 11,1 ,1 ,1 ,1 1 5,3 2 1,4 1,4 3,4 3 1,4 4 2,5 5 Bảng nhãn thể hiện giải thuật Prim