Bài giảng Toán học rời rạc: Phần 2

Bài giảng "Toán học rời rạc: Phần 2" giới thiệu tới người đọc các nội dung:Phép đếm (nguyên lý cộng, nhân và bù trừ; giải tích tổ hợp, nguyên lý Dirichlet, công thức đệ quy), lý thuyết đồ thị (đại cương, đồ thị liên thông, đường đi ngắn nhất, cây khung trọng lượng tối tiểu, luồng cực đại), số học. Mời các bạn cùng tham khảo.

Nội dung trích xuất từ tài liệu:
Bài giảng Toán học rời rạc: Phần 2TOÁNHỌCRỜIRẠC PHẦN2DISCRETEMATHEMATICS PARTTWO NỘIDUNG1. PHÉPĐẾM a. Nguyênlýcộng,nhân&bùtrừ b. Giảitíchtổhợp c. NguyênlýDirichlet d. Côngthứcđệquy2. LÝTHUYẾTĐỒTHỊ a. Đạicương b. Đồthịliênthông c. Đườngđingắnnhất d. Câykhungtrọnglượngtốitiểu e. Luồngcựcđại2. SỐHỌC a. Lýthuyếtchiahết b. Lýthuyếtđồngdư 2 PHÉPĐẾM(1)• NGUYÊNLÝCỘNG,NHÂN,BÙ – Alàmộttậphợp,kýhiệu|A|bảnsốcủaA,trongtrườnghợpA làtậphữuhạn,|A|chínhlàsốphầntửcủaA – |A B|=|A|+|B||A B| nếuA B= thì|A B|=|A|+|B| – |AxB|=|A|*|B| – B A:|A–B|=|A||B|• GIẢITÍCHTỔHỢP – Slàmộttậphợphữuhạn,|S|=m – SốcáctậphợpconcủaS=2m m m! – SốcáctậpconnphầntửcủaS(n m)= n ( m n)! n! – MộtbộnphầntửcũaS:(a1,a2,…,an) Sn sốcácbộnphầntửcủaS=mn – Sốcáchoánvịcủamộtdãymphầntử=m! 3 PHÉPĐẾM(2)• CÁCVÍVỤ – Trongmộtphònghọpcónngười,mỗingườibắttayvớimỗi ngườikhácđúngmộtlần.Sốbắttay? – Dùngnbitđểbiểudiễnnhịphânchocácsốnguyênkhôngâm, sốsốnguyêncóthểđượcbiểudiễn? – Cóbaonhiêusốthậpphâncó6chữsố?Baonhiêusốthập phâncósốchữsốnhỏhơnsáu? – Cóbaonhiêucáchsắpxếpchỗngồichonngườixungquanh mộtchiếcbànhọptròn? Bâygiờgiảsửôngchủtịchcuộchọpđượcsắpngồiởmộtghế xácđịnh,cóbaonhiêucáchsắpxếpchỗngồichocácngười cònlại? – Cóbaonhiêudãysốnguyêndương,cótổngbằngn? – Cóbaonhiêudãyksốnguyêndươngcótổngbằngn? – Cóbaonhiêucáchphânphátnmónquà(khácnhauđômột) chokđứatrẻ? 4 PHÉPĐẾM(3)– Cóbaonhiêucáchsắpxếp8cácquânxetrongbàncờ8x8sao chokhôngquânxenào«bịtấncông»?– Câynhịphânchiềucaohcónhiềunhấtbaonhiêunútlá?– Trongmặtphẳng,chonđườngthẳngđôimộtcắtnhauvà khôngcóbađườngthẳngnàođồngquy.nđườngthẳngnày chiamặtphẳngthànhbaonhiêumiền?– Chongiáclồi,khôngcóbađườngchéonàođồngquy,các đườngchéocủađagiácchiadagiácthànhbaonhiêumiền? 5 LÝTHUYẾTĐỒTHỊ(1)• CÁCĐỊNHNGHĨA,KHÁINIỆM Đồthị(vôhướng) • G=(V,E),V=tậpcácđỉnh,E=tậpcáccạnhv1v2,v1,v2 E • Đỉnhcôlập:đỉnhkhôngcócạnhđiqua • Đỉnhtreo:chỉthuộcmộtcạnhduynhất(cạnhtreo) • Đađồthị:tồntạinhiềuhơn1cạnhnốihaiđỉnh • đồthịđơn:tồntạinhiềunhấtmộtcạnhnốihaiđỉnh • Đỉnhkề:chungcạnh • Cạnhkề:chungđỉnh • Đồthịđầyđủ:mọicặpđỉnh(phânbiệt)đềucócạnhnối • Đồthịcon:A V,EA={(v1,v2) E|v1,v2 A},GA=(A,EA) • Đồthịbộphận:C E,GC=(E,C) • Đồthịbộphậncon 6 LÝTHUYẾTĐỒTHỊ(2)– BIỂUDIỄNĐỒTHỊ • Matrậnđỉnhcạnh • Matrậnkề • Matrậntrọngsố • Danhsáchđỉnhkề– ĐƯỜNGĐI&CHUTRÌNH • Đườngđi:u,v V,u=v0,v1,…,vn=vsaochovivi+1 E • Đườngđisơcấp:tập i=0,…,n1:vi vi+1 • Chutrình:v0=vn • Chutrìnhsơcấp: i=1,…,n1:vi vi+1– ĐỒTHỊLIÊNTHÔNG • Đồthịvôhướngliênthông: u,v V, đườngđigiữau,v • Thànhphầnliênthông: • GiảithuậtA1 • Đỉnhkhớp,cạnheo • Đồthịliênthôngbậc2:Liênthông,bậc 3,khôngcóđỉnhkhớp • GiảithuậtA2 7 LÝTHUYẾTĐỒTHỊ(3)Đồthịcóhướng • G=(V,C),V=tậpcácđỉnh,C=tậpcáccung(v1,v2),v1,v2 E • Khuyên • Đỉnhcôlập • Đỉnhtreo,cungtreo:mútcuốicủachỉmộtcung • Nửabậctrong(vào):d(x) • Nửabậcngoài(ra):d+(x) • Bậccủađỉnh:d(x)=d(x)+d+(x) • + (A)={(i,j)|i A,j A} • (A)={(i,j)|j A,i A} • (A)= +(A) (A) • Đađồthị,đồthịđơn • Đỉnhkề,cungkề • Đồthịcóhướngđốixứng,phiđốixứng 8 LÝTHUYẾTĐỒTHỊ(4)– BIỂUDIỄNĐỒTHỊ • Matrậnđỉnhcung:c=(v,.):M(v,c)=1,c=(.,v):M(v,c)=1 • Matrậnkề:(u,v) C:M(u,v)=1 • Matrậntrọngsố:(u,v) C, ...