±à¼ÍƼö: |
±¾ÕÂÖ÷Òª½éÉÜÁ˰׺вâÊԵĸÅÄî¡¢ÌØµã¡¢»ù±¾²âÊÔÄÚÈÝ¡¢Óï¾ä¸²¸Ç±ê×¼¼°³ÌÐòÁ÷³ÌͼµÈ£¬Ï£Íû¶ÔÄãÓаïÖú¡£
±¾ÎÄÀ´×ÔÓÚcsdn£¬ÓÉ»ðÁú¹ûÈí¼þLinda±à¼¡¢ÍƼö¡£ |
|
°×ºÐ²âÊÔÓֳƽṹ²âÊÔ¡¢Í¸Ã÷ºÐ²âÊÔ¡¢Âß¼Çý¶¯²âÊÔ»ò»ùÓÚ ´úÂëµÄ²âÊÔ¡£°×ºÐ²âÊÔÊÇÒ»ÖÖ
²âÊÔÓÃÀýÉè¼Æ·½·¨£¬ºÐ×ÓÖ¸µÄÊDZ»²âÊ﵀ Èí¼þ£¬°×ºÐÖ¸µÄÊǺÐ×ÓÊÇ¿ÉÊӵģ¬ÄãÇå³þºÐ×ÓÄÚ²¿µÄ¶«Î÷ÒÔ¼°ÀïÃæÊÇÈçºÎÔË×÷µÄ¡£"°×ºÐ"·¨È«ÃæÁ˽â³ÌÐòÄÚ²¿Âß¼½á¹¹¡¢¶ÔËùÓÐÂ߼·¾¶½øÐвâÊÔ¡£"°×ºÐ"·¨ÊÇÇî¾Ù·¾¶²âÊÔ¡£ÔÚʹÓÃÕâÒ»·½°¸Ê±£¬²âÊÔÕß±ØÐë¼ì²é³ÌÐòµÄÄÚ²¿½á¹¹£¬´Ó¼ì²é³ÌÐòµÄÂß¼×ÅÊÖ£¬µÃ³ö²âÊÔÊý¾Ý¡£¹á´©³ÌÐòµÄ¶ÀÁ¢Â·¾¶ÊýÊÇÌìÎÄÊý×Ö¡£
°×ºÐ²âÊÔÊÇÒ»ÖÖµäÐ͵IJâÊÔ·½·¨
ÊÇÒ»ÖÖ°´ÕÕ³ÌÐòÄÚ²¿Âß¼½á¹¹ºÍ±àÂë½á¹¹Éè¼Æ²âÊÔÊý¾Ý²¢Íê³É²âÊÔµÄÒ»ÖÖ²âÊÔ·½·¨
²âÊÔ¸²¸ÇÈ«²¿´úÂë¡¢·ÖÖ§¡¢Â·¾¶ºÍÌõ¼þ
ËüÀûÓò鿴´úÂ빦ÄܺÍʵÏÖ·½Ê½µÃµ½µÄÐÅÏ¢À´È·¶¨ÄÄЩÐèÒª²âÊÔ¡¢ÄÄЩ²»ÐèÒª¡¢ÈçºÎÕ¹¿ª²âÊÔ
ÓÖ³ÆÎª½á¹¹²âÊÔ»òÂß¼Çý¶¯²âÊÔ?
°×ºÐ²âÊÔÌØµãÖ÷ÒªÓÐ
1. ¿ÉÒÔ¹¹³É²âÊÔÊý¾ÝÊ¹ÌØ¶¨³ÌÐò²¿·ÖµÃµ½²âÊÔ
2. ÓÐÒ»¶¨µÄ³ä·ÖÐÔ¶ÈÁ¿ÊÖ¶Î
3. ¿É»ñµÃ½Ï¶à¹¤¾ßÖ§³Ö
4. ͨ³£Ö»ÓÃÓÚµ¥Ôª²âÊԺͼ¯³É²âÊÔ(Ö÷ÒªÊǵ¥Ôª²âÊÔ)
°×ºÐ²âÊԵĻù±¾²âÊÔÄÚÈÝ
»ù±¾²âÊÔÄÚÈÝ
¶Ô³ÌÐòÄ£¿éµÄËùÓжÀÁ¢Ö´Ðз¾¶ÖÁÉÙ²âÊÔÒ»´Î
¶ÔËùÓеÄÂß¼Åж¨£¬È¡¡°Õ桱ÓëÈ¡¡°¼Ù¡±µÄÁ½ÖÖÇé¿ö¶¼ÖÁÉÙ²âÊÔÒ»´Î
ÔÚÑ»·µÄ±ß½çºÍÔËÐеı߽çÏÞÄÚÖ´ÐÐÑ»·Ìå
²âÊÔÄÚ²¿Êý¾Ý½á¹¹µÄÓÐЧÐÔ
°×ºÐ²âÊÔËù²ÉÓõIJâÊÔ·½·¨ÊÇ
Âß¼¸²¸Ç£¨°üÀ¨Óï¾ä¸²¸Ç¡¢·ÖÖ§¸²¸Ç¡¢Ìõ¼þ¸²¸Ç¡¢·ÖÖ§-Ìõ¼þ¸²¸Ç¡¢Ìõ¼þ×éºÏ¸²¸ÇÒÔ¼°Â·¾¶¸²¸Ç£©
ÁùÖÖÂß¼¸²¸Ç±ê×¼£ºÓï¾ä¸²¸Ç¡¢Åж¨¸²¸Ç¡¢Ìõ¼þ¸²¸Ç¡¢Åж¨/Ìõ¼þ¸²¸Ç¡¢Ìõ¼þ×éºÏ¸²¸ÇºÍ·¾¶¸²¸Ç·¢ÏÖ´íÎóµÄÄÜÁ¦³ÊÓÉÈõÖÁÇ¿µÄ±ä»¯¡£

