TRƯNGðIHCSƯPHMKTHUTHƯNGYÊN
KHOACÔNGNGHTHÔNGTIN
BÀITP
HCPHNTOÁNRIRC2
Trìnhñ%ñàot)o
H*ñàot)o
:
:
ðihc
Chínhquy/Liênthông
BàitpTOÁNRIRC2BmônCôngnghphnmm2010
Trang2
LI NÓI ĐU
Cóthnóitoánhcrirclàmôntiênquytvàhiuqu nh!tñngưihc
nângcaotưduytoánhctrongphântích,thitkthu*ttoánvàrènluynk,năng
l*ptrìnhv/inh0ngthu*ttoánph1ctp.Khôngnh0ngthnócònlà“c6angõ”ñ
ngưi hc có th tip c*n v/i r!t nhi9u modul trong khoa hc máy tính (như
Chươngtrìnhd<ch,lýthuyttínhtoán,Trítunhânto,...).Bàit*pñcAngcB
vànângcaokinth1ctrongmônhcnày
V9nDidung,bámsátv/ichươngtrìnhcAanhàtrưngvàhthBngbàit*p
cũngñưHcbiênsontheocácchươnglýthuyt.V/imJichươngsKñưHcchiathành
4phMn:
Ph,nA.Nh.cl)ilýthuy5t:tómtOtcáckinth1ccơb n,cácvídPvàcác
lưuýh0uích,cáckinhnghimtrongkhil*ptrình
Ph,nB.ð6bàit8p:ñưaracácloibàit*pkhácnhau,v/icácm1cñDkhác
nhau.
Ph,nC.Bàit8pm;u:Hư/ngdRngi imDtsBbàitiêubiutrongphMnB,có
phântíchthu*ttoánvàcàiñStchươngtrình.
Ph,nD.Bàit8pt=gi?i:NgưihcthUchinvicgi icácbàit*pnày
MongrWngtàiliunàyñáp1ngñưHcphMnnàonhucMucAahcsinh,sinhviên.ðây
làb nñMutiênchOcchOncònr!tnhi9usaisót.Nhómtácgi mongnh*nñưHcsU
ñónggópcAacácthMycôgiáo,cácbnsinhviênvàcAat!tc nh0ngaiquantâmt/i
lĩnhvUcnày.
HưngYên,tháng7năm2010
BDmônCôngnghphMnm9m
KhoaCôngnghthôngtin
Trưngñihcsưphmk,thu*tHưngYên
BàitpTOÁNRIRC2BmônCôngnghphnmm2010
Trang3
M@CL@C
Bài1:Cáckháinimcơb ncAaLýthuytñ^th< ............................................................5
MPctiêu ...................................................................................................................5
a.NhOclilýthuyt..................................................................................................5
b.ð9bàit*p..............................................................................................................5
c.Hư/ngdRngi i......................................................................................................6
d.Bàit*ptUgi i .......................................................................................................7
Bài2:Biudianñ^th<trênmáytính..............................................................................10
MPctiêu .................................................................................................................10
a.NhOclilýthuyt................................................................................................10
b.ð9bàit*p............................................................................................................10
c.Hư/ngdRngi i....................................................................................................10
d.Bàit*ptUgi i .....................................................................................................14
Bài3:ð^th<Euler .........................................................................................................15
MPctiêu .................................................................................................................15
a.NhOclilýthuyt................................................................................................15
b.ð9bàit*p............................................................................................................16
c.Hư/ngdRngi i....................................................................................................16
d.Bàit*ptUgi i .....................................................................................................19
Bài4:ð^th<hamilton....................................................................................................20
MPctiêu .................................................................................................................20
a.NhOclilýthuyt................................................................................................20
b.ð9bàit*p............................................................................................................20
c.Hư/ngdRngi i....................................................................................................20
d.Bàit*ptUgi i .....................................................................................................22
Bài5:Th olu*ncàiñStñ^th<,cácthu*ttoánlitkêchutrìnhEulervàHamilton.
Th olu*nv9bàit*pl/n.................................................................................................23
MPctiêu .................................................................................................................23
a.NhOclilýthuyt................................................................................................23
b.ð9bàit*p............................................................................................................23
c.Hư/ngdRngi i....................................................................................................23
d.Bàit*ptUgi i .....................................................................................................31
Bài6Thu*ttoántìmkimtrênñ^th<và1ngdPng.........................................................34
MPctiêu .................................................................................................................34
a.NhOclilýthuyt................................................................................................34
b.ð9bàit*p............................................................................................................34
c.Hư/ngdRngi i....................................................................................................34
d.Bàit*ptUgi i .....................................................................................................51
Bài7:Câyvàcâykhung ................................................................................................52
MPctiêu .................................................................................................................52
a.NhOclilýthuyt................................................................................................52
b.ð9bàit*p............................................................................................................53
c.Hư/ngdRngi i....................................................................................................54
d.Bàit*ptUgi i .....................................................................................................55
Bài8:Th olu*nv9càiñStthu*ttoántìmcâykhungnhfnh!ttrênñ^th< ......................58
MPctiêu .................................................................................................................58
BàitpTOÁNRIRC2BmônCôngnghphnmm2010
Trang4
a.NhOclilýthuyt................................................................................................58
b.ð9bàit*p............................................................................................................58
c.Hư/ngdRngi i....................................................................................................58
d.Bàit*ptUgi i .....................................................................................................70
Bài9,10:BàitoántìmñưngñingOnnh!t ....................................................................71
MPctiêu .................................................................................................................71
a.NhOclilýthuyt................................................................................................71
b.ð9bàit*p............................................................................................................71
c.Hư/ngdRngi i....................................................................................................73
d.Bàit*ptUgi i .....................................................................................................92
Bài12:Bàitoánlu^ngcUcñitrongmng.....................................................................97
MPctiêu .................................................................................................................97
a.NhOclilýthuyt................................................................................................97
b.ð9bàit*p............................................................................................................98
c.Hư/ngdRngi i....................................................................................................99
d.Bàit*ptUgi i ...................................................................................................101
BàitpTOÁNRIRC2BmônCôngnghphnmm2010
Trang5
Bài1:Cáckháini*mcơb?ncFaLýthuy5tñHthI
MJctiêu
gLưutr0ñưHcñ^th<trênmáytínhtheonh0ngphươngphápkhácnhau.
gCàiñStñưHcchươngtrìnhchuynñhigi0acácphươngpháp.
gSinhviêncókh năngtUhc.
a.Nh.cl)ilýthuy5t
gHaiñjnhx,yñưHcgilàcSpñjnhliênthông,nuhoScgi0axvàycóítnh!tmDt
xíchnBiv/inhau,hoSct^ntiítnh!tmDtñưngñitlysangx.
gð^th<vôhư/ngG(V,E)ñưHcgilàñ^th<liênthông,numicSpñjnhcAanó
ñ9uliênthông.
gð^th<cóhư/ngG(V,E)ñưHcgilàñ^th<liênthôngmch,numicSpñjnhcAa
nóñ9uliênthông.
gBiudiandnghìnhhc:Gi s6cóñ^th<G(V,E).
Biudianñjnh:l!ycácñimtrênmStphnnghaytrênkhônggiantương1ng
v/icácphMnt6cAat*pVvàdùngngaykýhiucácphMnt6nàyñpghitrêncác
ñimtương1ng.
Biudiancnh:Nucnhav/ihaiñjnhñMulàx,ythìnóñưHcbiudian
bWngñonthnnghaymDtñoncongnBigi0ahaiñimx,yvàkhôngñiquacác
ñimtương1ngtrongkhônggian.
Biudiancung:nucungacóñjnhñMulàx,ñjnhcuBilày,thìnóñưHcbiu
dianbWngmDtñonthnnghoScñoncongñưHcñ<nhhư/ngñitlxsangyvàkhông
quacácñimtương1ngtrunggiankhác.
Hìnhnh*nñưHcgilàdngbiudianhìnhhccAañ^th<G(V,E).ðôikhi
ngưitacũnggidngbiudianhìnhhclàmDtñ^th<.
b.ð6bàit8p
Bài1ChoGñ^th<g^m4phMnG1,G2,G3vàG4nhưsau:
a.Chjrat*pñjnh,cnh(vôhư/ng,cóhư/ng,khuyên,..)cAamJiñ^th<ñãcho?Chj
loiñ^th<ñó?
b.ð^th<G,G1,G2,G3,G4vàG5cóliênthôngko?Nuñ^th<koliênthônghãy
chjracácthànhphMnliênthông?