Math IA Finding the Shortest Cycle in the Neighborhood PDF

Preview

Summary

To choices an appropriate math internal assessment topic is the challenge for many IB students, I’m no exception. In daily practice, I have huge interested in graph theory, and I have done a lot of investigations on that parts in class. But I found that my knowledge of graph theory was limited to th...

Description

Finding the Shortest Cycle in the Neighborhood Ma t h e ma t i c sSL Ca n d i da t en umbe r： h p b 19 0 Ex a ms e s s i o n :Ma y2 0 2 0 Sc h oo ln u mb e r :0 4 9 15 3 Wo r dc o u nt ：1 65 3

I nt r od u c t i o n Toc h oi c e sa na p p r o p r i a t ema t hi n t e r na la s s e s s me n tt o pi ci st h ec h a l l e n g ef o rma n yI Bs t u d e n t s ,I ’ m n oe x c e p t i o n .I nd a i l yp r a c t i c e , Iha v ehu g ei n t e r e s t e di ng r a p ht h e or y , a n dIh a v ed o neal o to f i nv e s t i g a t i o n so nt h a tpa r t si nc l a s s . Bu tIf o un dt h a tmykn o wl e d g eo fgr a p ht h e o r ywa sl i mi t e dt o t h et h e o r e t i c a lkn o wl e d g eo ft e x t b o o ks .Iwa ntt ou s et h i sa sas t a r t i n gp o i ntt oc on n e c twh a tI ' v e l e a r n e dwi t hmyd a i l yl i f e .Fi n a l l y ,Is e t t l e dons o me t h i n gt h a twa sf u n da me n t a la i di nmyDi p l oma .

Is t i l lr e me mb e ron ed a y， Ih a v ea na p p o i n t me n twi t hmyf r i e n dsa tar e s t a u r a n tne a rmyh o me . Af t e rd i n ne r ,Id e c i d e dt owa l kh o met oe x e r c i s e .Io p e n e dt h ema pa p pa n df ou n dt h a tt h e r ewe r e ma n yr o u t e sf r o mt hi sr e s t a ur a n tt omyh o me .Th ed i ffe r e n tr o ut e st og oh o mewi t hd i ffe r e n tt i me a nd d i s t a n c ema k emev e r yi n t e r e s t e di n ,a n dc ur i o usa bo u twh a tt hes h or t e s tc y c l ei nt he n e i g h bo r h o o d .Th i sl e f tmewi t haq ue s t i o n ,a n dwhe nIg o th o me ,Ib e g a nt os t u d yt h i squ e s t i o n .I ' m g oi n gt ou s egr a pht h e o r yt ofin dt h es ho r t e s tc y c l ei nt hen e i g h bo r h o o d .I nt h i se xp l o r a t i o n ,Ia i mt o s o l v et h eCh i ne s ePo s t ma nPr o b l e m,a ndIwi l lu s eDi j ks t r a ’ sa l g o r i t hm i nt h ep r oc e s st ofin dt h e s h or t e s tp a t hb e t we e nt wov e r t i c e s .

I nt h i si n v e s t i g a t i o n ,myma i ng o a lwa st oa p p l ywh a tIl e a r n e di nc l a s st or e a ll i f es o me wh e r e o u t s i d eo fl e s s o ne n v i r o n me n t , s ot ha tt h e ya r en ol o n g e rj u s tat h e o r y ,b u ta ni s s ueo rs o med a t e si n r e a l i t y . Then e x tt i meIe n c ou n t e rs o medi ffic u l t i e si nl i f e ,Ic a na l s ot r yt ous ema t hk n o wl e d g e wh i c hIg a i nf r o ml e s s o n st os o l v e .Mo r e o v e r , t h edi ffic u l t yoft h e s eq u e s t i o n sa n dt h ed e p t ho f ma t h e ma t i c si tr e qu i r e st ob es o l v e dmo t i v a t e smet oe x p l o r ed e e pe ri nt ot h er e a l mo fma t h e ma t i c s .

Ho wt ofindac y c l eo fmi ni muml e n gt h Fo rt h ec o n v e n i e nc eofp r o c e s s i n g , Ic a ns i mp l i f yt hema pi nt oag r a p h , ma d eo fd o t sa n dl i ne s .I n ma t h e ma t i c s ,t h e“ d o t ”i nagr a p hi sr e f e r r e dt oa s“ v e r t i c e s ”a n dl i n e sa r er e f e r r e dt oa s“ e dg e s ” .I n myc a s e ,i ft h er oa d sa r ec on s t r u c t e da se d g e s ,t h e nc r o s s r o a d sna t u r a l l yb e c o met h ev e r t i c e si nt h e g r a p h .