Óï¾ä¸²¸ÇÒªÇ󣺶ÀÁ¢Ö´Ðз¾¶ÖÁÉÙÒ»´Î¡£Ã¿ÌõÓï¾äÖÁÉÙÖ´ÐÐÒ»´Î¡£
¡¤Ëü¶Ô³ÌÐòµÄÂß¼¸²¸ÇºÜÉÙ£¬ÊǺÜÈõµÄÂß¼¸²¸Ç±ê×¼
¡¤ÎªÁ˸ü³ä·ÖµØ²âÊÔ³ÌÐò£¬ÐèÒª²ÉÓúó±ß½²ÊöµÄÆäËûÂß¼¸²¸Ç·½·¨
¡¤ÎªÁ˱©Â¶³ÌÐòÖеĴíÎó£¬Óï¾ä¸²¸ÇÊÇ×îÆðÂëµÄ²âÊÔÒªÇó£¬ÒªÇóÉè¼Æ×ã¹»¶àµÄ²âÊÔÓÃÀý£¬Ê¹µÃÿһÌõÓï¾äÖÁÉÙ±»Ö´ÐÐÒ»´Î
¡¤Óï¾ä¸²¸ÇµÄÓŵã
¼ì²éËùÓÐÓï¾ä
½á¹¹¼òµ¥µÄ´úÂëµÄ²âÊÔЧ¹û½ÏºÃ
ÈÝÒ×ʵÏÖ×Ô¶¯²âÊÔ
´úÂ븲¸ÇÂʸß
Èç¹ûÊdzÌÐò¿é¸²¸Ç£¬Ôò²»Óÿ¼ÂdzÌÐò¿éÖеÄÔ´´úÂë
Óï¾ä¸²¸Ç²»Äܼì²é³öµÄ´íÎóÓÐ
Ìõ¼þÓï¾ä´íÎó¡¢Âß¼ÔËËã´íÎó¡¢Ñ»·Óï¾ä´íÎó

