Ứng dụng đồ thị trong tin học

Giíi thiÖu : Lý thuyÕt ®å thÞ ®­îc nghiªn cøu vµ ph¸t triÓn do nÈy sinh tõ nhu cÇu gi¶i quyÕt c¸c vÊn ®Ò thùc tiÔn, cã nhiÒu øng dông trong c¸c ngµnh khoa häc kü thuËt kh¸c nhau. §Ò tµi thùc hiÖn lµ "Mét sè vÊn ®Ò øng dông cña ®å thÞ trong Tin häc", ®©y lµ ®Ò tµi nghiªn cøu lý thuyÕt gi¶i quyÕt nhiÖm vô lµ lµm s¸ng tá h¬n c¬ së to¸n cho Tin häc ®ång thêi nªu ra nh÷ng kh¶ n¨ng øng dông cña ®å thÞ trong Tin häc theo tõng néi dung cña Lý thuyÕt ®å thÞ. Lý thuyÕt ®å thÞ ®ãng vai trß lµm c¬ së to¸n cho Tin häc v× ®å thÞ lµ mét bé phËn cña To¸n rêi r¹c, b¶n chÊt vµ cÊu tróc cña ®å thÞ mang tÝnh rêi r¹c mµ c«ng cô chÝnh trong Tin häc lµ m¸y tÝnh, c¸c qu¸ tr×nh xö lý l­u tr÷ th«ng tin trong m¸y tÝnh còng mang tÝnh rêi r¹c, nªn ®iÒu nµy t­¬ng hîp gi÷a ®å thÞ vµ m¸y tÝnh. Lý thuyÕt ®å thÞ cã c¶ mét khèi l­îng kiÕn thøc lý thuyÕt ®å sé, øng dông cña ®å thÞ còng rÊt réng, ®Ò tµi ®­îc thùc hiÖn chØ bao gåm nh÷ng néi dung c¬ së vµ träng t©m cña ®å thÞ, vµo mçi néi dung lý thuyÕt sÏ ®­a ra nh÷ng vÝ dô øng dông minh ho¹ nh»m lµm râ sù øng dông cña phÇn lý thuyÕt ®ã. Trong c¸c øng dông rÊt réng lín cña ®å thÞ c¸c vÝ dô ®­îc ®­a ra còng ch­a ®Çy ®ñ nh­ng thùc sù ®ã còng lµ ®¹i diÖn vµ phÇn nµo lµm s¸ng tá c¸c vÊn ®Ò øng dông cña ®å thÞ. LuËn v¨n ®­îc thùc hiÖn ®i theo tõng phÇn néi dung cña lý thuyÕt ®å thÞ gåm 5 ch­¬ng nh­ sau : Ch­¬ng I Mét sè vÊn ®Ò c¬ b¶n cña ®å thÞ Nghiªn cøu c¸c vÊn ®Ò øng dông cña ®å thÞ, tr­íc hÕt ph¶i t×m hiÓu c¸c vÊn ®Ò c¬ b¶n cña lý thuyÕt ®å thÞ, ®©y lµ c¬ së ®Ó t×m hiÓu s©u s¾c h¬n c¸c vÊn ®Ò tiÕp theo. Trong ch­¬ng sÏ tr×nh bµy c¸c ®Þnh nghÜa vµ tÝnh chÊt c¬ b¶n cña ®å thÞ, nh­ng tãm l¹i ta quan t©m ®Õn c¸c vÊn ®Ò chÝnh sau: - TÝnh rêi r¹c : §å thÞ lµ cÊu tróc rêi r¹c gåm c¸c ®Ønh vµ c¹nh, thÓ hiÖn ®óng nh­ c¸c yÕu tè rêi r¹c trong m¸y tÝnh. C¸c yÕu tè rêi r¹c nhau nh­ng kh«ng hoµn toµn ®éc lËp nhau mµ gi÷a chóng cã sù liªn hÖ, cã mèi quan hÖ víi nhau. Nghiªn cøu mèi quan hÖ gi÷a c¸c yÕu tè rêi r¹c lµ quan träng, ®iÒu nµy quy ®Þnh b¶n chÊt vµ cÊu tróc cña ®å thÞ. - C¸ch biÓu diÔn vµ l­u tr÷ cña ®å thÞ trªn m¸y tÝnh : CÊu tróc d÷ liÖu liªn quan chÆt chÏ ®Õn gi¶i thuËt, c¸ch thøc biÓu diÔn ®å thÞ trªn m¸y tÝnh ¶nh h­ëng nhiÒu ®Õn viÖc gi¶i c¸c bµi to¸n øng dông trªn m¸y tÝnh. §Ò cËp tíi vÊn ®Ò nµy cã 3 ph­¬ng ph¸p chÝnh: a) BiÓu diÔn b»ng ma trËn kÒ Ph­¬ng ph¸p nµy dùa trªn mèi hÖ gi÷a tÊt c¶ c¸c cÆp ®Ønh, ®å thÞ n ®Ønh t­¬ng øng víi ma trËn vu«ng cÊp n, lµ ph­¬ng ph¸p ®­îc dïng phæ biÕn, thÓ hiÖn cho hÇu hÕt c¸c lo¹i ®å thÞ. ­u ®iÓm lµ dÔ dµng x¸c ®Þnh ®­îc c¸c cÆp ®Ønh cã kÒ nhau hay kh«ng hoÆc lµ rÊt thuËn tiÖn khi cÇn tÝnh sè bËc cña mçi ®Ønh, ngoµi ra ta cã thÓ biÕt ®­îc sè ®­êng ®i víi ®é dµi x¸c ®Þnh gi÷a 1 cÆp ®Ønh nµo ®ã b»ng c¸ch tÝnh tÝch cña ma trËn kÒ. Nh­îc ®iÓm cña ph­¬ng ph¸p nµy lµ kh«ng phô thuéc vµo sè c¹nh cña ®å thÞ, ta lu«n ph¶i sö dông n2 ®¬n vÞ bé nhí ®Ó l­u tr÷ nã. b) BiÓu diÔn b»ng danh s¸ch c¹nh (cung) §©y lµ c¸ch biÓu diÔn theo c¹nh, phô thuéc vµo sè c¹nh cña ®å thÞ. Danh s¸ch c¹nh (cung) lµ bao gåm tÊt c¶ c¸c c¹nh (cung) cña ®å thÞ, mçi mét c¹nh (cung) gåm c¸c thµnh phÇn: ®Ønh ®Çu, ®Ønh cuèi, träng sè (nÕu cã). Nh­ vËy ®¬n vÞ bé nhí ®Ó l­u tr÷ ®å thÞ m c¹nh lµ 2m (hoÆc 3m nÕu cã träng sè). Nh­îc ®iÓm cña ph­¬ng ph¸p nµy lµ khã x¸c ®Þnh c¸c ®Ønh kÒ víi mét ®Ønh cho tr­íc hoÆc lµ tÝnh sè bËc cña mét ®Ønh. c) BiÓu diÔn b»ng danh s¸ch kÒ Víi ph­¬ng ph¸p nµy th× øng víi mçi ®Ønh lµ 1 danh s¸ch liªn kÕt c¸c ®Ønh kÒ víi nã, víi ®å thÞ cã h­íng n ®Ønh m c¹nh th× ®¬n vÞ bé nhí ®Ó l­u tr÷ lµ n + m. C¸ch biÓu diÔn nµy thÝch hîp cho c¸c thuËt to¸n lµm viÖc víi cÊu tróc ®å thÞ hay thay ®æi nh­ thªm bít c¹nh. VÒ mÆt øng dông, khi ®Ò cËp tíi c¸c lo¹i ®å thÞ ®å thÞ ®Æc biÖt, trong ch­¬ng sÏ nªu nh÷ng m« h×nh cÊu tróc m¹ng (topolopy) d¹ng ®iÓm - ®iÓm cã ¸p dông ®Õn c¸c d¹ng cña ®å thÞ ®Æc biÖt, nh­ cÊu tróc m¹ng h×nh sao, h×nh vßng, b¸nh xe... HoÆc ta xÐt øng dông trong mét hÖ thèng th«ng tin nh­ m¹ng m¸y tÝnh, cã nh÷ng ®­êng truyÒn gi÷a 2 ®iÓm lµ rÊt quan träng, ®Ó tr¸nh nh÷ng sù cè cÇn cã c¸c ®­êng truyÒn tin dù phßng kh¸c, ®Ó xem xÐt c¸c ®­êng truyÒn dù phßng ta cÇn xem xÐt ®Õn ®­êng ®i, sè ®­êng ®i gi÷a 2 ®iÓm truyÒn tin ®ã. Nh­ vËy ta thÊy øng dông nµy liªn quan tíi ®­êng ®i, sè ®­êng ®i gi÷a 2 ®Ønh trong m« h×nh ®å thÞ t­¬ng øng. Ch­¬ng II. Sè æn ®Þnh vµ t« mµu ®å thÞ Ch­¬ng gåm 2 néi dung chÝnh: Sè æn ®Þnh vµ s¾c sè ®å thÞ. Sè æn ®Þnh lµ sè æn ®Þnh trong, sè æn ®Þnh ngoµi vµ nh©n ®å thÞ. Nh­ ®· nªu trªn, mèi quan hÖ gi÷a c¸c yÕu tè rêi r¹c lµ quan träng, ®Ò cËp tíi c¸c vÊn ®Ò nµy ta l¹i thÊy ®­îc râ mèi quan hÖ gi÷a c¸c tËp ®Ønh. TËp æn ®Þnh trong l¹i tËp c¸c ®Ønh cña ®å thÞ sao cho nh÷ng ®Ønh trong tËp nµy cã mèi quan hÖ lµ kh«ng kÒ nhau. TËp æn ®Þnh ngoµi hay cßn gäi lµ tËp thèng trÞ, nh÷ng ®Ønh trong tËp nµy cã mèi quan hÖ "thèng trÞ" c¸c ®Ønh kh¸c ngoµi tËp, quan hÖ "thèng trÞ" nµy ®­îc hiÓu lµ lu«n tån t¹i 1 ®Ønh thuéc tËp thèng trÞ sao cho nã kÒ víi 1 ®Ønh bÊt kú ngoµi tËp. Nh©n ®å thÞ chÝnh lµ tËp võa lµ tËp æn ®Þnh trong võa lµ tËp æn ®Þnh ngoµi, ®èi víi tËp æn ®Þnh trong ta quan t©m tíi tËp cã lùc l­îng cùc ®¹i, víi tËp æn ®Þnh ngoµi ta quan t©m tíi tËp cã lùc l­îng cùc tiÓu. VÒ mÆt øng dông cña sè æn ®Þnh : sè æn ®Þnh ngoµi th­êng ®­îc ¸p dông cho bµi to¸n ®Æt väng g¸c, tõ ý t­ëng nµy ta xÐt 1 øng dông phôc vô cho viÖc lËp tr×nh ch¬i cê ca r«. Trong kü thuËt ch¬i cê Ca r« qu©n cã kh¶ n¨ng th¾ng nhiÒu h¬n lµ qu©n cã kh¶ n¨ng thèng trÞ ®­îc qu©n ®èi ph­¬ng, sö dông cÊu tróc d÷ liÖu lµ ®å thÞ cho thÕ cê ta cã thÓ ¸p dông ph­¬ng ph¸p t×m tËp æn ®Þnh trong ®Ó tÝnh n­íc ®i cã lîi nhÊt cho cê ca r«, h¬n n÷a viÖc tÝnh to¸n ®­êng ®i, n­íc ®i còng sÏ ®­îc thuËn lîi h¬n. VÊn ®Ò t« mµu ®å thÞ lµ viÖc t×m sè mµu tèi thiÓu ®Ó t« c¸c ®Ønh ®å thÞ sao cho nh÷ng ®Ønh kÒ nhau ph¶i kh¸c mµu nhau hay cßn gäi lµ t×m s¾c sè ®å thÞ. VÒ mÆt øng dông ta cã thÓ thÊy ®­îc ¸p dông cho bµi to¸n lËp lÞch. LËp lÞch lµ viÖc bè trÝ hîp lý ®Ó sao cho kh«ng cã sù trïng lÆp nh­ lµ vÒ thêi gian vµ ®Þa ®iÓm... th× t­¬ng øng trong ®å thÞ ph¶i t« mµu c¸c ®Ønh sao cho 2 ®Ønh kÒ nhau th× kh«ng trïng mµu. VËy nªn ch¨ng ph¸t triÓn nghiªn cøu vÊn ®Ò t« mµu ®å thÞ mét c¸ch ®Çy ®ñ h¬n ®Ó phôc vô cho bµi to¸n lËp lÞch. Ch­¬ng III. Chu tr×nh, ®­êng Euler vµ Hamilton - Chu tr×nh, ®­êng ®i Euler : Chu tr×nh (®­êng ®i) Euler lµ chu tr×nh (®­êng ®i) ®i qua tÊt c¶ c¸c c¹nh ®å thÞ mçi c¹nh ®óng mét lÇn. Cã thÓ nãi ®· nhiÒu ng­êi biÕt ®Õn chu tr×nh, ®­êng ®i Euler khi mµ ch­a häc ®Õn lý thuyÕt vÒ Euler bëi v× ta hay gÆp c¸c bµi to¸n ®è vui lµ cho tr­íc mét h×nh vÏ víi yªu cÇu t« l¹i h×nh ®ã chØ b»ng mét nÐt liÒn. Cã nhiÒu vÊn ®Ò thùc tiÔn cã thÓ ¸p dông chu tr×nh (®­êng ®i) Euler ®Ó gi¶i quyÕt nh­ lµ t×m hµnh tr×nh cho ng­êi ph¸t th­, xe röa ®­êng... sao cho hµnh tr×nh lµ tèi ­u nhÊt. - Chu tr×nh, ®­êng ®i Hamilton : Chu tr×nh (®­êng ®i) Hamilton lµ chu tr×nh (®­êng ®i) ®i qua tÊt c¶ c¸c ®Ønh mçi ®Ønh ®óng mét lÇn. Kh¸c víi chu tr×nh, ®­êng ®i Euler ®· cã c¸c ®iÒu kiÖn cÇn vµ ®ñ ®Ó nhËn biÕt nã trong ®å thÞ, cßn chu tr×nh, ®­êng ®i Hamilton míi chØ cã ®iÒu kiÖn ®ñ. Chu tr×nh, ®­êng ®i Hamilton còng cã nhiÒu øng dông thùc tiÔn vÝ dô nh­ cho 1 hÖ thèng m¹ng, mét m¸y nµo ®ã cÇn göi ®i 1 th«ng ®iÖp tíi tÊt c¶ c¸c m¸y kh¸c theo kiÓu truyÒn tin l­u vµ chuyÓn tiÕp h·y t×m ®­êng truyÒn tin thÝch hîp nhÊt. Chu tr×nh, ®­êng ®i Euler vµ Hamilton cã tÇm quan träng vµ ý nghÜa øng dông cao, nh­ng ®©y còng thùc sù lµ bµi to¸n khã, viÖc ®Ò cËp ®Çy ®ñ lý thuyÕt còng ch­a ®­îc thùc hiÖn mét c¸ch trän vÑn ë trong ch­¬ng. Ch­¬ng IV §­êng ®i ng¾n nhÊt trong ®å thÞ Cã nhiÒu bµi to¸n d¹ng tèi ­u cã thÓ vËn dông lý thuyÕt vÒ chu tr×nh, ®­êng ®i Euler hoÆc Hamilton ®Ó gi¶i quyÕt, ngoµi ra ta cã thÓ ¸p dông lý thuyÕt vÒ ®­êng ®i ng¾n nhÊt trong ®å thÞ ®Ó gi¶i quyÕt lo¹i bµi to¸n nµy. Bµi to¸n t×m ®­êng ®i ng¾n nhÊt cã nhiÒu øng dông vÊn ®Ò lµ cÇn ®­a ra thuËt to¸n h÷u hiÖu ®Ó gi¶i quyÕt lo¹i bµi to¸n nµy. Cã nhiÒu thuËt to¸n ®­îc nªu ra, nh­ng ta sÏ quan t©m tíi thuËt to¸n ®­îc dïng phæ biÕn vµ cã nhiÒu ­u ®iÓm ®ã lµ thuËt to¸n Dijkstra cho ®å thÞ cã träng sè. Nguyªn t¾c cña nhiÒu thuËt to¸n lµ ®¸nh träng sè d(v) c¸c ®Ønh sau ®ã tiÕn hµnh ®iÒu chØnh l¹i träng sè c¸c ®Ønh theo ®iÒu kiÖn sau: NÕu d[u] + c[u, v] < d[v] th× d[v] := d[u] + c[u, v] Trong ®ã träng sè d[v] lµ ®é dµi ®­êng ®i ng¾n nhÊt tõ ®Ønh xuÊt ph¸t tíi ®Ønh v, c[u, v] lµ ma trËn träng sè. T­ t­ëng cña thuËt to¸n Dijkstra lµ x©y dùng dÇn dÇn tËp S c¸c ®Ønh cã träng sè nhá nhÊt: mçi lÇn t×m ®­îc ®Ønh cã träng sè nhá nhÊt th× dïng nã ®Ó ®iÒu chØnh träng sè c¸c ®Ønh kÒ víi nã sau ®ã ®­a ®Ønh cã träng sè nhá nhÊt võa t×m ®­îc vµo tËp S. VÒ mÆt øng dông : Trong lÜnh vùc Tin häc, xÐt ë 1 m¹ng m¸y tÝnh nhiÒu khi ng­êi ta cÇn x¸c ®Þnh mét ®­êng truyÒn cã thêi gian truyÒn tin ng¾n nhÊt gi÷a 2 m¸y nµo ®ã. §Ó thùc hiÖn ®iÒu nµy cã thÓ m« h×nh m¹ng b»ng ®å thÞ sau ®ã vËn dông thuËt to¸n t×m ®­êng ®i ng¾n nhÊt ®Ó gi¶i quyÕt. C¸c øng dông th× cã nhiÒu, trong ch­¬ng nµy ta sÏ ®Ò cËp mét c¸ch cô thÓ vÒ thuËt to¸n Viterbi vËn dông lý thuyÕt ®­êng ®i ng¾n nhÊt ®Ó söa gãi tin bÞ truyÒn sai trong 1 hÖ thèng th«ng tin, ®©y lµ 1 øng dông kh¸ thiÕt thùc v× nã hay b¾t gÆp trong 1 hÖ thèng truyÒn tin. Khi nãi ®Õn bµi to¸n t×m ®­êng ®i ng¾n nhÊt, ng­êi ta còng hay më réng thµnh bµi to¸n t×m ®­êng ®i dµi nhÊt. Víi vÊn ®Ò nµy trong ch­¬ng còng nªu ra cô thÓ øng dông ®å thÞ cho viÖc lËp lÞch thi c«ng 1 c«ng tr×nh lín. §©y lµ 1 øng dông thuéc lo¹i bµi to¸n tèi ­u vËn dông ®­êng ®i dµi nhÊt vµ ®ång thêi còng lµ øng dông cho c«ng t¸c lËp lÞch. §å thÞ cho øng dông nµy gäi lµ s¬ ®å m¹ng Pert, ®©y còng lµ lo¹i ®å thÞ cã ­u tiªn tr­íc sau vµ cuèi ch­¬ng sÏ xÐt ®Õn øng dông cña lo¹i ®å thÞ nµy trong viÖc lËp tr×nh song song. Ch­¬ng V. Mét sè vÊn ®Ò vÒ c©y Lµ néi dung cuèi cïng cña luËn v¨n, ch­¬ng nµy sÏ ®Ò cËp ®Õn nhiÒu øng dông cña c©y cho viÖc ¸p dông, ph©n tÝch c¸c gi¶i thuËt c¬ së trong kü n¨ng lËp tr×nh. C©y lµ tr­êng hîp riªng cña ®å thÞ, cã nh÷ng ®Æc tr­ng riªng dÔ nhËn thÊy ®ã lµ lu«n tån t¹i 1 ®­êng ®i duy nhÊt gi÷a mäi cÆp ®Ønh, biÕt ®­îc sè ®Ønh th× lu«n biÕt ®­îc sè c¹nh... §Ó nghiªn cøu hÕt c¸c tÝnh chÊt vÒ c©y th× ®ã lµ c¶ 1 khèi l­îng kiÕn thøc lín, ch­¬ng nµy chØ ®Ò cËp tíi nh÷ng vÊn ®Ò c¬ b¶n nhÊt vÒ c©y vµ tËp trung khai th¸c nh÷ng øng dông cña nã. Sù øng dông c©y trong viÖc ph©n tÝch c¸c gi¶i thuËt ®ã lµ nhiÒu thuËt to¸n cã thÓ m« h×nh b»ng c©y, hay nãi c¸ch kh¸c lµ dïng c©y ®Ó thÓ hiÖn, biÓu diÔn thuËt to¸n. Khi nh×n vµo c©y thÓ hiÖn thuËt to¸n ta sÏ hiÓu s©u s¾c thuËt to¸n h¬n lµ khi nghe ph¸t biÓu thuËt to¸n b»ng lêi bëi v× c©y cho ta c¸i nh×n trùc quan sinh ®éng, d­êng nh­ thÊy ®­îc hÕt c¸c b­íc ®i ch­¬ng tr×nh thuËt to¸n khi ch¹y trªn m¸y tÝnh. Ngoµi ra nh×n vµo m« h×nh c©y biÓu diÔn thuËt to¸n dÔ t¹o cho ta ®­îc t­ duy lËp tr×nh cµi ®Æt thuËt to¸n h¬n lµ khi ta ®äc thuËt to¸n ®­îc ph¸t biÓu b»ng lêi hay xem vµo s¬ ®å khèi cña thuËt to¸n. C©y cã nhiÒu øng dông quan träng mµ trong ch­¬ng sÏ ®Ò cËp tíi nh­ c©y t×m kiÕm, c©y quyÕt ®Þnh, c©y m· ho¸ tiÒn tè, c©y biÓu thøc... §©y lµ nh÷ng øng dông rÊt thiÕt thùc trong kü thuËt lËp tr×nh, ch¼ng h¹n nh­ trong mét ch­¬ng tr×nh nµo ®ã, mét ng­êi nhËp vµo mét biÓu thøc nhÞ nguyªn to¸n häc vËy lµm thÕ nµo mµ biÓu diÔn, l­u tr÷ vµ xö lý biÓu thøc nµy trong m¸y tÝnh, ®iÒu nµy cã thÓ thùc hiÖn ®­îc nhê sù vËn dông c©y biÓu diÔn biÓu thøc. Trong lý thuyÕt ®å thÞ, khi nãi vÒ c©y th× c©y bao trïm lµ vÊn ®Ò kh«ng thÓ thiÕu. C©y bao trïm còng cã nhiÒu øng dông, ®Æc biÖt lµ c©y bao trïm ng¾n nhÊt, ta còng cã thÓ vËn dông nã ®Ó gi¶i lo¹i bµi to¸n tèi ­u vÝ dô nh­ bµi to¸n nèi m¹ng m¸y tÝnh sao cho chÝ phÝ nèi m¹ng lµ thÊp nhÊt. §Ó t×m c©y bao trïm nhá nhÊt trong ch­¬ng sÏ giíi thiÖu ®Õn hai thuËt to¸n Kruskal vµ Prim, mçi thuËt to¸n ®Òu cã nh÷ng ®Æc ®iÓm riªng. Còng cã nh÷ng lóc ta chØ cÇn t×m c©y bao trïm nãi chung, ®Ó t×m c©y bao trïm trong ch­¬ng còng sÏ ®Ò cËp tíi thuËt to¸n t×m kiÕm ­u tiªn theo chiÒu réng vµ chiÒu s©u, ®©y lµ thuËt to¸n rÊt c¬ së nh­ng lµ quan träng v× nã ®­îc ¸p dông trong hÇu hÕt c¸c thuËt to¸n liªn quan ®Õn ®å thÞ. KÕt luËn : §Ò tµi ®­îc thùc hiÖn xong còng ®· cã ®­îc nh÷ng kÕt qu¶ nhÊt ®Þnh trong viÖc lµm s¸ng tá ®­îc c¬ së lý thuyÕt ®å thÞ, thÓ hiÖn ®­îc vai trß cña ®å thÞ lµ lµm c¬ së to¸n cho Tin häc, phôc vô ®¾c lùc trong kü thuËt lËp tr×nh vµ ®ång thêi nªu ®­îc tÝnh øng dông cña ®å thÞ theo tõng néi dung lý thuyÕt. Bªn c¹nh nh÷ng kÕt qu¶ ®¹t ®­îc còng cã nh÷ng ®iÒu ch­a ®­îc nh­ nhiÒu vÊn ®Ò cña ®å thÞ ch­a nªu ra ®­îc thuËt to¸n cô thÓ ®Ó gi¶i quyÕt, nhiÒu thuËt to¸n vÉn ch­a ®­îc cµi ®Æt. VÒ mÆt øng dông th× cßn cã nhiÒu øng dông cßn nªu chung chung, míi dõng l¹i trªn m« h×nh lý thuyÕt ch­a cã nh÷ng sè liÖu chøng minh hay lµ ch­¬ng tr×nh cµi ®Æt cô thÓ, khi ®i tõng néi dung lý thuyÕt ®å thÞ th× chØ nªu ®­îc c¸c øng dông cña phÇn néi dung lý thuyÕt ®ã mµ ch­a nªu ®­îc c¸c øng dông cña tæng hîp nhiÒu néi dung lý thuyÕt ®å thÞ. Cuèn luËn v¨n ®­îc hoµn thµnh sau thêi gian gÇn 3 th¸ng, t¸c gi¶ sÏ kh«ng thÓ nµo hoµn thµnh ®­îc ®Ò tµi cña m×nh nÕu nh­ kh«ng nhËn ®­îc sù gióp ®ì, h­íng dÉn tËn t×nh cña thÇy gi¸o Pgs. Ts §ç §øc Gi¸o, t¸c gi¶ xin ch©n thµnh bµy tá lßng biÕt ¬n ®èi víi thÇy Pgs. Ts §ç §øc Gi¸o vµ cïng toµn thÓ c¸c thÇy c« gi¸o, c¸n bé khoa C«ng nghÖ Th«ng tin tr­êng §¹i häc D©n lËp §«ng §« vµ b¹n bÌ ®· quan t©m, ®éng viªn gióp ®ì t¸c gi¶ hoµn thµnh cuèn luËn v¨n nµy. Hµ néi 6/2000 Sinh viªn thùc hiÖn: Phan Thanh Long. Môc lôc Trang Giíi thiÖu .................................................................................................. 1 Mét sè vÊn ®Ò c¬ b¶n cña ®å thÞ ............................................................. 1 Sè æn ®Þnh vµ t« mµu ®å thÞ .................................................................... 2 Chu tr×nh, ®­êng ®i Euler vµ Hamilton ................................................ 3 §­êng ®i ng¾n nhÊt trong ®å thÞ ............................................................ 4 Mét sè vÊn ®Ò vÒ c©y ............................................................................... 4 KÕt luËn .................................................................................................... 5