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

Bước sang năm bản lề của thế kỷ 21, nhìn lại thế kỷ 20 là thế kỷ mà con người đạt được nhiều thành tựu khoa học rực rỡ nhất, một trong những thành tựu đó là sự bùng nổ của ngành khoa học máy tính. Sự phát triển kỳ diệu của máy tính trong thế kỷ này gắn liền với sự phát triển toán học hiện đại, đó là toán rời rạc. Toán học rời rạc nghiên cứu các cấu trúc có tính chất rời rạc không liên tục. Toán rời rạc bao gồm các lĩnh vực như quan hệ, lý thuyết đồ thị, lôgíc toán, ngôn ngữ hình thức . trong đó lý thuyết đồ thị là một bộ phận trọng tâm với nhiều khối lượng kiến thức khá lý thú và được nghiên cứu nhiều nhất. Toán rời rạc nói chung và lý thuyết đồ thị nói riêng là công cụ thiết yếu cho nhiều ngành khoa học kỹ thuật, và là một thành phần quan trọng trong học vấn đối với sinh viên các ngành kỹ thuật đặc biệt sinh viên ngành Tin học. Lý thuyết đồ thị, với cách tiếp cận đối tượng nghiên cứu và phương pháp tư duy khá độc đáo thực sự ngày càng hữu ích có nhiều ứng dụng phong phú và gây không ít bất ngờ. Máy tính mà bản thân nó với các quá trình làm việc mang tính rời rạc, nên điều này tương hợp gắn chặt lý thuyết đồ thị với công nghệ máy tính trong việc nghiên cứu các đối tượng có tính chất rời rạc. Lý thuyết đồ thị có nhiều ứng dụng thực tiễn đặc biệt là trong lĩnh vực Tin học, muốn hiểu biết sâu sắc các vấn đề Tin học cần nắm vững các kiến thức về Toán học rời rạc mà trong đó đặc biệt là lý thuyết đồ thị. Từ những nhận thức trên, với đề tài "Một số vấn đề ứng dụng của đồ thị trong Tin học" đây không chỉ là nhiệm vụ em phải thực hiện trong kỳ bảo vệ luận văn tốt nghiệp mà thực sự đây là đề tài mà em rất quan tâm và say mê nghiên cứu. Với tấm lòng biết ơn sâu sắc, em xin chân thành cảm ơn Thầy giáo Pgs. Ts Đỗ Đức Giáo là người trực tiếp, tận tình, chu đáo giảng dạy và hướng dẫn em hoàn thành cuốn luận văn này. Nhân dịp này em cũng xin cảm ơn sự giúp đỡ, dạy bảo tận tình của 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à những bạn học đã đóng góp những ý kiến bổ ích cho bản luận văn này. Do trình độ hiểu biết còn hạn chế, thời gian chuẩn bị không nhiều, bản luận văn này còn nhiều sai sót và chưa đầy đủ, em rất mong nhận được sự góp ý của các thầy cô và các bạn quan tâm.

doc7 trang | Chia sẻ: lvcdongnoi | Ngày: 30/06/2013 | Lượt xem: 1551 | Lượt tải: 0download
Bạn đang xem nội dung tài liệu Ứng dụng đồ thị trong tin học, để tải tài liệu về máy bạn click vào nút DOWNLOAD ở trên
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

Các file đính kèm theo tài liệu này:

  • docTomTat.doc
  • docBttat.doc
  • rarUng dung do thi trong Tin hoc.rar