Bài giảng Lý thuyết đồ thị - Chương 6: Cây - Nguyễn Trần Phi Phượng

Nội dung text: Bài giảng Lý thuyết đồ thị - Chương 6: Cây - Nguyễn Trần Phi Phượng

1. Chương 6 CÂY
2. 6.1 Định nghĩa – Tính chất Định nghĩa1 Cây là đồ thị vô hướng, liên thông và không có chu trình. Đồ thị không có chu trình gọilàrừng. Ví dụ 1 Rừng gồm ba cây T1, T2, T3. 12/05/2011 Lý thuyết đồ thị 2
3. 6.1 Định nghĩa – Tính chất Ví dụ 2 G1,G2 là cây. G3 không là cây do có chứa chu trình. G4 không là cây do không liên thông. 12/05/2011 Lý thuyết đồ thị 3
4. 6.1 Định nghĩa – Tính chất Định lý 1 Giả sử T=(V,E) là một đồ thị vô hướng n đỉnh. Khi đó, các mệnh đề sau đây là tương đương: 1. T là cây; 2. T không chứachutrìnhvàcón–1cạnh; 3. T liên thông và có n–1cạnh; 4. T liên thông và mỗicạnh củaTđềulàcầu; 5. Hai đỉnh bấtkỳ củaTđượcnốivới nhau bằng đúng một đường đi đơn; 6. T không chứa chu trình nhưng nếuthêmmộtcạnh bấtkỳ vào T thì ta sẽđược thêm đúng 1 chu trình. 12/05/2011 Lý thuyết đồ thị 4
5. 6.1 Định nghĩa – Tính chất Chứng minh định lý (1) ⇒ (2): T là cây ⇒ T không chứa chu trình và có n-1 cạnh. •Hiển nhiên T không chứa chu trình (do T là cây) •Tachỉ cầnchứng minh T có n-1 cạnh. •XétTn là cây có n đỉnh. Ta sẽ chứng minh quy nạptheon – n = 2, Cây có 2 đỉnhthìcó1cạnh. Đúng. –Giả sử mọi cây có k đỉnh thì sẽ có k-1 cạnh –XétTk+1 làcâycók+1đỉnh. Dễ thấyrằng trong cây Tk+1 luôn tồn tạiítnhất1đỉnh treo. –Loại đỉnh treo này (cùng vớicạnh nối) ra khỏiTk+1 ta được đồ thị T’ có k đỉnh. Dễ thấyT’vẫn liên thông và không có chu trình (do Tk+1 không có chu trình) – Suy ra T’ là cây. Theo giả thiếtquynạp, T’ có k đỉnh thì sẽ có k-1 cạnh. Vậy cây Tk+1 cókcạnh. (đpcm) 12/05/2011 Lý thuyết đồ thị 5
6. 6.1 Định nghĩa – Tính chất Chứng minh định lý (2) ⇒ (3): T không chứa chu trình và có n-1 cạnh ⇒ T liên thông và có n-1 cạnh. •Hiển nhiên T có n-1 cạnh (theo giả thiết) •Tachỉ cầnchứng minh T liên thông. •Giả sử Tcókthànhphần liên thông vớisốđỉnh lầnlượtlàn1, , nk. •Khiđómỗi thành phầnliênthôngcủaTsẽ là mộtcâyvàsẽ có số cạnh lầnlượtlàn1-1, n2-1, , nk-1. •Suyra,số cạnh củaTsẽ là n1-1 + n2-1 + + nk-1=n–k. •Theogiả thiết, số cạnh củacâylàn-1.Từđósuyrak=1hayTchỉ có 1 thành phần liên thông. Suy ra T liên thông (đpcm). 12/05/2011 Lý thuyết đồ thị 6
7. 6.1 Định nghĩa – Tính chất Chứng minh định lý (3) ⇒ (4): T liên thông và có n-1 cạnh ⇒ T liên thông và mỗicạnh củaTđềulàcầu. •Hiển nhiên T liên thông (theo giả thiết) •Tachỉ cầnchứng minh mỗicạnh củaTđềulàcầu. •Xét(u,v)làcạnh bấtkỳ củaT.Nếubỏ (u,v) ra khỏiT,tasẽđược đồ thị T’ có n đỉnh và n-2 cạnh. •Tađãchứng minh được đồ thị có n đỉnh và n-2 cạnh thì không thể liên thông. •Vậynếubỏ cạnh (u,v) ra thì sẽ làm mất tính liên thông của đồ thị. Suy ra (u,v) là cầu. (đpcm). 12/05/2011 Lý thuyết đồ thị 7
8. 6.1 Định nghĩa – Tính chất Chứng minh định lý (4) ⇒ (5): T liên thông và mỗicạnh củaTđềulàcầu ⇒ Giữahai đỉnh bấtkỳ của T luôn tồntại đúng 1 đường đi đơn. • Xét u, v là hai đỉnh bấtkỳ trong T. • Do T liên thông nên luôn tồntại đường đigiữauvàv.Tasẽ chứng minh đường đi này là duy nhất. •Giả sử có hai đường đi đơn khác nhau giữa u và v. Khi đóhai đường đinàysẽ tạo thành một chu trình. •Suyra,cáccạnh trên chu trình này sẽ không thể là cầu được–Mâu thuẫn. •Vậygiữauvàvchỉ có thể tồntại đúng 1 đường đi đơn. (đpcm) 12/05/2011 Lý thuyết đồ thị 8
9. 6.1 Định nghĩa – Tính chất Chứng minh định lý (5) ⇒ (6): Giữahaiđỉnh bấtkỳ của T luôn tồntại đúng 1 đường đi đơn ⇒ T không chứa chu trình, nhưng nếuthêmvào1cạnh bấtkỳ thì sẽ phát sinh đúng 1 chu trình • T không thể có chu trình, vì nếucóchutrìnhthìgiữahaiđỉnh trên chu trình này sẽ có 2 đường đi đơn khác nhau – mâu thuẫnvớiGT. •Giả sử ta thêm vào T cạnh (u,v) bấtkỳ (trước đó không có cạnh này trong T). •Khiđócạnh này sẽ tạovới đường đi duy nhấtgiữauvàvtrongT tạo thành 1 chu trình duy nhất. (Vì nếutạothành2chutrìnhthì chứng tỏ trước đócó2đường đikhácnhaugiữauvàv–mâuthuẫn vớigiả thiết) 12/05/2011 Lý thuyết đồ thị 9
10. 6.1 Định nghĩa – Tính chất Chứng minh định lý (6) ⇒ (1): T không chứa chu trình, nhưng nếuthêmvào1cạnh bất kỳ thì sẽ phát sinh đúng 1 chu trình ⇒ T là cây •Hiển nhiên T không chứa chu trình (theo giả thiết). •Giả sử T không liên thông. Khi đóTsẽ có nhiềuhơn 1 thành phần liên thông •Suyra,nếuthêmvàomộtcạnh bấtkỳ giữahaiđỉnh thuộc2thành phần liên thông khác nhau sẽ không tạothêmchutrìnhnào–mâu thuẫnvớigiả thiết. •Vậy, T phải liên thông. Suy ra T là cây. (đpcm) 12/05/2011 Lý thuyết đồ thị 10
11. 6.1 Định nghĩa – Tính chất Định nghĩa2 Cho T là mộtcây.Chọnmột đỉnh r củacâygọilàgốc. Vì có đường đi duy nhấttừ gốctớimỗi đỉnh của đồ thị nên ta định hướng mỗicạnh là hướng từ gốc đira.Câycùngvới gốcsinhramột đồ thị có hướng gọilàcây có gốc. – Trong một cây có gốc r thì: – deg-(r) = 0 – deg-(v) =1 vớimọi đỉnh không phảilàgốc. 12/05/2011 Lý thuyết đồ thị 11
12. 6.1 Định nghĩa – Tính chất Định nghĩa3 Cho cây có gốcr. –Gốcrđượcgọilàđỉnh mức0(level 0). –Cácđỉnh kề vớigốcrđượcxếp ở phía dướigốcvàgọi là đỉnh mức1(level 1). – Đỉnh sau của đỉnh mức1(xếpphíadưới đỉnh mức)gọilà đỉnh mức2. – – Level (v) =k⇔ đường đitừ gốcrđến v qua k cung. – Độ cao củacâylà mức cao nhấtcủa các đỉnh. 12/05/2011 Lý thuyết đồ thị 12
13. 6.1 Định nghĩa – Tính chất level 0 level 1 level 2 level 3 level 4 12/05/2011 Lý thuyết đồ thị 13
14. 6.1 Định nghĩa – Tính chất Định nghĩa4 Cho cây có gốcr. a) Nếuuvlàmột cung củaTthìuđượcgọilàcha của v,còn v gọilàcon củau. b) Đỉnh không có con gọilàlá (hay đỉnh ngoài). Đỉnh không phảilàlágọilàđỉnh trong. c) Hai đỉnh có cùng cha gọilàanh em. 12/05/2011 Lý thuyết đồ thị 14
15. 6.1 Định nghĩa – Tính chất Định nghĩa5 Cho T là cây có gốc. a) T đượcgọilàcây k-phân nếumỗi đỉnh củaTcónhiều nhất là k con. b) Cây 2-phân đượcgọilàcây nhị phân. c) Cây k-phân đủ là cây mà mọi đỉnh trong có đúng k con. d) Cây k-phân với độ cao h đượcgọilàcân đối nếu các đỉnh đều ở mức h hoặc h–1. 12/05/2011 Lý thuyết đồ thị 15
16. 6.1 Định nghĩa – Tính chất 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 12/05/2011 Lý thuyết đồ thị 16
17. 6.1 Định nghĩa – Tính chất Định nghĩa6 ChoTlàcâynhị phân có gốclàr.Tacóthể biểu diễnTnhư hình vẽ dướivới hai cây con tạirlàTL và TR ,chúng lầnlượt đượcgọilàcây con bên trái và cây con bên phải củaT. r TL TR 12/05/2011 Lý thuyết đồ thị 17
18. 6.1 Định nghĩa – Tính chất Định nghĩa7 Độ dài đường đi trong và độ dài đường đi ngoài Cho T là cây nhị phân đủ. a) Độ dài đường đitronglà tổng tấtcả các mứccủa các đỉnh trong, ký hiệuIP(T). b) Độ dài đường đi ngoài là tổng tấtcả các mứccủacáclá, ký hiệuEP(T). 12/05/2011 Lý thuyết đồ thị 18
19. 6.1 Định nghĩa – Tính chất Ví dụ Tính độ dài đường đitrongvàđộ dài đường đingoàicủa đồ thị dưới đây: 1 2 3 4 5 6 7 8 9 12/05/2011 Lý thuyết đồ thị 19
20. 6.2 Bài toán cây khung nhỏ nhất Định nghĩa1 Giả sử G=(V,E) là đồ thị vô hướng liên thông. Cây T=(V,F) vớiF⊆ E đượcgọilàcây khung (cây tối đại, cây bao trùm)của đồ thị G. Ví dụ Đồ thị và các cây khung của nó 12/05/2011 Lý thuyết đồ thị 20
21. 6.2 Bài toán cây khung nhỏ nhất Định nghĩa2 Cho đồ thị có trọng số G. Cây khung nhỏ nhấtcủaG(nếu tồntại) là cây khung có tổng trọng số nhỏ nhất trong số các cây khung củaG. Thuật toán tìm cây khung nhỏ nhất -ThuậttoánKruskal -ThuậttoánPrim 12/05/2011 Lý thuyết đồ thị 21
22. 6.2 Bài toán cây khung nhỏ nhất Thuật toán Kruskal Cho G là đồ thị liên thông, có trọng số,nđỉnh. Bước1.Trướchếtchọncạnh ngắnnhấte1 trong các cạnh củaG. Bước2.Khi đãchọnkcạnh e1,e2, ek thì chọntiếpcạnh ek+1 ngắnnhất trong các cạnh còn lạicủa G sao cho không tạo thành chu trình với các cạnh đãchọntrước. Bước3.Chọn đủ n-1 cạnh thì dừng. 12/05/2011 Lý thuyết đồ thị 22
23. 6.2 Bài toán cây khung nhỏ nhất Thuật toán Kruskal Ví dụ 6 3 a u d 4 1 4 b 6 8 c 12/05/2011 Lý thuyết đồ thị 23
24. 6.2 Bài toán cây khung nhỏ nhất Thuật toán Kruskal Ví dụ a S 1 1 b 6 3 a u d 4 4 1 b 6 8 c 12/05/2011 Lý thuyết đồ thị 24
25. 6.2 Bài toán cây khung nhỏ nhất Thuật toán Kruskal Ví dụ 3 a u d S 1 2 b 6 3 a u d 4 4 1 b 6 8 c 12/05/2011 Lý thuyết đồ thị 25
26. 6.2 Bài toán cây khung nhỏ nhất Thuật toán Kruskal Ví dụ 3 a u d 4 S 1 3 b 6 3 a u d 4 4 1 b 6 8 c 12/05/2011 Lý thuyết đồ thị 26
27. 6.2 Bài toán cây khung nhỏ nhất Thuật toán Kruskal Ví dụ 3 a u d 4 S 1 4 b 6 6 3 a u d 4 4 1 b 6 c 8 c 12/05/2011 Lý thuyết đồ thị 27
28. 6.2 Bài toán cây khung nhỏ nhất 6 3 Thuật toán Kruskal a u d 4 4 Ví dụ 1 b 6 Trọng số Cạnh 8 1 (a,b) Chọn c 3 (u,d) Chọn 4 (b,u) Chọn 4 (b,d) Không chọn vì tạo chu trình: b u d b 6 (a,u) Không chọn vì tạo chu trình: a b u a 6(c,d)Chọn. Dừng vì đã đủ cạnh 8(b,c) 12/05/2011 Lý thuyết đồ thị 28
29. 6.2 Bài toán cây khung nhỏ nhất Thuật toán Prim Bước1.Chọnmột đỉnh bấtkỳ v1 để có cây T1 chỉ gồm một đỉnh. Bước2.KhiđãchọncâyTk thì chọntiếpcâyTk+1 = Tk∪ ek+1.Trongđóek+1 là cạnh ngắnnhất trong các cạnh có một đầumútthuộcTk và đầu mút kia không thuộcTk. Bước3.Chọn được cây Tn thì dừng. 12/05/2011 Lý thuyết đồ thị 29
30. 6.2 Bài toán cây khung nhỏ nhất Thuật toán Prim Ví dụ 6 3 a u d 4 1 4 b 6 8 c 12/05/2011 Lý thuyết đồ thị 30
31. 6.2 Bài toán cây khung nhỏ nhất Thuật toán Prim Ví dụ 6 3 a u d 4 4 1 b 6 T1 c 8 c 12/05/2011 Lý thuyết đồ thị 31
32. 6.2 Bài toán cây khung nhỏ nhất Thuật toán Prim Ví dụ d 6 6 3 a u d 4 4 1 b 6 T2 c 8 c 12/05/2011 Lý thuyết đồ thị 32
33. 6.2 Bài toán cây khung nhỏ nhất Thuật toán Prim Ví dụ 3 u d 6 6 3 a u d 4 4 1 b 6 T3 c 8 c 12/05/2011 Lý thuyết đồ thị 33
34. 6.2 Bài toán cây khung nhỏ nhất Thuật toán Prim Ví dụ 3 u d 4 b 6 6 3 a u d 4 4 1 b 6 T4 c 8 c 12/05/2011 Lý thuyết đồ thị 34
35. 6.2 Bài toán cây khung nhỏ nhất Thuật toán Prim Ví dụ 3 a u d 4 1 b 6 6 3 a u d 4 4 1 b 6 T5 c 8 c 12/05/2011 Lý thuyết đồ thị 35
36. 6.2 Bài toán cây khung nhỏ nhất Thuật toán Prim Để biểudiễnlờigiải, ta sẽ sử dụng2mảng: –Mảng d: d[v] dùng để lưu độ dài cạnh ngắnnhấtnốivới v trong số các cạnh chưaxét. –Mảng near: near[v] dùng để lưu đỉnh còn lại (ngoài v) củacạnh ngắnnhất nói ở trên. v d[v] near[v] 3 a u d c00 1 4 d6c b 6 u3d b4u c a1b 12/05/2011 Lý thuyết đồ thị 36
37. 6.2 Bài toán cây khung nhỏ nhất // Khởi tạo //Bướclặp Chọn s là một đỉnh nào đó của đồ thị Stop = False; While (! Stop) VH = {s};//Tập những đỉnh đã đưa vào cây { Tìm u∈V\V thỏa mãn d[u] = min{d[v]: v∈V\V }; T = ∅; //Tập cạnh của cây H H VH =VH ∪ {u}; d[s] = 0; near[s] = s; T=T∪ { (u, near[u]) }; If (|VH|==n) For v∈V\VH { { H=(VH, T) là cây khung của đồ thị; Stop = True; d[v] = a[s,v]; } Else near[v] = s; For v ∈V\VH } If d[v] > a[u,v] then { d[v] = c[u,v]; near[v] = u; } } 12/05/2011 Lý thuyết đồ thị 37
38. 6.2 Bài toán cây khung nhỏ nhất 6 3 3 a u d a u d 4 4 1 1 4 b 6 6 b 8 c c Bước lặp Đỉnh c Đỉnh a Đỉnh b Đỉnh d Đỉnh u VH T Khởi tạo [0,c] [∞,c] [8,c] [6,c]* [∞,c] a ∅ 1-[∞,c] [4,d] - [3,d]* c,d (d,c) 2 - [6,u] [4,d]* - - c,d,u (d,c),(u,d) 3 - [1,b]* - - - c,d,u,b (d,c),(u,d),(b,u) 4 - - - - - c,d,u,b,a (d,c),(u,d),(b,u), (a,b) 12/05/2011 Lý thuyết đồ thị 38