Åж¨¸²¸ÇÒªÇó£ºÂß¼ÅжÏÖÁÉÙÒ»´Î¡£Ã¿¸öÅж¨µÄÿ¸ö·ÖÖ§ÖÁÉÙÖ´ÐÐÒ»´Î¡£
ÒªÇóÉè¼Æ×ö¹»¶àµÄ²âÊÔÓÃÀý£¬Ê¹µÃ³ÌÐòÖеÄÿһ¸ö·ÖÖ§ÖÁÉÙͨ¹ýÒ»´Î
¼´Ã¿Ò»Ìõ·ÖÖ§Óï¾äµÄ¡°Õ桱ֵºÍ¡°¼Ù¡±Öµ¶¼ÖÁÉÙÖ´ÐÐÒ»´Î
whileÓï¾ä¡¢switchÓï¾ä¡¢Òì³£´¦Àí¡¢Ìø×ªÓï¾äºÍÈýÄ¿ÔËËã·û(a£¿b£ºc)µÈµÈͬÑù¿ÉÒÔʹÓ÷ÖÖ§¸²¸ÇÀ´²âÊÔ
¶Ô¶à·ÖÖ§Óï¾ä£¬ÈçCÓïÑÔÖеÄcaseÓï¾ä£¬·ÖÖ§¸²¸Ç±ØÐë¶Ôÿһ¸ö·ÖÖ§µÄÿһÖÖ¿ÉÄܵĽá¹û¶¼½øÐвâÊÔ
Åж¨¸²¸ÇÒª±ÈÓï¾ä¸²¸Ç²é´íÄÜÁ¦Ç¿Ò»Ð©£º
Ö´ÐÐÁË·ÖÖ§¸²¸Ç£¬Êµ¼ÊÒ²¾ÍÖ´ÐÐÁËÓï¾ä¸²¸Ç
Åж¨¸²¸ÇÓëÓï¾ä¸²¸Ç´æÔÚͬÑùµÄȱµã
²»Äܲé³öÌõ¼þÓï¾ä´íÎ󣬲»Äܲé³öÂß¼ÔËËã´íÎ󣬲»Äܲé³öÑ»·´ÎÊý´íÎ󣬲»Äܲé³öÑ»·Ìõ¼þ´íÎó

Ìõ¼þ¸²¸ÇÒªÇó£ºÃ¿¸öÅж¨µÄÿ¸öÌõ¼þӦȡµ½¸÷ÖÖ¿ÉÄܵÄÖµ¡£
²»½öÿһ¸öÓï¾äÖÁÉÙÖ´ÐÐÒ»´Î£¬Ê¹µÃÅж¨ÖеÄÿ¸öÌõ¼þ»ñµÃ¸÷ÖÖ¿ÉÄܽá¹û
Åж¨¸²¸ÇÖ»¹ØÐÄÕû¸öÅж¨±í´ïʽµÄ½á¹û£¬Ìõ¼þ¸²¸Ç¹ØÐĵÄÔòÊÇÿ¸öÌõ¼þ¸÷ÖÖȡֵµÄ½á¹û
Ìõ¼þ¸²¸ÇµÄÀû±×
Äܹ»¼ì²éËùÓеÄÌõ¼þ´íÎó
²»ÄÜʵÏÖ¶Ôÿ¸ö·ÖÖ§µÄ¼ì²é
ÓÃÀýÊýÔö¼Ó

Åж¨/Ìõ¼þ¸²¸ÇÒªÇó£ºÍ¬Ê±Âú×ãÅж¨¸²¸ÇÌõ¼þ¸²¸Ç¡£
Éè¼Æ×ã¹»¶àµÄ²âÊÔÓÃÀý£¬Ê¹µÃÅж¨ÖÐÿ¸öÌõ¼þµÄËùÓпÉÄÜȡֵÖÁÉÙÄܹ»»ñȡһ´Î£¬Í¬Ê±Ã¿¸öÅжϵÄËùÓпÉÄܵÄÅж¨½á¹ûÖÁÉÙÖ´ÐÐÒ»´Î
ÓÃÓÚ½â¾öÌõ¼þ¸²¸Ç²»Ò»¶¨°üÀ¨Åж¨¸²¸Ç£¬Åж¨¸²¸ÇÒ²²»Ò»¶¨°üÀ¨Ìõ¼þ¸²¸ÇµÄÎÊÌâ
·ÖÖ§-Ìõ¼þ¸²¸ÇµÄÀû±×£º
¼È¿¼ÂÇÁËÿһ¸öÌõ¼þ£¬ÓÖ¿¼ÂÇÁËÿһ¸ö·ÖÖ§£¬·¢ÏÖ´íÎóÄÜÁ¦Ç¿ÓÚ·ÖÖ§¸²¸ÇºÍÌõ¼þ¸²¸Ç
²¢²»ÄÜÈ«Ãæ¸²¸ÇËùÓз¾¶
ÓÃÀýÊýÁ¿µÄÔö¼Ó

