Bài giảng Lý thuyết đồ thị (Graph theory) - Chương 4: Cây

Chia sẻ: Xaydung K23 | Ngày: | Loại File: PDF | Số trang:15

Thêm vào BST

Báo xấu

106
lượt xem 6
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Nội dung chương này trình bày định nghĩa và các tính chất cơ bản của cây; tìm cây bao trùm theo phương pháp – DFS (Depth First Search); cây bao trùm nhỏ nhất và một số nội dung khác. Tham khảo nội dung bài giảng để nắm bắt nội dung chi tiết.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Lý thuyết đồ thị (Graph theory) - Chương 4: Cây

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) T1 T2 v2 4 1
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 Chiều cao của cây Mức 0 Một cây tự do có thể x root Mức 1 Ví dụ: chọn một đỉnh bất kỳ làm y Mức 2 gốc để trở thành cây có gốc root Mức 3 - 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
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) Cây có 11 đỉnh  có 11-1=10 cạnh E (v)  max  (u , v) 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
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
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? T1 T2 … 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 - Duyệt Tr2theo thứ tự giữa,…, duyệt Trk theo thứ tự giữa - Thăm r Ví dụ: Kết quả duyệt theo Inorder? Ví dụ: Kết quả duyệt theo postorder? 19 20 5
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 5 1 5 D 1 1 B C A 8 8 8 6 6 6 C 7 7 7 21 H liên thông  H 22 có G Một cây bao trùm của G G không liên thông  G không có cây bao trùm 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
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 { T=Cây chỉ gồm 1 đỉnh v1 2 2 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) 2 1 2 3 4 5 6 7 2 1 2 3 4 5 6 7 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 1 1 0 1 0 0 1 3 3 1 1 0 1 0 0 1 6 6 1 4 1 4 4 0 1 1 0 0 1 1 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 5 5 7 7 1 0 1 1 1 0 0 7 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
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 1 1 0 1 0 0 1 3 3 1 1 0 1 0 0 1 3 6 6 1 4 4 1 4 4 0 1 1 0 0 1 1 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 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 1 1 0 1 0 0 1 3 3 1 1 0 1 0 0 1 3 6 6 1 4 1 4 4 0 1 1 0 0 1 1 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 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
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 1 1 0 1 0 0 1 3 3 1 1 0 1 0 0 1 3 6 6 4 1 4 1 4 0 1 1 0 0 1 1 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 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 5 6 7 7 1 0 1 1 1 0 0 35 36 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 – 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 7 5 7 5 2 2 6 6 1 4 1 4 2 2 3 6 3 5 5 1 4 6 1 4 5 40 7 5 7 10
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) 2 3 2 3 đượ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 8 8 c(G): Trọng số của đồ thị G 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 A 8 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 C 5 4  3 5     D  9 3  43 44 C 11
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|
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 6 8 18 6 8 18 6 8 18 6 12 12 12 12 1 7 5 1 7 5 1 7 5 1 7 5 3 8 3 8 3 8 3 8 5 5 5 5 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 6 Kruskal tìm một cây 12 10 6 5 bao trùm nhỏ nhất 1 7 5 8 B 15 F của G? A D 6 6 3 8 8 8 5 10 12 4 6 11 E 7 G 9 1 51 52 13
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 (|VT|
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 2 9 3 4 9 2 9 8 18 8 18 6 12 6 8 18 6 12 12 5 1 7 5 1 7 1 7 5 3 3 8 8 3 8 5 5 5 10 10 10 6 6 11 11 6 11 7 7 7 9 1 9 1 9 1 57 58 15