Bài giảng Toán rời rạc (Phần II: Lý thuyết đồ thị): Chương 4 - Nguyễn Đức Nghĩa

Chương 4 trình bày về bài toán cây khung nhỏ nhất (The minimum spanning tree problem). Nội dung chính gồm có: Cây và các tính chất cơ bản của cây, cây khung của đồ thị, xây dựng tập các chu trình cơ bản của đồ thị, bài toán cây khung nhỏ nhất.
Nội dung trích xuất từ tài liệu:
Bài giảng Toán rời rạc (Phần II: Lý thuyết đồ thị): Chương 4 - Nguyễn Đức Nghĩa Chương 4Bài toán cây khung nhỏ nhất The Minimum Spanning Tree Problem Nội dung4.1.Câyvàcáctínhchấtcơbảncủacây4.2.Câykhungcủađồthị4.3.Xâydựngtậpcácchutrìnhcơbảncủađồthị4.4.Bàitoáncâykhungnhỏnhất 2 Cây và rừng (Tree and Forest)§Þnh ng hÜa 1. Ta g äi c ©y lµ ®å thÞ v « híng liª nth«ng kh«ng c ã c hu tr×nh. §å thÞ kh«ng c ã c hutr×nh®îc g äilµrõ ng .Nh vËy, rõ ng lµ ®å thÞ mµ mç i thµnh phÇn liªnth«ng c ñanãlµmé tc ©y. T1 T2 T3 Rừng F gồm 3 cây T1, T2,, T3 3 VÍ DỤG1,G2làcâyG3,G4khônglàcây 4 Các tính chất cơ bản của cây Địnhlý1.GiảsửT=(V,E)làđồthịvôhướngnđỉnh. Khiđócácmệnhđềsauđâylàtươngđương: (1)Tlàliênthôngvàkhôngchứachutrình; (2)Tkhôngchứachutrìnhvàcón1cạnh; (3)Tliênthôngvàcón1cạnh; (4)Tliênthôngvàmỗicạnhcủanóđềulàcầu; (5)HaiđỉnhbấtkỳcủaTđượcnốivớinhaubởi đúngmộtđườngđiđơn; (6)Tkhôngchứachutrìnhnhưnghễcứthêmvào nómộtcạnhtathuđượcđúngmộtchutrình. 5 Nội dung4.1.Câyvàcáctínhchấtcơbảncủacây4.2.Câykhungcủađồthị4.3.Xâydựngtậpcácchutrìnhcơbảncủađồthị4.4.Bàitoáncâykhungnhỏnhất 6 Cây khung của đồ thị Địnhnghĩa2. GiảsửG=(V,E)làđồthịvôhướngliên thông. Cây T=(V,F) với F E được gọi là cây khung củađồthịG. b c b c b ca d a d a d e e e G T1 T2 Đồ thị G và 2 cây khung T1 và T2 của nó 7 Số lượng cây khung của đồ thị Định lý sau đây cho biết số lượng cây khungcủađồthịđầyđủKn: Địnhlý2(Cayley). Sốcâykhungcủađồthị Knlànn2.ArthurCayley(1821–1895) b a b c b c a a c c a b K3 BacâykhungcủaK3 8 Bài toán trong hoá học hữu cơBiểudiễncấutrúcphântử:MỗiđỉnhtươngứngvớimộtnguyêntửCạnh–thểhiệnliênkếtgiữacácnguyêntửBàitoán:Đếmsốđồngphâncủacacbuahydronochứamộtsốnguyêntửcácbonchotrước 9 methane H ethane H H C H H C H H H H C Hpropane H H C H H H C H H C H H C H H C H butane H C H H C H H H saturatedhydrocarbonsCnH2n+2 10 Nội dung4.1.Câyvàcáctínhchấtcơbảncủacây4.2.Câykhungcủađồthị4.3.Xâydựngtậpcácchutrìnhcơbảncủađồthị4.4.Bàitoáncâykhungnhỏnhất 11 Tập các chu trình cơ bản Gi¶ sö G = (V,E) lµ ®¬n ®å thÞ v« híng liªn th«ng, H=(V,T) lµ c©y khung cña nã. C¸c c¹nh cña ®å thÞ thuéc c©y khung ta sÏ gäi lµ c¸c c¹nh trong, cßn c¸c c¹nh cßn l¹i sÏ gäi lµ c¹nh ngoµi. §Þnh nghÜa 3. NÕu thªm m é t c¹nh ngoµi e E T vµoc©ykhungHchóngtas Ïthu®îc®óngm é tchu tr×nhtrongH,kýhiÖuchutr×nhnµylµ C e .TËpc¸c chutr×nh ={C e :e ET}®îcgäilµtËpc¸cchutr×nhc¬b¶ncña®åthÞG. 12 Tính chấtGi¶ sö A vµ B lµ hai tËp hîp, ta ®a vµo phÐp to¸nsau A B = (A B) (A B). TËp A B ®îc gäi lµ hiÖu ®è i xø ng cña hai tËp Avµ B.Tªn gäi c hutr×nhc ¬b ¶n g¾n liÒn víi sù k ...