›
›

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

ppt 33 trang ngocly 3180
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Lý thuyết đồ thị - Chương 2: Cây", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pptbai_giang_ly_thuyet_do_thi_chuong_2_cay.ppt

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

  1. CÂY ntsonptnk@gmail.com
  2. ĐỊNH NGHĨA • CÂY là đồ thị liên thơng và khơng cĩ chu trình • RỪNG là một đồ thị gồm p thành phần liên thơng, trong đĩ mỗi A B thành phần liên thơng là một cây • Lưu ý: cây khơng chứa khuyên và cạnh song song. D C Lý thuyết đồ thị - chương 2 – Nguyễn Thanh Sơn
  3. SỰ TỒN TẠI ĐỈNH TREO Định lý: Một cây T gồm N đỉnh với N 2 chứa ít nhất hai đỉnh treo D A B F E C Lý thuyết đồ thị - Nguyễn Thanh Sơn
  4. CÁC ĐỊNH NGHĨA TƯƠNG ĐƯƠNG Xét đồ thị G gồm N đỉnh, các điều sau đây tương đương. 1.Đồ thị G là cây. 2.Giữa hai đỉnh bất kỳ của G, tồn tại duy nhất một dây chuyền nối chúng với nhau. 3.G liên thơng tối tiểu. 4.Thêm một cạnh nối 2 đỉnh bất kỳ của G thì G sẽ chứa một chu trình duy nhất. 5.G liên thơng và cĩ n-1 cạnh 6.G khơng cĩ chu trình và cĩ n-1 cạnh Lý thuyết đồ thị - Nguyễn Thanh Sơn
  5. CÂY TỐI ĐẠI • Định nghĩa: Cho G=(X, E) là một đồ thị liên thơng và T=(X, F) là một đồ thị bộ phận của G. Nếu T là cây thì T được gọi là một cây tối đại của G. • Các tên gọi khác: cây khung, cây bao trùm, cây phủ D A B F E C Lý thuyết đồ thị - Nguyễn Thanh Sơn
  6. SỰ TỒN TẠI CỦA CÂY TỐI ĐẠI • Định lý: Mọi đồ thị liên thơng đều cĩ chứa ít nhất một cây tối đại D A B F E C Lý thuyết đồ thị - Nguyễn Thanh Sơn
  7. XÁC ĐỊNH CÂY TỐI ĐẠI Thuật tốn tựa PRIM Input: đồ thị liên thơng G=(X, E), X gồm N đỉnh Output: cây tối đại T=(V, U) của G 1.Chọn tùy ý v X và khởi tạo V := { v }; U := ; 2.Chọn w X \ V sao cho e E, e nối w với một đỉnh trong V 3.V := V {w}; U := U {e} 4.Nếu U đủ N-1 cạnh thì dừng, ngược lại lặp từ bước 2. Lý thuyết đồ thị - Nguyễn Thanh Sơn
  8. XÁC ĐỊNH CÂY TỐI ĐẠI D A B F E C V = {F, A, B, E, C, D} U = {FA, AB, BE, FC, ED} Lý thuyết đồ thị - Nguyễn Thanh Sơn
  9. CÂY TỐI ĐẠI NGẮN NHẤT Định nghĩa: Cho G=(X, E) 1.G được gọi là ĐỒ THỊ CĨ TRỌNG nếu mỗi cạnh của G được tương ứng với một số thực, nghĩa là cĩ một ánh xạ như sau: L: E |R e | L(e) 1.TRỌNG LƯỢNG của một cây T của G bằng với tổng trọng lượng các cạnh trong cây: L(T) = (e T)L(e) 1.CÂY TỐI ĐẠI NGẮN NHẤT là cây tối đại cĩ trọng lượng nhỏ nhất của G Lý thuyết đồ thị - Nguyễn Thanh Sơn
  10. MA TRẬN TRỌNG LƯỢNG • Trong các thuật tốn tìm cây tối đại ngắn nhất chúng ta cĩ thể bỏ đi hướng các cạnh và các khuyên; đối với các cạnh song song thì cĩ thể bỏ đi và chỉ để lại một cạnh trọng lượng nhỏ nhất trong chúng. Vì vậy đồ thị cĩ thể biểu diễn bằng MA TRẬN TRỌNG LƯỢNG LNxN được qui ước như sau: o ●Lij = trọng lượng cạnh nhỏ nhất nối i đến j (nếu cĩ) o ●Lij = nếu khơng cĩ cạnh nối i đến j Lý thuyết đồ thị - Nguyễn Thanh Sơn
  11. MA TRẬN TRỌNG LƯỢNG 5 16 D A 12 B 6 7 5 15 E C 10 Lý thuyết đồ thị - Nguyễn Thanh Sơn
  12. XÁC ĐỊNH CÂY TỐI ĐẠI NGẮN NHẤT Thuật tốn PRIM Input: đồ thị liên thơng G=(X, E), X gồm N đỉnh Output: cây tối đại ngắn nhất T=(V, U) của G 1.Chọn tùy ý v X và khởi tạo V := { v }; U := ; 2.Chọn cạnh e cĩ trọng lượng nhỏ nhất trong các cạnh (w, v) mà w X\V và v V 3.V := V {w}; U := U {e} 4.Nếu U đủ N-1 cạnh thì dừng, ngược lại lặp từ bước 2. Lý thuyết đồ thị - Nguyễn Thanh Sơn
  13. THUẬT TỐN PRIM 5 16 D A 12 B 10 6 F 7 5 15 9 E C 10 8 V = {F, C, A, D, E, B} U = {FC, CA, AD, DE, EB} Trọng lượng: 32 Lý thuyết đồ thị - Nguyễn Thanh Sơn
  14. THUẬT TỐN PRIM - nháp 5 5 D A 5 B 5 5 F 5 5 5 5 E C 5 5 Lý thuyết đồ thị - Nguyễn Thanh Sơn
  15. XÁC ĐỊNH CÂY TỐI ĐẠI NGẮN NHẤT Thuật tốn KRUSKAL Input: đồ thị G=(X, E) liên thơng, X gồm N đỉnh Output: cây tối đại ngắn nhất T=(V, U) của G 1.Sắp xếp các cạnh trong G tăng dần theo trọng lượng; khởi tạo T := . 2.Lần lượt lấy từng cạnh e thuộc danh sách đã sắp xếp. Nếu T+{e} khơng chứa chu trình thì kết nạp e vào T: T := T+{e}. 3.Nếu T đủ N-1 cạnh thì dừng; ngược lại, lặp bước 2. Lý thuyết đồ thị - Nguyễn Thanh Sơn
  16. THUẬT TỐN KRUSKAL 5 16 D A 12 B 10 6 F 7 15 15 9 E C 10 8 E = {AD, DE, EB, AC, CC, FC, AF, CE, AB, BC, DB} Trọng lượng: 32 Lý thuyết đồ thị - Nguyễn Thanh Sơn
  17. THUẬT TỐN TỰA PRIM – CÀI ĐẶT Graph Graph::SpanningTree() { //Tìm cây khung của đồ thị } Lý thuyết đồ thị - Nguyễn Thanh Sơn
  18. THUẬT TỐN PRIM – CÀI ĐẶT Graph Graph::MST_Prim() { //Tìm cây tối đại ngắn nhất của đồ thị cĩ trọng } Lý thuyết đồ thị - Nguyễn Thanh Sơn
  19. THUẬT TỐN KRUSKAL – CÀI ĐẶT Graph Graph::MST_Kruskal() { //Tìm cây tối đại ngắn nhất của đồ thị cĩ trọng } Lý thuyết đồ thị - Nguyễn Thanh Sơn
  20. ĐỒ THỊ CĨ GỐC Định nghĩa: Cho đồ thị cĩ hướng G=(X, E). Ta nĩi G là một ĐỒ THỊ CĨ GỐC nếu tồn tại đỉnh r X sao cho từ r cĩ đường đi đến v, v X G1 G2 Lý thuyết đồ thị - Nguyễn Thanh Sơn
  21. ĐỒ THỊ LIÊN THƠNG MẠNH Định nghĩa: Cho đồ thị cĩ hướng G=(X, E). Ta nĩi G là ĐỒ THỊ LIÊN THƠNG MẠNH khi và chỉ khi i,j X luơn tồn tại đường đi từ i đến j và đường đi từ j đến i. G1 G2 Lý thuyết đồ thị - Nguyễn Thanh Sơn
  22. ĐỒ THỊ TỰA LIÊN THƠNG MẠNH Định nghĩa: Cho đồ thị cĩ hướng G=(X, E). Ta nĩi G là ĐỒ THỊ TỰA LIÊN THƠNG MẠNH khi và chỉ khi i, j X, k X sao cho cĩ đường đi từ k đến i và cĩ đường đi từ k đến j. G1 G2 Lý thuyết đồ thị - Nguyễn Thanh Sơn
  23. ĐỒ THỊ TỰA LIÊN THƠNG MẠNH • Nhận xét: G=(X, E) là đồ thị cĩ hướng: G cĩ gốc G tựa liên thơng mạnh G liên thơng • Định lý: với G=(X, E) là đồ thị cĩ hướng hữu hạn, ta cĩ: G cĩ gốc G tựa liên thơng mạnh Lý thuyết đồ thị - Nguyễn Thanh Sơn
  24. CÂY CĨ HƯỚNG (CÂY NGỒI) Định nghĩa: Cho G=(X, E) là đồ thị cĩ hướng liên thơng. G được gọi là cây cĩ hướng nếu: 1. a)G khơng cĩ chu trình, 2. b)G cĩ gốc. G1 G2 Lý thuyết đồ thị - Nguyễn Thanh Sơn
  25. CÂY CĨ HƯỚNG Lưu ý: • ●Chu trình cĩ thể khơng quan tâm đến hướng của các cạnh. • ●Cây cĩ hướng cũng là cây. • ●Cần phân biệt cây trong LTĐT và cây trong các giáo trình khác Lý thuyết đồ thị - Nguyễn Thanh Sơn
  26. CÂY CĨ HƯỚNGCÁC ĐỊNH NGHĨA TƯƠNG ĐƯƠNG Cho đồ thị cĩ hướng G=(X, E) gồm N đỉnh. Các điều sau đây tương đương với nhau. 1.G là một cây cĩ hướng. 2. r X thỏa v X, cĩ một đường đi duy nhất từ r đến v. 3.G tựa liên thơng mạnh tối tiểu. 4.G liên thơng và cĩ đỉnh r sao cho: d-(r)=0 và d-(i)=1, i X\{r}. 1.G khơng cĩ chu trình và cĩ đỉnh r sao cho: d-(r)=0 và d-(i)=1, i X\{r}. Lý thuyết đồ thị - Nguyễn Thanh Sơn
  27. CÂY CĨ HƯỚNGCÁC ĐỊNH NGHĨA TƯƠNG ĐƯƠNG 1.G tựa liên thơng mạnh và khơng cĩ chu trình. 2.G tựa liên thơng mạnh và cĩ N-1 cạnh. Lưu ý: • ●r trong các định nghĩa trên là duy nhất và được gọi là gốc của cây cĩ hướng. • ●Mỗi đỉnh i X cĩ duy nhất một đỉnh j mà cạnh liên kết với (j, i) hướng vào i, đỉnh j được gọi đỉnh cha của I. • ●Nếu đỉnh x X thỏa điều kiện d+(x)=0 thì x được gọi là lá của cây cĩ hướng. Lý thuyết đồ thị - Nguyễn Thanh Sơn
  28. CÂY CĨ HƯỚNG Định lý: Cho G là đồ thị cĩ hướng. 1.Nếu G cĩ chứa một đồ thị bộ phận là cây cĩ hướng thì G tựa liên thơng mạnh. 2.Nếu G tựa liên thơng mạnh thì G cĩ chứa một đồ thị bộ phận là cây cĩ hướng. Nếu G tựa liên thơng mạnh, T là một cây cĩ hướng là đồ thị bộ phận G thì T cũng được gọi là cây cĩ hướng tối đại của G. Lý thuyết đồ thị - Nguyễn Thanh Sơn
  29. MA TRẬN KIRCHOFF Định nghĩa: Cho đồ thị cĩ hướng G=(X, E) gồm N đỉnh. Ma trận KIRCHOFF là ma trận KNxN được định nghĩa như sau: d-(i) nếu i=j Kij = -Bij nếu i j (Bij làphần tử ở dịng i cột j của ma trận kề) Lý thuyết đồ thị - Nguyễn Thanh Sơn
  30. MA TRẬN KIRCHOFF 1 2 4 3 Lý thuyết đồ thị - Nguyễn Thanh Sơn
  31. ĐỊNH LÝ KIRCHOFF Định lý: Giả sử G là đồ thị cĩ hướng đơn, N đỉnh, N-1 cạnh cĩ ma trận Kirchoff là K. • Gọi K(1, 1) là ma trận cĩ được từ ma trận K bằng cách bỏ đi dịng 1 và cột 1, • khi đĩ G là cây ngồi cĩ gốc tại đỉnh 1 X khi và chỉ khi det K(1, 1)=1. Lý thuyết đồ thị - Nguyễn Thanh Sơn
  32. ĐỊNH LÝ KIRCHOFF 1 2 4 3 Lý thuyết đồ thị - Nguyễn Thanh Sơn
  33. BÀI TẬP 1.Chứng minh các định lý tương đương 2.Xác định số lượng cây tối đại của đồ thị dạng CÂY, CHU TRÌNH SƠ CẤP, ĐỦ, 3.Chứng minh tính đúng đắn của các giải thuật PRIM, KRUSKAL GV: Dương Anh Đức