[Giáo trình Toán rời rạc] - Chương3 - Đồ thị

Tài liệu " [Giáo trình Toán rời rạc] - Chương3 - Đồ thị " 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ương3 - Đồ thị http://ebook.here.vn T i mi n phí ð thi, eBook, Tài li u h c t p CHƯƠNG III ð TH Lý thuy t ñ th là m t ngành khoa h c ñư c phát tri n t lâu nhưng l i có nhi u ng d ng hi n ñ i. Nh ng ý tư ng cơ b n c a nó ñư c ñưa ra t th k 18 b i nhà toánh c Th y Sĩ tên là Leonhard Euler. Ông ñã dùng ñ th ñ gi i quy t bài toán 7 chi cc u Konigsberg n i ti ng. ð th cũng ñư c dùng ñ gi i các bài toán trong nhi u lĩnh v c khác nhau. Thíd , dùng ñ th ñ xác ñ nh xem có th c hi n m t m ch ñi n trên m t b ng ñi n ph ngñư c không. Chúng ta cũng có th phân bi t hai h p ch t hóa h c có cùng công th cphân t nhưng có c u trúc khác nhau nh ñ th . Chúng ta cũng có th xác ñ nh xem haimáy tính có ñư c n i v i nhau b ng m t ñư ng truy n thông hay không n u dùng môhình ñ th m ng máy tính. ð th v i các tr ng s ñư c gán cho các c nh c a nó có thdùng ñ gi i các bài toán như bài toán tìm ñư ng ñi ng n nh t gi a hai thành ph trongm t m ng giao thông. Chúng ta cũng có th dùng ñ th ñ l p l ch thi và phân chiakênh cho các ñài truy n hình.3.1. ð NH NGHĨA VÀ THÍ D . ð th là m t c u trúc r i r c g m các ñ nh và các c nh (vô hư ng ho c cóhư ng) n i các ñ nh ñó. Ngư i ta phân lo i ñ th tùy theo ñ c tính và s các c nh n icác c p ñ nh c a ñ th . Nhi u bài toán thu c nh ng lĩnh v c r t khác nhau có th gi iñư c b ng mô hình ñ th . Ch ng h n ngư i ta có th dùng ñ th ñ bi u di n s c nhtranh các loài trong m t môi trư ng sinh thái, dùng ñ th ñ bi u di n ai có nh hư nglên ai trong m t t ch c nào ñó, và cũng có th dùng ñ th ñ bi u di n các k t c c c acu c thi ñ u th thao. Chúng ta cũng có th dùng ñ th ñ gi i các bài toán như bài toántính s các t h p khác nhau c a các chuy n bay gi a hai thành ph trong m t m nghàng không, hay ñ gi i bài toán ñi tham quan t t c các ñư ng ph c a m t thành phsao cho m i ñư ng ph ñi qua ñúng m t l n, ho c bài toán tìm s các màu c n thi t ñtô các vùng khác nhau c a m t b n ñ . Trong ñ i s ng, chúng ta thư ng g p nh ng sơ ñ , như sơ ñ t ch c b máy, sơñ giao thông, sơ ñ hư ng d n th t ñ c các chương trong m t cu n sách, ..., g mnh ng ñi m bi u th các ñ i tư ng ñư c xem xét (ngư i, t ch c, ñ a danh, chương m csách, ...) và n i m t s ñi m v i nhau b ng nh ng ño n th ng (ho c cong) hay nh ngmũi tên, tư ng trưng cho m t quan h nào ñó gi a các ñ i tư ng. ðó là nh ng thí d vñ th .3.1.1. ð nh nghĩa: M t ñơn ñ th G = (V, E) g m m t t p khác r ng V mà các ph nt c a nó g i là các ñ nh và m t t p E mà các ph n t c a nó g i là các c nh, ñó là cácc p không có th t c a các ñ nh phân bi t. 37http://ebook.here.vn T i mi n phí ð thi, eBook, Tài li u h c t p3.1.2. ð nh nghĩa: M t ña ñ th G = (V, E) g m m t t p khác r ng V mà các ph n tc a nó g i là các ñ nh và m t h E mà các ph n t c a nó g i là các c nh, ñó là các c pkhông có th t c a các ñ nh phân bi t. Hai c nh ñư c g i là c nh b i hay song songn u chúng cùng tương ng v i m t c p ñ nh. Rõ ràng m i ñơn ñ th là ña ñ th , nhưng không ph i ña ñ th nào cũng là ñơnñ th .3.1.3. ð nh nghĩa: M t gi ñ th G = (V, E) g m m t t p khác r ng V mà các ph n tc a nó g i là các ñ nh và m t h E mà các ph n t c a nó g i là các c nh, ñó là các c pkhông có th t c a các ñ nh (không nh t thi t là phân bi t). V i v∈V, n u (v,v)∈E thì ta nói có m t khuyên t i ñ nh v. Tóm l i, gi ñ th là lo i ñ th vô hư ng t ng quát nh t vì nó có th ch a cáckhuyên và các c nh b i. ða ñ th là lo i ñ th vô hư ng có th ch a c nh b i nhưngkhông th có các khuyên, còn ñơn ñ th là lo i ñ th vô hư ng không ch a c nh b iho c các khuyên.Thí d 1: v1 v2 v3 v4 v1 v2 v3 v5 v6 v7 v4 v5 v6 ðơn ñ th Gi ñ th3.1.4. ð nh nghĩa: M t ñ th có hư ng G = (V, E) g m m t t p khác r ng V mà cácph n t c a nó g i là các ñ nh và m t t p E mà các ph n t c a nó g i là các cung, ñó làcác c p có th t c a các ph n t thu c V.3.1.5. ð nh nghĩa: M t ña ñ th có hư ng G = (V, E) g m m t t p khác r ng V màcác ph n t c a nó g i là các ñ nh và m t h E mà các ph n t c a nó g i là các cung,ñó là các c p có th t c a các ph n t thu c V. ð th vô hư ng nh n ñư c t ñ th có hư ng G b ng cách xoá b các chi u mũitên trên các cung ñư c g i là ñ th vô hư ng n n c a G.Thí d 2: v1 v2 v3 v5 v1 v2 v3 V5 v6 v7 v4 v5 v6 ð th có hư ng ða ñ th có hư ng 38http://ebook.here.vn T i mi n phí ð thi, eBook, Tài li u h c t pThí d 3: 1) ð th “l n t ” trong sinh thái h c. ð th ñư c dùng trong nhi u môhình có tính ñ n s tương tác ...