Bài giảng Cây

Chia sẻ: Paradise_12 Paradise_12 | Ngày: | Loại File: PDF | Số trang:29

Thêm vào BST

Báo xấu

71
lượt xem 4
download

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

Định nghĩa và tính chất Định nghĩa Cây. a) Cho G là đồ thị vô hướng. G được gọi là một cây nếu G liên thông và không có chu trình sơ cấp. b) Rừng là đồ thị mà mỗi thành phần liên thông của nó là một cây. Định nghĩa và tính chất 1 4 3 10 9 6 11 12 13 14 7 8 15 16 17 2 5 3 4 1 .Định nghĩa và tính chất Điều kiện cần và đủ. Cho T là đồ thị vô hướng có n đỉnh. Các phát biểu sau đây là tương đương: i. T là cây. ii. T liên thông và...

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 Cây

Cây Cây 1. ĐN và tính chất 2. Cây khung ngắn nhất Biên soạn: TS.Nguyễn Viết Đông 3. Cây có gốc 4. Phép duyệt cây 2 Định nghĩa và tính chất Định nghĩa và tính chất Định nghĩa Cây. 1 a) Cho G là đồ thị vô hướng. G được gọi là một 4 2 cây nếu G liên thông và không có chu trình 3 sơ cấp. 10 5 9 8 6 7 b) Rừng là đồ thị mà mỗi thành phần liên 15 thông của nó là một cây. 11 12 16 17 13 14 3 4 1
Định nghĩa và tính chất Định nghĩa và tính chất Điều kiện cần và đủ. 1 Cho T là đồ thị vô hướng có n đỉnh. Các phát biểu sau đây là tương đương: 4 2 3 i. T là cây. 10 ii. T liên thông và có n-1 cạnh. 5 9 8 iii. T không có chu trình sơ cấp và có n-1 cạnh . 6 7 iv. T liên thông và mỗi cạnh là một cầu. 15 11 12 16 17 13 14 v. Giữa hai đỉnh bất kỳ có đúng một đường đi sơ cấp nối chúng với nhau. vi. T không có chu trình sơ cấp và nếu thêm vào một cạnh giữa hai đỉnh không kề nhau thì có một chu trình sơ cấp duy nhất. 5 6 Breadth-first Search Algorithm .Thuật toán ưu tiên Định nghĩa và tính chất chiều rộng Cho G là đồ thị liên thông với tập đỉnh {v1, v2, …, vn} Định nghĩa cây khung. Bước 0:thêm v1 như là gốc của cây rỗng. Bước 1: thêm vào các đỉnh kề v1 làm con của nó và các Cho G = (V,E) là đồ thị vô hướng. cạnh nối v1 với chúng. Những đỉnh này là đỉnh mức 1 trong cây. T là đồ thị con khung của G. Bước 2: đối với mọi đỉnh v mức1, thêm vào các cạnh Nếu T là một cây thì T được gọi là cây khung(hay kề với v vào cây sao cho không tạo nên chu trình đơn. cây tối đại, hay cây bao trùm) của đồ thị G. Thu được các đỉnh mức 2. ……………………………………………………. Thuật toán tìm cây khung. Tiếp tục quá trình này cho tới khi tất cả các đỉnh của đồ thị được ghép vào cây. CâyT thu được là cây khung của đồ thị. 7 2
Ví dụ. Xét đồ thị liên thông G. c l b e a c l b e a e f f d d b g e f i d d b f g i c h k a h i j g j h Chọn e làm gốc i j  Thêm a và c làm con của b, m k  h là con duy nhất của d, m k Các đỉnh kề với e là con của nó.  g và j là con của f,  k là con duy nhất của i, Các đỉnh mức 1 là: b, d, f, i Các đỉnh mức 2 là: a, c, h, g, j, k Depth-first Search Algorithm (Thuật toán ưu tiên chiều sâu) c l b e a Cho G là đồ thị liên thông với tập đỉnh{v1, v2, …, vn} Chọn một đỉnh tùy ý của đồ thị làm gốc. Xây dựng e f f d d b đường đi từ đỉnh này bằng cách lượt ghép các cạnh sao g i cho mỗi cạnh mới ghép sẽ nối đỉnh cuối cùng trên đường đi với một đỉnh còn chưa thuộc đường đi.Tiếp tục c h a k h ghép thêm cạnh vào đường đi chừng nào không thể thêm i j g j được nữa. Nếu đường đi qua tất cả các đỉnh của đồ thị thì cây do đường đi này tạo nên là cây khung. Nếu chưa m k thì lùi lại đỉnh trước đỉnh cuối cùng của đường đi và xây l m dựng đường đi mới xuất phát từ đỉnh này đi qua các đỉnh Cuối cùng thêm l và m là con của g và k tương  còn chưa thuộc đường đi. Nếu điều đó không thể làm ứng được thì lùi thêm một đỉnh nữa trên đường đi, tức là lùi hai đỉnh trên đường đi và thử xây dựng đường đi mới. Các đỉnh mức 3 là: l, m 3
Ví dụ. Tìm cây bao trùm của đồ thị G. f d i j a f d i j g d a f g h e c f e k h h c b k c e k h i b k g j a b g j  Thêm i làm con thứ hai của h và lùi về f. Giải. Bắt đầu chọn đỉnh f làm gốc và  Lại thêm các hậu duệ của f : d, e, c, a Thêm các hậu duệ của f : g, h, k, j  Lùi về c và thêm b làm con thứ hai của nó . Lùi về k không thêm được cạnh nào, tiếp tục lùi về h Cây thu được là cây khung của đồ thị đã cho Định nghĩa và tính chất Cây khung ngắn nhất Thuật toán tìm cây khung ngắn nhất Định nghĩa Cây khung ngắn nhất. a)Thuật toán Kruscal Cho G là đồ thị có trọng số. Cây khung T của Cho G là đồ thị liên thông, có trọng số, n đỉnh. G được gọi là cây khung ngắn nhất (cây tối đại ngắn nhất,cây bao trùm ngắn nhất, cây Bước 1.Trước hết chọn cạnh ngắn nhất e1 trong các cạnh khung tối tiểu) nếu nó là cây khung của G mà của G. có trọng lượng nhỏ nhất. Bước 2. Khi đã chọn k cạnh e1,e2,…ek thì chọn tiếp cạnh ek+1 ngắn nhất trong các cạnh còn lại của G sao cho không tạo thành chu trình với các cạnh đã chọn trước. Bước 3. Chọn đủ n-1 cạnh thì dừng. 15 16 4
Cây khung ngắn nhất Cây khung ngắn nhất 6 3 d a a u S1 4 1 1 4 6 3 d a u b b 6 144 8 b 6 8 c c 17 18 Cây khung ngắn nhất Cây khung ngắn nhất 3 3 d a u d a u 4 1 1 6 6 3 3 d d a u a u b 4 4 b 1 1 4 4 b b 6 6 S2 S3 8 8 c c 19 20 5
Thuật toán Krusal Cây khung ngắn nhất 1 8 A B 3 5 3 C 3 4 d F 1 a u 1 6 4 1 D 2 E 6 3 d a u b 6 AE DC AC ED BD AF AD BC FE AB 14 4 1 1 1 2 3 3 4 5 6 8 b 6 S4 0. S0={} 8 c c 21 22 Thuật toán Krusal Thuật toán Krusal 1 1 8 8 A A B B 3 3 5 5 C C 3 3 4 4 F F 1 1 1 1 6 6 D D 2 2 E E AE DC AC ED BD AF AD BC FE AB AE DC AC ED BD AF AD BC FE AB 1 1 1 2 3 3 4 5 6 8 1 1 1 2 3 3 4 5 6 8 0. S0={} 1. S1= {AE} 1. S1=S0 + AE = {AE} 2. S2=S1 + DC = {AE,DC} 23 24 6
Thuật toán Krusal Thuật toán Krusal 1 1 8 8 A A B B 3 3 5 5 C C 3 3 4 4 F F 1 1 1 1 6 6 D D 2 2 E E AE DC AC ED BD AF AD BC FE AB AE DC AC ED BD AF AD BC FE AB 1 1 1 2 3 3 4 5 6 8 1 1 1 2 3 3 4 5 6 8 3. S3= {AE,DC,AC} 4. S4= {AE,DC,AC,BD} 4. S4=S3 + BD= {AE,DC,AC,BD} 5. S5=S4 + AF= {AE,DC,AC,BD,AF} 25 26 Thuật toán Krusal Ví dụ 1 A A B 11 3 7 10 C 3 B F 1 G D 8 9 1 3 5 D E E 10 12 8 Kết luận: S5= {AE,DC,AC,BD,AF} 4 là cây bao trùm tối tiểu cần tìm C 10 F Trọng lượng: 9 28 27 7
Cây khung ngắn nhất Cây khung ngắn nhất Thuật toán tìm cây khung ngắn nhất Thuật toán tìm cây khung ngắn nhất b)Thuật toán Prim. 6 3 d Bước 1. Chọn 1 đỉnh bất kỳ v1 để có cây T1 chỉ gồm 1 a u đỉnh. 4 1 4 Bước 2. Khi đã chọn cây Tk thì chọn tiếp cây b Tk+1 = Tk ek+1. Trong đó ek+1 là cạnh ngắn nhất trong 6 các cạnh có một đầu mút thuộc Tk và đầu mút kia 8 không thuộc Tk Bước 3. Chọn được cây Tn thì dừng. c 29 30 Cây khung ngắn nhất Cây khung ngắn nhất d 6u 3 6u 3 d d a a 6 4 4 1 1 4 4 b b 6 6 T1 T2 8 8 c c c c 31 32 8
Cây khung ngắn nhất Cây khung ngắn nhất 3 3 d d u u 4 6u 3 6u 3 d d a a b 6 6 4 4 1 1 4 4 b b 6 6 T3 T4 8 8 c c c c 33 34 Thuật toán Prim Cây khung ngắn nhất 1 8 A B 3 5 3 C d a u 3 4 F 1 1 4 6 1 D 2 E 6u 3 d a b 6 4 1 4 b 6 T5 8 c c 35 36 9
Thuật toán Prim Thuật toán Prim 1 1 8 8 A A B B 3 3 5 5 C C 3 3 4 4 F F 1 1 1 1 6 6 D D 2 2 E E 37 38 Thuật toán Prim Thuật toán Prim 1 1 8 8 A A B B 3 3 5 5 C C 3 3 4 4 F F 1 1 1 1 6 6 D D 2 2 E E 39 40 10
Thuật toán Prim Thuật toán Prim 1 1 8 8 A A B B 3 3 5 5 C C 3 3 4 4 F F 1 1 1 1 6 6 D D 2 2 E E Cây T5 = {AC, AE,CD,AF,DB} là cây bao trùm tối tiểu cần tìm với w(T5) = 9 41 42 Ví dụ Cây khung ngắn nhất Đề thi 2004 A Hãy trình bày thuật toán tìm cây khung ngắn nhất 11 7 10 của G chứa cạnh 58 nhưng không chứa cạnh 26 B G D 8 9 3 5 2 9 2 1 3 E 10 3 12 8 14 11 7 4 1 4 4 6 5 5 6 8 12 C 10 F 9 8 7 13 10 43 44 11
Cây khung ngắn nhất Cây có gốc Giải Định nghĩa.  Đặt G’= G -26 thì cây khung phải tìm là ở trong Cho T là một cây. Chọn một đỉnh r của cây gọi là G’. Đầu tiên chọn cạnh 58 sau đó áp dụng gốc . Vì có đường đi sơ cấp duy nhất từ gốc tới Kruscal như thông thường mỗi đỉnh của đồ thị nên ta định hướng mỗi cạnh là 2 9 3 1 2 hướng từ gốc đi ra . Cây cùng với gốc sinh ra một 7 2 9 2 1 3 1 đồ thị có hướng gọi là cây có gốc 4 4 14 11 7 6 5 Trong một cây có gốc r thì deg-(r) = 0, 4 1 4 6 5 6 8 5 6 8 12 deg-(v) =1với mọi đỉnh không phải là gốc. 9 7 9 8 7 10 13 10 45 46 Cây có gốc Cây có gốc Định nghĩa Cho cây có gốc r. ----------------------------------level 0  Gốc r được gọi là đỉnh mức 0 (level 0). ---------------------------------------level 1  Các đỉnh kề với gốc r được xếp ở phía dưới gốc và gọi là đỉnh mức 1(level 1). ----------------------------------------------level 2  Đỉnh sau của đỉnh mức 1(xếp phía dưới đỉnh mức1)gọi là đỉnh mức 2. …… ------------------------------------------------- -level 3  Level (v) = k  đường đi từ gốc r đến v qua k cung. ---------------------------------------------level 4  Độ cao của cây là mức cao nhất của các đỉnh. 47 48 12
Cây có gốc Cây có gốc Định nghĩa Định nghĩa Cho cây có gốc r Cho cây có gốc r a) Nếu uv là một cung của T thì u được gọi là cha d) Nếu có đường đi v1v2…vk thì v1, v2,.., vk-1 gọi là của v, còn v gọi là con của u. tổ tiên của vk. Còn vk gọi là hậu duệ của v1, v2,.., vk-1. b) Đỉnh không có con gọi là lá(hay đỉnh ngoài). Đỉnh không phải là lá gọi là đỉnh trong. e) Cây con tại đỉnh v là cây có gốc là v và tất cả các đỉnh khác là mọi hậu duệ của v trong cây T c) Hai đỉnh có cùng cha gọi là anh em. đã cho. 49 50 Cây có gốc Cây có gốc Định nghĩa 1 Cho T là cây có gốc. 4 2 a) T được gọi là cây k-phân nếu mỗi đỉnh của T có 3 nhiều nhất là k con. 10 5 9 8 b) Cây 2-phân được gọi là cây nhị phân. 6 7 15 c) Cây k-phân đủ là cây mà mọi đỉnh trong có 11 12 16 17 13 14 đúng k con. d) Cây k- phân với độ cao h được gọi là cân đối nếu các lá đều ở mức h hoặc h – 1 . 51 52 13
Cây có gốc Cây có gốc Định nghĩa Định nghĩa Cho T là cây nhị phân có gốc là r. Ta có thể biểu Độ dài đường đi trong và độ dài đường đi ngoài diễn T như hình vẽ dưới với hai cây con tại r là Cho T là cây nhị phân đủ. TL và TR ,chúng lần lượt được gọi là cây con bên trái và cây con bên phải của T. a) Độ dài đường đi trong là tổng tất cả các mức của các đỉnh trong, ký hiệu IP(T). r b) Độ dài đường đi ngoài là tổng tất cả các mức của các lá, ký hiệu EP(T). TL TR 53 54 Cây có gốc Cây có hướng Định lí IP(T) = ? 1 EP(T) = ? 2 3 Cho T là cây nhị phân đủ với k đỉnh trong và s lá. 7 Ta có: 5 4 6 s = k+1 và EP=IP+2k 10 8 11 9 55 56 14
Cây có hướng Phép duyệt cây(Tree travesal) Định nghĩa Định nghĩa Cho T là cây nhị phân không đủ. Lập T’ là cây có Duyệt cây là liệt kê tất các đỉnh của cây theo một thứ tự nào đó thành một dãy, mỗi được bằng cách sau: đỉnh chỉ xuất hiện một lần . i. Thêm vào mỗi lá của T hai con. ii. Thêm vào v một con nếu v là đỉnh trong của T mà chỉ có một con. Ta đặt: IP(T) :=IP(T’)& EP(T):=EP(T’) 57 58 Phép duyệt cây Preorder Traversal: J E A H T M Y Phép duyệt tiền thứ tự Visit first. (Preoder traversal) ROOT ‘J’ 1. Đến gốc r. ‘T’ ‘E’ 2. Dùng phép duyệt tiền thứ tự để duyệt các ‘M’ ‘Y’ cây con T1 rồi cây con T2 …từ trái sang ‘A’ ‘H’ phải. Visit left subtree second Visit right subtree last 59 60 15
Phép duyệt cây Preorder Traversal: J E A H T M Y Phép duyệt hậu thứ tự Visit first. (Posoder traversal). ROOT ‘J’ 1. Dùng phép duyệt hậu thứ tự để lần lượt duyệt cây con T1, T2,…. từ trái sang phải. ‘T’ ‘E’ 2. Đến gốc r. ‘M’ ‘Y’ ‘A’ ‘H’ Visit right subtree Visit left subtree in Preorder in Preorder 61 62 Postorder Traversal: A H E M Y T J Postorder Traversal: A H E M Y T J Visit last Visit last ROOT ROOT ‘J’ ‘J’ ‘T’ ‘T’ ‘E’ ‘E’ ‘M’ ‘Y’ ‘M’ ‘Y’ ‘A’ ‘A’ ‘H’ ‘H’ Visit right subtree Visit left subtree first Visit right subtree second Visit left subtree in Postorder in Postorder 63 64 16
Phép duyệt cây Inorder Traversal: A E H J M T Y Phép duyệt trung thứ tự cho cây nhị Visit second phân (Inorder traversal) ROOT ‘J’ 1. Duyệt cây con bên trái TL theo trung thứ tự. ‘T’ ‘E’ 2. Đến gốc r. ‘M’ ‘Y’ ‘A’ ‘H’ 3. Duyệt cây con bên phải theo trung thứ tự. Visit left subtree first Visit right subtree last 65 66 Phép duyệt cây Inorder Traversal: A E H J M T Y Visit second 1 preoder ROOT 4 2 3 ‘J’ 10 5 9 8 ‘T’ 6 7 ‘E’ 15 11 12 16 17 13 14 ‘M’ ‘Y’ ‘A’ ‘H’ Preoder:1,2,5,11,12,13,14,3,6,7,4,8,9,10,15,16,17 Visit left subtree Visit right subtree in Inorder in Inorder 67 68 17
Phép duyệt cây Phép duyệt cây ... r 1 b a posoder Inoder e c d 4 2 3 f g i h 10 5 j n 9 m 8 6 7 k p t 15 11 12 16 17 13 s u 14 q Inoder :p,j,q,f,c,k,g,a,d,r,b,h,s,m,e,i,t,n,u Posoder:11,12,13,14,5,2,6,7,3,8,9,15,16,17,10,4,1 69 70 Định nghĩa Cây nhị phân của biểu thức Cây nhị phân của biểu thức là cây nhị phân mà Gốc 1. Mỗi biến số được biểu diễn bởi một lá. ‘-’ 2. Mỗi đỉnh trong biểu diễn một phép toán với các thành tố là cây con tại đỉnh ấy. 3. Cây con bên trái và bên phải của một đỉnh trong biểu ‘8’ ‘5’ diễn cho biểu thức con, giá trị của chúng là thành tố mà ta áp dụng cho phép toán tại gốc của cây con. 8-5 có giá trị 3 INORDER TRAVERSAL: -85 PREORDER TRAVERSAL: 85- POSTORDER TRAVERSAL: 71 72 18
Cây nhị phân của biểu thức Cây nhị phân của biểu thức ‘*’ ‘*’ ‘*’ ‘3’ ‘3’ ‘+’ ‘+’ ‘2’ ‘2’ ‘4’ ‘4’ Kết quả? Dạng trung tố, tiền tố, hậu tố? ( 4 + 2 ) * 3 = 18 73 74 Cây nhị phân của biểu thức Giải thích Để có biểu thức theo ký pháp Ba lan, ta duyệt ‘*’ cây nhị phân của biểu thức bằng phép duyệt tiền thứ tự. ‘3’ ‘+’ Thực hiện biểu thức từ phải sang trái: Bắt đầu từ bên phải, khi gặp một phép toán thì ‘2’ ‘4’ phép toán này được thực hiện cho 2 thành tố Infix: ((4+2)*3) ngay bên phải nó, kết quả này là thành tố cho Ký pháp Ba lan : từ phải sang trái Prefix: * + 4 2 3 phép toán tiếp theo. Postfix: 4 2 + 3 * Ký pháp BL đảo : từ trái sang phải 75 76 19
Ví dụ Giải thích Để có biểu thức theo ký pháp Ba lan ngược, ta ‘*’ duyệt cây nhị phân của biểu thức bằng phép duyệt hậu thứ tự. ‘-’ ‘/’ Thực hiện biểu thức từ trái sang phải: Bắt đầu từ bên trái, khi gặp một phép toán thì ‘3’ ‘5’ ‘+’ ‘8’ phép toán này được thự hiện cho 2 thành tố ‘2’ ‘4’ ngay bên trái nó, kết quả này là thành tố cho phép toán tiếp theo. Kết quả của infix, prefix, postfix? 77 78 ‘*’ ‘*’ ‘/’ ‘/’ ‘-’ ‘-’ ‘8’ ‘8’ ‘5’ ‘5’ ‘3’ ‘3’ ‘+’ ‘+’ ‘2’ ‘2’ ‘4’ ‘4’ ((8-5)*((4+2)/3)) ((8-5)*((4+2)/3)) Infix: Infix: * - 8 5 / + 4 2 3 Thực hiện từ phải sang Prefix: *-85 /+423 Prefix: Thực hiện từ trái sang Postfix: 85- 42+3/* Postfix: 85- 42+3/* 79 80 20