Us i n gBa i d uma p ,Ime a s u r e dt h el e n g t h so fd i ffe r e n tr oa d sa n dma d et h e mi n t oag r a p h :

I nt h i sg r a p h ,t hee d g e sa r el a be l l e da st h e i rl e n g t h s .Su c hl a b e l sa r eu s ua l l yc a l l e d“ we i g h t ” , a n da g r a p ht h a th a se d g e swi t hwe i gh t si sc a l l e da“ we i gh t e dgr a p h” .Myg o a li st ofin dt hec y c l eo f mi n i mum we i g h tt h a tc o v e r sa l le d g e s . Wh e r eIs t a r td o e sn o tma t t e ri nt h i sc a s ebe c a u s ea l le d g e s a r ec on n e c t e dt ov e r t i c e ss oac y c l et h a tc o n t a i nsa l lt h ee d g e smu s tp a s st h r o u g ha l lt h ev e r t i c e s .

I fIwi s ht owa l kt hel e a s td i s t a n c ea n dpa s se v e r yr o a di nt h ec o mmu n i t y ,t hemo s te ffic i e n twa yi s a pp a r e n t l yt owa l ke a c hr o a de x a c t l yo n c e . Ag r a p ht ha tc o nt a i n sac y c l et op a s se v e r ye dg ee x a c t l y o n c ei sc a l l e da n“ Eul e r i a ng r a p h ” ,a n da c c o r d i n gt o ( h t t p s : / / ma t h wo r l d . wol f r a m. c o m/ Eu l e r i a n Gr a ph . h t ml ) ,a nEu l e r i a ng r a phc a n n o th a v ev e r t i c e so f o d dd e gr e e .Na me l y , n ov e r t i c e sc a nh a v ea no d dn u mb e ro fe d g e sc o nn e c t e dt ot h e m.I nmyc a s e ,B,

D,E, F ,G,Ha r ea l lv e r t i c e swi t ho ddd e g r e e ,s ot h i sg r a p hi sn o tEu l e r i a n .I fav e r t e xh a sa ne v e n d e g r e e , t h e ni tc a nb ee n t e r e da n de x i t e dv i ad i ffe r e n te d g e s . Ho we v e r ,f o rav e r t e xwi t ho d dd e gr e e , s o mee d g e sh a v et ob er e p e a t e dt oe n t e ra nde x i tt hi sv e r t e x .Th e r e f or e , t h i sp r o b l e mh a st ob e s o l v i n gwi t hr e p e a t i n gwa l ksa mo n gd i ffe r e n tv e r t i c e swi t ho ddd e g r e e ,t h e n c emya i ms h o u l db et o fin dt h emi n i mu m we i g h twa l kb e t we e nt h ev e r t i c e sB,D,E, F ,G,H.

Th i sp r o bl e mo ffin di n gac y c l eo fmi n i mumwe i gh ti sc a l l e dt h e“ Ch i ne s ePo s t ma nPr o b l e m ( CPP) ” ,a ndi no r d e rt os ol v et h eCPPf o rt h i sgr a p h, Iwi l lu s ea na l g o r i t h mc a l l e dt h eDi j k s t r a ’ s a l g o r i t h mt ofin dt h ewa l ko fmi n i mu m we i g h tb e t we e nt h ev e r t i c e s .

Di j ks t r a ’ sa l g o r i t hm1 Di j ks t r a ’ sa l g o r i t h mi su s e dt ofin dt h ewa l ko fmi ni mu m we i g h tf r o mo n ev e r t e xt oa n o t h e r . I two r k s b yt r y i n ga l lt h ed i ffe r e n twa l k st ofin dt h es h o r t e s ton e .

Fo re x a mp l e , i fIa mt ofin dt h es h o r t e s tp a t hf r o mBt oD:

Ia r b i t r a r i l ys t a r twi t ho n eo ft h ev e r t e x .I n t h i sc a s eIwi l ls t a r twi t hB.

Fi r s t l y ,Il a b e lBwi t h0 .

1https://www.programiz.com/dsa/dijkstra-algorithm

Th e nIwi l lg ot ot hea d j a c e n tv e r t i c e s o fB, a n dl a b e lt h e mb yt h el e n gt hI n e e dt ot a k et or e a c ht h e m.

I ft h el e n g t ho ft h ep a t hIt a k et o r e a c hav e r t e xi ss ma l l e rt h a nt h e f o r me rl a b e lo nt h ev e r t e x,Iwi l l r e pl a c et hel a b e lwi t ht h es ma l l e r l a b e l . I ft h ep a t hi sl o n g e r ,d ono t up d a t et hel a b e l . Fo re xa mpl e ,BED i s1 4 2 +1 00 =2 4 2 ,bu tBCDi s 10 6 +1 9 1=2 9 7 .Si n c e2 4 2...