Ìõ¼þ×éºÏ¸²¸ÇÒªÇó£ºÃ¿¸öÅж¨Öи÷Ìõ¼þµÄÿһÖÖ×éºÏÖÁÉÙ³öÏÖÒ»´Î¡£
ÒªÇóÉè¼Æ×ã¹»¶àµÄ²âÊÔÓÃÀý£¬Ê¹µÃÿ¸öÅж¨ÖÐÌõ¼þµÄ¸÷ÖÖ×éºÏÖÁÉÙ³öÏÖÒ»´Î
Âú×ãÌõ¼þ×éºÏ¸²¸Ç±ê×¼µÄ²âÊÔÓÃÀý£¬Ò²Ò»¶¨Âú×ãÅж¨¸²¸Ç¡¢Ìõ¼þ¸²¸ÇºÍÅж¨/Ìõ¼þ¸²¸Ç±ê×¼
Ìõ¼þ×éºÏ¸²¸ÇÊÇÇ°Ãæ¼¸ÖÖ¸²¸Ç±ê×¼ÖÐ×îÇ¿µÄ
µ«ÊÇ£¬Âú×ãÌõ¼þ×éºÏ¸²¸ÇÒªÇóµÄ²âÊÔÓÃÀý²¢²»Ò»¶¨ÄÜʹ³ÌÐòÖеÄÿÌõ·¾¶¶¼Ö´Ðе½

·¾¶¸²¸ÇÒªÇó£ºÊ¹³ÌÐòÖÐÿһÌõ¿ÉÄܵÄ·¾¶ÖÁÉÙÖ´ÐÐÒ»´Î¡£ ËùÓгöÈë¿Ú²âÊÔ¡£(È«¸²¸Ç)
¸²¸ÇÂÊ£ºÂß¼Ó빦Äܸ²¸Ç = ÖÁÉÙÒ»´Îitems/×ÜitemÊý¡£
³ÌÐòÁ÷³ÌͼµÄ¸÷¸ö·ûºÅ£º

³ÌÐòͼ
¶¨Ò壺¸ø¶¨Ò»¸ö²ÉÓÃÃüÁîʽ³ÌÐòÉè¼ÆÓïÑÔ±àдµÄ³ÌÐò£¬Æä³ÌÐòͼÊÇÒ»ÖÖÓÐÏòͼ£¬ÆäÖУº
´«Í³¶¨Ò壺
½ÚµãÊdzÌÐòÓï¾ä£¬±ß±íʾ¿ØÖÆÁ÷£¨´Ó½Úµãiµ½½ÚµãjÓÐÒ»Ìõ±ß£¬µ±ÇÒ½öµ±¶ÔÓ¦½ÚµãjµÄÓï¾ä¿ÉÒÔÁ¢¼´ÔÚ½Úµãi¶ÔÓ¦µÄÓï¾äÖ®ºóÖ´ÐУ©¡£
¸Ä½øºóµÄ¶¨Ò壺
½ÚµãҪôÊÇÕû¸öÓï¾ä£¬ÒªÃ´ÊÇÓï¾äµÄÒ»²¿·Ö£¬±ß±íʾ¿ØÖÆÁ÷£¨´Ó½Úµãiµ½½ÚµãjÓÐÒ»Ìõ±ß,µ±ÇÒ½öµ±¶ÔÓ¦½ÚµãjµÄÓï¾ä»òÓï¾äµÄÒ»²¿·Ö£¬¿ÉÒÔÁ¢¼´ÔÚ½Úµãi¶ÔÓ¦µÄÓï¾ä»òÓï¾äµÄÒ»²¿·ÖÖ®ºóÖ´ÐУ©
DD-·¾¶
½á¹¹ÐÔ²âÊÔ×îÖøÃûµÄÐÎʽÒÔ½Ð×ö¾ö²ßµ½¾ö²ß·¾¶(DD-·¾¶)µÄ½á¹¹Îª»ù´¡¡£
DD-·¾¶Ö¸Óï¾äµÄÒ»ÖÖÐòÁУ¬´Ó¾ö²ßÓï¾äµÄ¡°³ö·¡±¿ªÊ¼£¬µ½ÏÂÒ»¸ö¾ö²ßÓï¾äµÄ¡°Èë·¡±½áÊø£¬ÔÚÕâÖÖÐòÁÐÖÐûÓÐÄÚ²¿·ÖÖ§¡£
DD-·¾¶¶¨Òå
¶¨Ò壺¸ø¶¨²ÉÓÃÃüÁîʽÓïÑÔ±àдµÄÒ»¶Î³ÌÐò£¬ÆäDD-·¾¶Í¼ÊÇÓÐÏòͼ¡£ÆäÖУ¬Æä½Úµã±íʾÆä³ÌÐòͼµÄDD-·¾¶£¬±ß±íʾÁ¬ÐøDD-·¾¶Ö®¼äµÄ¿ØÖÆÁ÷¡£
ʵ¼ÊÉÏ£¬DD-·¾¶Í¼ÊÇÒ»ÖÖѹËõͼ£¬ÔÚÕâÖÖѹËõͼÖУ¬2-Á¬½Ó×é¼þ±»Ñ¹ËõDD-·¾¶µÄµ¥¸ö½Úµã¡£
Ìá³öDD-·¾¶µÄÄ¿µÄ£¬ÔÚÓÚDD-·¾¶Äܹ»·Ç³£¾«È·µØÃèÊö²âÊÔ¸²¸Ç¡£
½«ÉÏÒ»¸öÅжϵijö¿ÚÓëÏÂÒ»¸öÅжϵÄÈë¿ÚÖ®¼äµÄ³ÌÐòͼ½ÚµãѹËõ³ÉÒ»¸ö½Úµã¡£
 »·Ðθ´ÔÓ¶È(McCabe¶ÈÁ¿·¨)ÊÇÒ»ÖÖΪ³ÌÐòÂß¼¸´ÔÓÐÔÌṩ¶¨Á¿²â¶ÈµÄÈí¼þ¶ÈÁ¿£¬½«¸Ã¶ÈÁ¿ÓÃÓÚ¼ÆËã³ÌÐòµÄ»ù±¾µÄ¶ÀÁ¢Â·¾¶ÊýÄ¿£¬ÎªÈ·±£ËùÓÐÓï¾äÖÁÉÙÖ´ÐÐÒ»´ÎµÄ²â¶ÈÊýÁ¿µÄÉϽ硣
