[Giáo trình Toán rời rạc] - Chương6 - Tree

Tài liệu " [Giáo trình Toán rời rạc] - Chương6 - Tree " mang tính chất tham khảo, giúp ích cho các bạn tự học, ôn thi, với phương pháp học hay, thú vị, rèn luyện kỹ năng giải đề, nâng cao vốn kiến thức cho các bạn trong các kỳ thi sắp tới. Tác giả hy vọng tài liệu này sẽ giúp ích cho các bạn.
Nội dung trích xuất từ tài liệu:
[Giáo trình Toán rời rạc] - Chương6 - Tree http://ebook.here.vn T i mi n phí ð thi, eBook, Tài li u h c t p CHƯƠNG VI CÂY M t ñ th liên thông và không có chu trình ñư c g i là cây. Cây ñã ñư c dùngt năm 1857, khi nhà toán h c Anh tên là Arthur Cayley dùng cây ñ xác ñ nh nh ngd ng khác nhau c a h p ch t hoá h c. T ñó cây ñã ñư c dùng ñ gi i nhi u bài toántrong nhi u lĩnh v c khác nhau. Cây r t hay ñư c s d ng trong tin h c. Ch ng h n,ngư i ta dùng cây ñ xây d ng các thu t toán r t có hi u qu ñ ñ nh v các ph n ttrong m t danh sách. Cây cũng dùng ñ xây d ng các m ng máy tính v i chi phí r nh tcho các ñư ng ñi n tho i n i các máy phân tán. Cây cũng ñư c dùng ñ t o ra các mãcó hi u qu ñ lưu tr và truy n d li u. Dùng cây có th mô hình các th t c mà ñ thihành nó c n dùng m t dãy các quy t ñ nh. Vì v y cây ñ c bi t có giá tr khi nghiên c ucác thu t toán s p x p.6.1. ð NH NGHĨA VÀ CÁC TÍNH CH T CƠ B N.6.1.1. ð nh nghĩa: Cây là m t ñ th vô hư ng liên thông, không ch a chu trình và cóít nh t hai ñ nh. M t ñ th vô hư ng không ch a chu trình và có ít nh t hai ñ nh g i là m t r ng.Trong m t r ng, m i thành ph n liên thông là m t cây.Thí d 1: R ng sau có 3 cây: i m a d c f g h j l b e k n6.1.2. M nh ñ : N u T là m t cây có n ñ nh thì T có ít nh t hai ñ nh treo.Ch ng minh: L y m t c nh (a,b) tuỳ ý c a cây T. Trong t p h p các ñư ng ñi sơ c pch a c nh (a,b), ta l y ñư ng ñi t u ñ n v dài nh t. Vì T là m t cây nên u ≠ v. M tkhác, u và v ph i là hai ñ nh treo, vì n u m t ñ nh, u ch ng h n, không ph i là ñ nh treothì u ph i là ñ u mút c a m t c nh (u,x), v i x là ñ nh không thu c ñư ng ñi t u ñ n v.Do ñó, ñư ng ñi sơ c p t x ñ n v, ch a c nh (a,b), dài hơn ñư ng ñi t u ñ n v, trái v itính ch t ñư ng ñi t u ñ n v ñã ch n.6.1.3. ð nh lý: Cho T là m t ñ th có n ≥ 2 ñ nh. Các ñi u sau là tương ñương:1) T là m t cây.2) T liên thông và có n−1 c nh.3) T không ch a chu trình và có n−1 c nh.4) T liên thông và m i c nh là c u.5) Gi a hai ñ nh phân bi t b t kỳ c a T luôn có duy nh t m t ñư ng ñi sơ c p. 87http://ebook.here.vn T i mi n phí ð thi, eBook, Tài li u h c t p6) T không ch a chu trình nhưng khi thêm m t c nh m i thì có ñư c m t chu trình duynh t. ⇒Ch ng minh: 1)⇒2) Ch c n ch ng minh r ng m t cây có n ñ nh thì có n−1 c nh. Tach ng minh b ng quy n p. ði u này hi n nhiên khi n=2. Gi s cây có k ñ nh thì có k−1c nh, ta ch ng minh r ng cây T có k+1 ñ nh thì có k c nh. Th t v y, trong T n u ta xoám t ñ nh treo và c nh treo tương ng thì ñ th nh n ñư c là m t cây k ñ nh, cây này cók−1 c nh, theo gi thi t quy n p. V y cây T có k c nh. ⇒2)⇒3) N u T có chu trình thì b ñi m t c nh trong chu trình này thì T v n liên thông.Làm l i như th cho ñ n khi trong T không còn chu trình nào mà v n liên thông, lúc ñóta ñư c m t cây có n ñ nh nhưng có ít hơn n−1 c nh, trái v i 2). ⇒3)⇒4) N u T có k thành ph n liên thông T1, ..., Tk l n lư t có s ñ nh là n1, ..., nk (v in1+n2+ … +nk=n) thì m i Ti là m t cây nên nó có s c nh là ni−1. V y ta có n−1=(n1−1)+(n2−1)+ ... +(nk−1)=(n1+n2+ … +nk)−k=n−k.Do ñó k=1 hay T liên thông. Hơn n a, khi b ñi m t c nh thì T h t liên thông, vì n ucòn liên thông thì T là m t cây n ñ nh v i n−2 c nh, trái v i ñi u ñã ch ng minh trên. ⇒4)⇒5) Vì T liên thông nên gi a hai ñ nh phân bi t b t kỳ c a T luôn có m t ñư ng ñi sơc p, nhưng không th ñư c n i b i hai ñư ng ñi sơ c p vì n u th , hai ñư ng ñó s t ora m t chu trình và khi b m t c nh thu c chu trình này, T v n liên thông, trái v i githi t. ⇒5)⇒6) N u T ch a m t chu trình thì hai ñ nh b t kỳ trên chu trình này s ñư c n i b ihai ñư ng ñi sơ c p. Ngoài ra, khi thêm m t c nh m i (u,v), c nh này s t o nên v iñư ng ñi sơ c p duy nh t n i u và v m t chu trình duy nh t. ⇒6)⇒1) N u T không liên thông thì thêm m t c nh n i hai ñ nh hai thành ph n liênthông khác nhau ta không nh n ñư c m t chu trình nào. V y T liên thông, do ñó nó làm t cây.6.2. CÂY KHUNG VÀ BÀI TOÁN TÌM CÂY KHUNG NH NH T.6.2.1. ð nh nghĩa: Trong ñ th liên thông G, n u ta lo i b c nh n m trên chu trìnhnào ñó thì ta s ñư c ñ th v n là liên thông. N u c lo i b các c nh các chu trìnhkhác cho ñ n khi nào ñ th không còn chu trình (v n liên thông) thì ta thu ñư c m t câyn i các ñ nh c a G. Cây ñó g i là cây khung hay cây bao trùm c a ñ th G. T ng quát, n u G là ñ th có n ñ nh, m c nh và k thành ph n liên thông thì ápd ng th t c v a mô t ñ i v i m i thành ph n liên thông c a G, ta thu ñư c ñ th g ilà r ng khung c a G. S c nh b lo i b trong th t c này b ng m−n+k, s này ký hi ulà ν(G) và g i là chu s c a ñ th G.6.2.2. Bài toán tì ...