Bài giảng Lí thuyết đồ thị - Chương 4: Cây - Trần Quốc Việt

Nội dung text: Bài giảng Lí thuyết đồ thị - Chương 4: Cây - Trần Quốc Việt

1. 05/11/2013 Bài giảng: Chương 4 LÝ THUYẾT ĐỒ THỊ (GRAPH THEORY) (Tree) TRẦN QUỐC VIỆT 1 2 1. Định nghĩa và các tính chất cơ bản 1. Định nghĩa và các tính chất cơ bản Định nghĩa: Cây (Tree) còn gọi là cây tự do (free tree) là Định lý 1: Giữa 2 đỉnh bất kỳ trong cây T luôn có một và chỉ đột đồ thị vô hướng liên thông và không có chu trình một đường đi trong T nối chúng C/m: Xét 2 đỉnh x, y bất kỳ trong T (x≠y) Ví dụ: T1 và T2 sau đây là 2 cây Do T liên thông nên có đường đi nối x và y Giả sử có ít nhất 2 đường đi khác nhau giữa và y: p1: x=v0,v1, ,vi, ,vk1, ,vj,vj+1, ,y p2: x=v0,v1, ,vi, ,vk2, ,vj,vj+1 ,y vk1 v1 vj Vj+1 y Tồn tại chu trình x=v0 vi (mâu thuẫn với gt) v 4 T1 T2 2 1
2. 05/11/2013 Định nghĩa và các tính chất cơ bản (tt) Định nghĩa và các tính chất cơ bản (tt) Định nghĩa: Cây có gốc (rooted tree) là một cây có hướng, Xét xây có gốc T trên đó đã chọn một đỉnh là gốc (root) của cây và các cạnh định - Mức của đỉnh: Khoảng cách từ gốc đến nút đó hướng sao cho với mọi đỉnh luôn có một đường đi từ gốc đến - Chiều cao của cây: Mức lớn nhất của một đỉnh bất kỳ đỉnh đó root Mức 0 Một cây tự do có thể x root Ví dụ: Mức 1 chọn một đỉnh bất kỳ làm y gốc để trở thành cây có gốc Mức 2 root Mức 3 Chiều cao của cây - Nếu (xy) là cạnh của T: ta gọi x đỉnh cha (parent) của y, y là đỉnh con (child) của x - Lá (leaves): Những đỉnh không có cây con. - Đỉnh trong (internal vertices): là những đỉnh có ít nhất 1 cây Cây có gốc con Định nghĩa và các tính chất cơ bản (tt) Định nghĩa và các tính chất cơ bản (tt) Định nghĩa: Tập hợp các cây đôi một không có đỉnh chung Định lý 2: Nếu một cây có n đỉnh thì sẽ có m=n-1 cạnh gọi là một rừng (Forest) C/m: Ta chọn một nút làm gốc để được cây có gốc • Với cây chỉ có 1 đỉnh (n=1), số cạnh là 0, nghĩa là: m=n-1 • Giả sử cây có k đỉnh thì có k-1 cạnh là đúng, • Xét cây có k+1 đỉnh và xét một đỉnh lá v bất kỳ, nếu loại bỏ v cùng với cạnh nối đến v (chỉ có duy nhất 1 cạnh nối đến v), đồ thị T’ còn lại cũng là một cây có k đỉnh T’ có k-1 cạnh T có k một rừng (forest): gồm nhiều cây không có đỉnh chung cạnh Mọi đỉnh x trong một cây mà là gốc của một cây con, • Theo nguyên lý quy nạp, “một cây có n đỉnh thì sẽ có m=n-1 Khi xóa đỉnh x khỏi cây ta được một rừng cạnh” đúng với mọi n (n>=1) 8 2
3. 05/11/2013 Định nghĩa và các tính chất cơ bản (tt) Định nghĩa và các tính chất cơ bản (tt) Ví dụ: Định nghĩa (độ lệch tâm):Xét xây có gốc T - Độ lệch tâm (eccentricity) của đỉnh v: là Khoảng cách lớn nhất từ v đến đỉnh bất kỳ trong T. Kí hiệu E(v) E(v)  (u,v) Cây có 11 đỉnh có 11-1=10 cạnh max u T root E(x)=? x v E(v)=? 9 Định nghĩa và các tính chất cơ bản (tt) Định nghĩa và các tính chất cơ bản (tt) Xét xây có gốc T Cho cây có gốc T: - Đỉnh có độ lệch tâm nhỏ nhất gọi là tâm (center) của T . Nếu số con tối đa của một đỉnh - Độ lệch tâm của tâm gọi là bán kính (radius) của T trong T là m và có ít nhất một Ví dụ: Cho cây T đỉnh đúng m con thì T gọi là cây root m-phân (m-ary tree) Xác định tâm của T? Xác định bán kính của T? . Nếu mọi đỉnh trong của T đều có Cây tam phân x v đúng m cây con thì T gọi là cây m-phân đủ (complete m-ary tree) . Cây m-phân với m=2 gọi là cây nhị phân Cây nhị phân đủ12 3
4. 05/11/2013 Định nghĩa và các tính chất cơ bản (tt) C/m định lý 3 Định lý 3 (Định lý Daisy Chain): T là một đồ thị có n đỉnh, các mệnh đề sau là tương đương (i) T là cây (ii) T không có chu trình và có n-1 cạnh (iii) T Liên thông và nếu hủy bất kỳ một cạnh nào trong T thì T sẽ mất tính liên thông (iv) Giữ 2 đỉnh bất kỳ trong T luôn tồn tại duy nhất một đường đi nối chúng (v) T không có chu trình, nếu thêm 1 cạnh bất kỳ nối 2 đỉnh trong T thì T sẽ có chu trình (vi) T liên thông và có n-1 cạnh 13 14 Định nghĩa và các tính chất cơ bản (tt) Định nghĩa và các tính chất cơ bản (tt) Định lý 4: Một cây tự do có nhiều nhất 2 tâm Định lý 5: Định lý 5: Một cây m-phân đầy đủ có i đỉnh trong thì (i) Một cây m-phân có chiều cao h thì có nhiều nhất là mh có mi+1 đỉnh lá Hệ luận: T là một cây m-phân đầy đủ (ii) Một cây m-phân có l lá thì có chiều cao h ≥[logml] (i) T có i đỉnh trong T có l = (m-1)i+1 lá (iii) Một cây m-phân đầy đủ, cân bằng có l lá thì có chiều (ii) T có l lá T có I = (l-1)/(m-1) đỉnh trong cao h=[logml] và n = (ml-1)/(m-1) đỉnh (i) T có n đỉnh T có i = (n-1)/m đỉnh trong và l = [(m-1)n+1)]/m nút lá 15 16 4
5. 05/11/2013 2. Các phương pháp duyệt cây 2. Các phương pháp duyệt cây Xét cây có gốc T, gọi Tr1, Tr2, ,Trklần lượt là các cây con của nút r 2.1. Duyệt cây theo thứ tự trước (preoder) theo thứ tự từ trái qua phải - Thăm gốc r của T - Đệ quy: Duyệt từng cây con lần lượt từ T1 đến Trk theo r thứ tự trước Ví dụ: Kết quả duyệt theo Preorder? T T1 2 Tk 17 18 2. Các phương pháp duyệt cây 2. Các phương pháp duyệt cây 2.2. Duyệt cây theo thứ tự giữa (inoder) 2.3. Duyệt cây theo thứ tự sau (postorder) - Duyệt Tr1 theo thứ tự giữa - Duyệt Tr1 theo postorder, duyệt Tr2 theo postorder, , - Thăm r duyệt Trk theo postorder - Thăm r - Duyệt Tr2theo thứ tự giữa, , duyệt Trk theo thứ tự giữa Ví dụ: Kết quả duyệt theo Inorder? Ví dụ: Kết quả duyệt theo postorder? 19 20 5
6. 05/11/2013 Cây bao trùm(spanning tree) Cây bao trùm(spanning tree) Cho đồ thị vô hướng G. Cây T gọi là một cây bao trùm Định lý: của G nếu T≤G và T chứa mọi đỉnh của G Đồ thị G có cây bao trùm  G liên thông D Ví dụ: 4 4 4 B 3 3 3 2 2 2 A 5 1 5 1 5 1 D C B A 8 8 8 6 6 6 C 7 7 7 H liên thông H có 21 G không liên thông G không có cây bao trùm 22 G Một cây bao trùm của G cây bao trùm Tìm cây bao trùm theo phương pháp Tìm cây bao trùm – DFS (Depth First Search) Bước 1: Chọn một đỉnh bất kỳ v của G làm điểm xuất Hai phương pháp: phát (gốc) của T. Bước 2:Xác định một đường đi sơ cấp xuất phát từ v qua các đỉnh G nhưng T, cho đến khi không Tìm theo chiều sâu (DFS: Depth First Search) thể đi tiếp. Gọi k là đỉnh kết thúc đường đi. Đặt đường đi này vào T rồi quay trở về đặt đỉnh liền Tìm theo chiều rộng (BFS: Breadth First Search) trước k làm điểm xuất phát. Lập lại thủ tục này cho đến khi mọi đỉnh của G đều nằm trong T. 24 6
7. 05/11/2013 Tìm cây bao trùm theo phương pháp Tìm cây bao trùm theo phương pháp – DFS (Depth First Search) – DFS (Depth First Search) DFS(G: Liên thông với các đỉnh v1,v2, ,vn) 4 4 3 3 2 2 { T=Cây chỉ gồm 1 đỉnh v1 visit(v1) } 1 5 1 5 Visit(v: đỉnh của G) 8 8 { For (mỗi đỉnh w kề với v nhưng chưa có trong T) - Thêm đỉnh w và cạnh (v,w) vào T 6 6 7 7 visit(w); } 9 9 25 26 Tìm cây bao trùm theo phương pháp Tìm cây bao trùm theo phương pháp – DFS (Depth First Search) – DFS (Depth First Search) 1 2 3 4 5 6 7 1 2 3 4 5 6 7 2 2 1 0 1 1 0 0 0 1 1 0 1 1 0 0 0 1 2 1 0 1 1 0 1 0 2 1 0 1 1 0 1 0 3 3 6 3 1 1 0 1 0 0 1 6 3 1 1 0 1 0 0 1 1 1 4 4 0 1 1 0 0 1 1 4 4 0 1 1 0 0 1 1 5 0 0 0 0 0 0 1 5 0 0 0 0 0 0 1 6 0 1 0 1 0 0 0 6 0 1 0 1 0 0 0 7 5 7 1 0 1 1 1 0 0 7 5 7 1 0 1 1 1 0 0 v=1; T= với VT={1}, ET= w=2, a12 0  2 VT,VT={1,2},ET={(1,2)} 27 28 7
8. 05/11/2013 Tìm cây bao trùm theo phương pháp Tìm cây bao trùm theo phương pháp – DFS (Depth First Search) – DFS (Depth First Search) 1 2 3 4 5 6 7 2 1 2 3 4 5 6 7 2 1 0 1 1 0 0 0 1 1 0 1 1 0 0 0 1 2 1 0 1 1 0 1 0 2 1 0 1 1 0 1 0 3 3 3 3 1 1 0 1 0 0 1 6 1 1 0 1 0 0 1 6 1 1 4 0 1 1 0 0 1 1 4 4 0 1 1 0 0 1 1 4 5 0 0 0 0 0 0 1 5 0 0 0 0 0 0 1 6 0 1 0 1 0 0 0 6 0 1 0 1 0 0 0 7 1 0 1 1 1 0 0 7 5 7 1 0 1 1 1 0 0 7 5 w=4, a34 0  4 VT,VT={1,2,3,4},ET={(1,2),(2,3),(3,4)} w=3, a23 0  3 VT,VT={1,2,3},ET={(1,2),{2,3)} 29 30 Tìm cây bao trùm theo phương pháp Tìm cây bao trùm theo phương pháp – DFS (Depth First Search) – DFS (Depth First Search) 1 2 3 4 5 6 7 2 1 2 3 4 5 6 7 2 1 0 1 1 0 0 0 1 1 0 1 1 0 0 0 1 2 1 0 1 1 0 1 0 2 1 0 1 1 0 1 0 3 3 3 1 1 0 1 0 0 1 6 3 1 1 0 1 0 0 1 6 1 1 4 0 1 1 0 0 1 1 4 4 0 1 1 0 0 1 1 4 5 0 0 0 0 0 0 1 5 0 0 0 0 0 0 1 6 0 1 0 1 0 0 0 6 0 1 0 1 0 0 0 7 1 0 1 1 1 0 0 7 5 7 1 0 1 1 1 0 0 7 5 V=4 V=4 w=6, a46 0  6 VT,VT={1,2,3,4,6},ET={(1,2),(2,3),(3,4),(4,6)} W=7, a47 0  7 VT,VT={1,2,3,4,6,7},ET={(1,2),(2,3),(3,4),(4,6),(4,7)} 31 32 8
9. 05/11/2013 Tìm cây bao trùm theo phương pháp Tìm cây bao trùm theo phương pháp – DFS (Depth First Search) – DFS (Depth First Search) 1 2 3 4 5 6 7 2 1 2 3 4 5 6 7 2 1 0 1 1 0 0 0 1 1 0 1 1 0 0 0 1 2 1 0 1 1 0 1 0 2 1 0 1 1 0 1 0 3 3 3 1 1 0 1 0 0 1 6 3 1 1 0 1 0 0 1 6 1 1 4 0 1 1 0 0 1 1 4 4 0 1 1 0 0 1 1 4 5 0 0 0 0 0 0 1 5 0 0 0 0 0 0 1 6 0 1 0 1 0 0 0 6 0 1 0 1 0 0 0 7 1 0 1 1 1 0 0 7 5 7 1 0 1 1 1 0 0 7 5 V=4 V=7 W=7, a47 0  7 VT,VT={1,2,3,4,6,7},ET={(1,2),(2,3),(3,4),(4,6),(4,7)} W=5, a75 0  5 VT,VT={1,2,3,4,6,7,5},ET={(1,2),(2,3),(3,4),(4,6), (4,7),(7,5)} 33 Mọi cạnh của G đều có trong T, dừng 34 Tìm cây bao trùm theo phương pháp Tìm cây bao trùm theo phương pháp – DFS (Depth First Search) – DFS (Depth First Search) Cây bao trùm tìm được 1 2 3 4 5 6 7 2 1 0 1 1 0 0 0 1 2 1 0 1 1 0 1 0 3 6 3 1 1 0 1 0 0 1 1 4 4 0 1 1 0 0 1 1 0 0 0 0 0 0 1 5 0 1 0 1 0 0 0 6 7 5 7 1 0 1 1 1 0 0 35 36 9
10. 05/11/2013 Tìm cây bao trùm theo phương pháp Tìm cây bao trùm theo phương pháp – BFS (Breadth First Search) – BFS (Breadth First Search) 1) Chọn 1 đỉnh bất kỳ của G làm đỉnh xuất phát (gốc) của BFS(G: liên thông với tập đỉnh v1,v2, ,vn) T. { T:= Cây chỉ gồm 1 đỉnh v1; 2) Đặt mọi cạnh nối gốc với 1 đỉnh T vào T. Lần lượt xét Q={v}// Queue: các đỉnh chưa xử lý từng đỉnh con trực tiếp của gốc. Xem đỉnh này là gốc while (Q≠) mới, lặp lại thủ tục này cho đến khi mọi đỉnh của G đều { v = Q.Remove(); nằm trong T. 2 for (mỗi đỉnh w kề với v) if w Q and w T 3 { Q.Add(w) 6 1 4 Thêm cạnh (v,w) vào T } } 7 5 37 } 38 Tìm cây bao trùm theo phương pháp Tìm cây bao trùm theo phương pháp – BFS (Breadth First Search) 2 2 – BFS (Breadth First Search) 3 3 6 6 1 4 1 4 3 3 5 5 7 7 2 6 2 6 1 4 1 4 2 2 3 6 3 5 5 1 4 6 1 4 40 7 5 7 5 10
11. 05/11/2013 Tìm cây bao trùm theo phương pháp – BFS (Breadth First Search) Cây bao trùm nhỏ nhất 4 4 Đồ thị có trọng số: Là đồ thị trong đó mỗi cạnh (cung) 3 3 2 2 được gán thêm một số thực gọi là trọng số (weight) của cạnh (cung) Kí hiệu: 1 5 1 5 c(e): Trọng số của cạnh e c(G): Trọng số của đồ thị G 8 8 D B 9 8 A 6 6 7 7 4 3 5 9 9 41 C 42 Cây bao trùm nhỏ nhất Cây bao trùm nhỏ nhất Ma trận kề của đồ thị có trọng số: Cho G= có Bài toán: Cho G là đồ thị liên thông, có trọng số. Hãy trọng số, ma trận kề trọng số của G là ma trận A có tìm một cây bao trùm của G có trọng số nhỏ nhất kích cỡ |V| |V| trong đó mỗi phần tử aij có giá trị như sau: Trọng số của cạnh/cung (vi,vj) nếu (vi,vj) E D D aij B 9 B Nếu (vi,vj) E 8 A A A B C D 4 4 3 D 3 5 B 9 5 8 A 8 5 A B 8 4 9 4 C C 3 5 4 3 5 C D 9 3 43 44 C 11
12. 05/11/2013 Thuật toán tìm cây bao trùm nhỏ Cây bao trùm nhỏ nhất nhất: Thuật toán KRUSKAL Định lý: Cho T là một cây bao trùm của đồ thị có trọng Kruskal(G: đồ thi liên thông có trọng số) số G liên thông. T là một cây bao trùm tối thiểu nếu và { T := ; chỉ nếu mỗi cạnh e T đều có trọng số lớn nhất trên E=EG;// EG là tập cạnh của G chu trình tạo bởi e và các cạnh của T While |T|<(n-1) and (E≠) { Chọn e là cạnh độ dài nhỏ nhất trong E D D B 9 B 9 E := E\{e} 8 A A If (T{e} không chứa chu trình) then 4 4 3 3 T := T{e} // Kết nạp cạnh e vào cây khung nhỏ nhất 5 5 } If ( |T|<(n-1) ) then Đồ thị không liên thông. C C 45 else return T; 46 } Thuật toán tìm cây bao trùm nhỏ Thuật toán tìm cây bao trùm nhỏ nhất: Thuật toán KRUSKAL nhất: Thuật toán KRUSKAL 4 4 4 4 3 4 3 4 3 4 3 4 2 9 2 9 2 9 2 9 8 18 8 18 8 18 8 18 12 6 12 6 12 6 12 6 1 7 5 1 7 5 1 7 5 1 7 5 3 3 3 3 5 8 5 8 5 8 5 8 10 10 10 10 6 11 6 11 6 11 6 11 7 7 7 7 9 1 9 1 9 1 9 1 47 48 12
13. 05/11/2013 Thuật toán tìm cây bao trùm nhỏ Thuật toán tìm cây bao trùm nhỏ nhất: Thuật toán KRUSKAL nhất: Thuật toán KRUSKAL 4 4 4 4 3 4 3 4 3 4 3 4 2 9 2 9 2 9 2 9 8 18 8 18 8 18 8 18 12 6 12 6 12 6 12 6 1 7 5 1 7 5 1 7 5 1 7 5 3 3 3 3 5 8 5 8 5 8 5 8 10 10 10 10 6 11 6 11 6 11 6 11 7 7 7 7 9 1 9 1 9 1 9 1 49 50 Thuật toán tìm cây bao trùm nhỏ Thuật toán tìm cây bao trùm nhỏ nhất: Thuật toán KRUSKAL nhất: Thuật toán KRUSKAL 4 3 4 2 9 C Sử dụng thuật toán 8 18 12 6 10 Kruskal tìm một cây 6 5 1 7 5 8 bao trùm nhỏ nhất B 15 F A D của G? 6 6 3 5 8 8 8 12 10 4 6 11 E 7 G 9 1 51 52 13
14. 05/11/2013 Thuật toán tìm cây bao trùm Thuật toán tìm cây bao trùm nhỏ nhất: Thuật toán PRIM nhỏ nhất: Thuật toán PRIM Prim(G: liên thông, có trọng số) 4 4 3 4 3 4 { ET := ;VT={1};// VT là tập đỉnh của T, ET: tập cạnh của T 2 9 2 9 while (|V | ; 6 11 6 11 7 7 } 9 1 9 1 53 54 Thuật toán tìm cây bao trùm Thuật toán tìm cây bao trùm nhỏ nhất: Thuật toán PRIM nhỏ nhất: Thuật toán PRIM 4 4 4 4 3 3 4 3 4 3 4 2 4 2 9 2 9 2 9 9 8 8 18 8 18 8 18 18 6 12 6 12 6 12 6 12 5 1 7 5 1 7 5 1 7 5 1 7 3 3 3 3 8 5 8 5 8 5 8 5 10 10 10 10 6 6 11 6 11 6 11 11 7 7 7 7 9 1 9 1 9 1 9 1 55 56 14
15. 05/11/2013 Thuật toán tìm cây bao trùm Thuật toán tìm cây bao trùm nhỏ nhất: Thuật toán PRIM nhỏ nhất: Thuật toán PRIM 4 4 4 3 3 4 2 4 3 4 2 9 9 2 9 8 8 18 6 18 6 8 18 12 12 12 6 5 1 7 5 1 7 1 7 5 3 3 8 3 5 8 5 5 8 10 10 10 6 6 11 11 6 11 7 7 7 9 1 9 1 9 1 57 58 15