»·Ðθ´ÔÓ¶ÈÈ¡¾öÓÚ³ÌÐò¿ØÖÆÁ÷µÄ¸´Ôӳ̶ȣ¬Ò²¼´ÊÇÈ¡¾öÓÚ³ÌÐò½á¹¹µÄ¸´Ôӳ̶ȡ£ËüÊǶԲâÊÔÄѶȵÄÒ»ÖÖ¶¨Á¿¶ÈÁ¿£¬Ò²ÄܶÔÈí¼þ×îÖյĿɿ¿ÐÔ¸ø³öijÖÖÔ¤²â¡£
¼ÆËã·½·¨£º
1¡¢Á÷ͼGµÄ»·Ðθ´ÔÓ¶ÈV(G)=ÇøÓòÊý
2¡¢Á÷ͼGµÄ»·Ðθ´ÔÓ¶ÈV(G)=E-N+2£¬ÆäÖУ¬EÊÇÁ÷ͼÖбߵÄÌõÊý£¬NÊǽáµãÊý¡£
3¡¢Á÷ͼGµÄ»·Ðθ´ÔÓ¶ÈV(G)=P+1£¬ÆäÖУ¬PÊÇÁ÷ͼÖÐÅж¨·ÖÖ§µãµÄÊýÄ¿¡£
4¡¢ Á÷ͼGµÄ»·Ðθ´ÔÓ¶ÈV(G)=m-n+p¡£ (mΪ»¡¡¢nΪ½ÚµãÊý¡¢pΪǿÁ¬Í¨·ÖÁ¿(³ö¶ÈΪ0µÄ½ÚµãÊý¼Ó1))
ÓÐÏòͼGÖУ¬Èç¹ûÁ½¸ö¶¥µãvi,vj¼ä£¨vi>vj£©ÓÐÒ»Ìõ´Óviµ½vjµÄÓÐÏò·¾¶£¬Í¬Ê±»¹ÓÐÒ»Ìõ´Óvjµ½viµÄÓÐÏò·¾¶£¬Ôò³ÆÁ½¸ö¶¥µãÇ¿Á¬Í¨¡£ÓÐÏòͼµÄ¼«´óÇ¿Á¬Í¨×Óͼ£¬³ÆÎªÇ¿Á¬Í¨·ÖÁ¿(strongly
connected components)¡£
·¶Àý£º

|