µÚ¾ÅÕ ͼÓëÍøÂç·ÖÎö ÏÂÔر¾ÎÄ

±¥ºÍ»¡¡ª¡ªÈç¹ûÈÝÁ¿ÍøÂçDÖÐij»¡(vi,vj)ÉϵÄÁ÷Á¿fijµÈÓÚÆäÈÝÁ¿ÏÞÖÆcij£¬¼´fij?cij£¬Ôò³Æ(vi,vj)ΪDµÄ±¥ºÍ»¡¡£

Ç°Ïò»¡¡¢ºóÏò»¡¡ª¡ª¼ÙÉèQΪÈÝÁ¿ÍøÂçDÖдÓvSµ½vTµÄÁ´£¬²¢Çҹ涨vSºÍ

vTΪÁ´µÄ·½Ïò£¬Á´ÉÏÓëÁ´µÄ·½ÏòÒ»ÖµĻ¡³ÆΪǰÏò»¡£¬ÓëÁ´µÄ·½ÏòÏà·´µÄ»¡³Æ

ΪºóÏò»¡¡£Ç°Ïò»¡¼¯ºÏÓÃQ?±íʾ£¬ºóÏò»¡¼¯ºÏÓÃQ?±íʾ¡£

¿ÉÔö¹ãÁ´¡ª¡ª¼ÙÉèfÊÇÈÝÁ¿ÍøÂçDµÄÒ»¸ö¿ÉÐÐÁ÷£¬Èç¹ûÂú×ã

??0?fij?cij???0?fij?cij(vi,vj)?Q?

(vi,vj)?Q?Ôò³ÆQΪ´ÓvSµ½vTµÄ£¨¹ØÓÚfµÄ£©¿ÉÔö¹ãÁ´¡£

¸î¼¯¡ª¡ªÈÝÁ¿ÍøÂçD?(V,E,C),vSºÍvTΪԴºÍ»ã£¬Èô´æÔÚ»¡¼¯E'?E£¬½«ÍøÂçD·ÖΪÁ½¸ö×ÓͼD1ºÍD2£¬Æ䶥µã¼¯ºÏ·Ö±ðΪSºÍS£¬S?S?V£¬

S?S??£¬vSºÍvTΪ±ðÊôÓÚSºÍS£¬Ôò³Æ»¡¼¯

E'?(S,S)?{(u,v)|u ?S,v?S }

ΪDµÄÒ»¸ö¸î¼¯¡£

¸î¼¯ÈÝÁ¿¡ª¡ªE'?(S,S)ΪÈÝÁ¿ÍøÂçD?(V,E,C)µÄÒ»¸î¼¯£¬³ÆE'ÖÐËùÓл¡µÄÈÝÁ¿Ö®ºÍ

C(S,S)?ΪE'µÄ¸î¼¯ÈÝÁ¿¡£

e?E'?c(e)

×îС¸î¼¯¡ª¡ªÈÝÁ¿ÍøÂçDÒ»°ãÓжà¸ö¸î¼¯£¬ÆäÖиÈÝÁ¿×îСµÄ¸î¼¯³ÆΪ

DµÄ×îС¸î¼¯£¬Æä¸î¼¯ÈÝÁ¿³ÆΪDµÄ×îС¸î¼¯ÈÝÁ¿¡£

(2) ×î´óÁ÷×îС¸î¶¨Àí

¶¨Àí9-1 ÉèfΪÍøÂçD?(V,E,C)µÄÈÎÒ»¿ÉÐÐÁ÷£¬Á÷Á¿ÎªW£¬(S,S)Ϊ·ÖÀëvSµ½vTµÄÒ»¸ö¸î¼¯£¬ÔòÓÐW?C(S,S)¡£

¶¨Àí9-2 £¨×î´óÁ÷¡ª×îС¸î¼¯¶¨Àí£©ÈÎÒâÒ»¸öÈÝÁ¿ÍøÂçD?(V,E,C)ÖУ¬´Ó

5

Ô´vSµ½»ãvTµÄ×î´óÁ÷µÄÁ÷Á¿µÈÓÚ·ÖÀëvS¡¢vTµÄ×îС¸î¼¯ÈÝÁ¿¡£

ÍÆÂÛ ¿ÉÐÐÁ÷fÊÇ×î´óÁ÷µÄ³äÒªÌõ¼þÊDz»´æÔÚ´ÓvSµ½vT¹ØÓÚfµÄ¿ÉÔö¹ãÁ´¡£ 4¡¢×îС·ÑÓÃ×î´óÁ÷ÎÊÌâ

Ñо¿ÍøÂçÖеÄÁ÷ʱ£¬ÐèҪעÒâÁ÷µÄ¿ÉÐÐÐÔ¡¢¸ßЧÐԺ;­¼ÃÐÔ¡£Êµ¼ÊÍøÂçÖеÄÁ÷±ØÐëÊÇ¿ÉÐÐÁ÷£¬ÆäÁ÷Á¿²»Äܳ¬¹ý×î´óÁ÷µÄÁ÷Á¿¡£ÍøÂçÒÔ×îС·ÑÓÃͨ¹ýijһ¿ÉÐÐÁ÷µÄÎÊÌâ¾ÍÊÇ×îС·ÑÓÃÁ÷ÎÊÌ⣬µ±ÍøÂçÖеÄÁ÷Á¿´ïµ½×î´óʱ£¬¾ÍÊÇ×îС·ÑÓÃ×î´óÁ÷ÎÊÌâ¡£

¸³È¨ÈÝÁ¿ÍøÂ硪¡ªÖ¸ÔÚÈÝÁ¿ÍøÂçD?(V,E,C)ÖУ¬DµÄÿÌõ»¡(vi,vj)ÉϳýÁ˸ø³ö×î´óÁ÷ÈÝÁ¿cijÍ⣬»¹¸ø³öÁ˵¥Î»Á÷Á¿µÄ³É±¾dij(?0)¡£¸³È¨ÈÝÁ¿ÍøÂç¼ÇΪ

D?(V,E,C,d)¡£

×îС·ÑÓÃÁ÷ÎÊÌ⡪¡ªÖ¸Çó¸³È¨ÈÝÁ¿ÍøÂçDµÄÒ»¸ö¿ÉÐÐÁ÷f?{fij}£¬Ê¹µÃÁ÷Á¿

W(f)?w*£¬ÇÒ×Ü·ÑÓÃd(f)?(vi,vj)?E?dijijf´ïµ½×îС¡£

×îС·ÑÓÃ×î´óÁ÷ÎÊÌ⡪¡ªÖ¸fΪ×î´óÁ÷ʱµÄ×îС·ÑÓÃÁ÷ÎÊÌâ¡£

µ±D?(V,E,C,d)ÊÇÒ»¸ö¸³È¨ÈÝÁ¿ÍøÂ磬fÊÇDÉϵÄÒ»¸ö¿ÉÐÐÁ÷£¬QÊÇ´ÓÔ´

vSµ½»ãvTµÄÒ»Ìõ¹ØÓÚfµÄ¿ÉÔö¹ãÁ´£¬»¹ÓÐÏÂÁÐÖØÒª¸ÅÄ

Á´µÄ·ÑÓ᪡ª³Æ?dijfij??dijfijΪQµÄ·ÑÓ㬼ÇΪd(Q)£¬ÆäÖÐQ?ΪQµÄ

Q?Q?Ç°Ïò»¡¼¯ºÏ£¬Q?ΪQµÄºóÏò»¡¼¯ºÏ¡£

×îС·ÑÓÿÉÔö¹ãÁ´¡ª¡ªÈôQ*ÊÇ´ÓÔ´vSµ½»ãvTËùÓпÉÔö¹ãÁ´ÖзÑÓÃ×îСµÄÁ´£¬Ôò³ÆQ*Ϊ×îС·ÑÓÿÉÔö¹ãÁ´¡£

QÊǹØÓÚfµÄ´ÓÔ´vSµ½»ãvT¶¨Àí9-3 ÈôfÊÇÁ÷Á¿ÎªW(f)ϵÄ×îС·ÑÓÃÁ÷£¬

µÄÒ»Ìõ×îС·ÑÓÿÉÔö¹ãÁ´£¬Ôòf¾­¹ýQµ÷ÕûÁ÷Á¿?ºóµÃµ½µÄпÉÐÐÁ÷f?Ò»¶¨ÊÇÁ÷Á¿ÎªW(f)??ϵÄ×îС·ÑÓÃÁ÷¡£

6

¡ì9.2 Ö÷Òª½âÌâ·½·¨ºÍµäÐÍÀýÌâ·ÖÎö

ÌâÐÍI ÇóÁ¬Í¨Í¼µÄ×îС֧³ÅÊ÷

1¡¢Kruskal·¨

KruskalËã·¨µÄ»ù±¾Ë¼ÏëÊÇÏȽ«ÍøÂçÖеıßÈ«²¿È¥³ý£¬È»ºóÖð²½ÌôÑ¡±¸Ñ¡±ßÖÐȨ×îСµÄ±ß¹¹³É×îС֧³ÅÊ÷£¬²¢ÇÒÈ·±£ÓëÒѾ­Ñ¡ºÃµÄ±ß²»²úÉú»Ø·¡£KruskalËã·¨Ò²³ÆΪ¼Ó±ßËã·¨»ò±ÜȦ·¨¡£

KruskalËã·¨²½ÖèÈçÏ£º

µÚ1²½£º½«Í¼GµÄmÌõ±ß°´È¨µÄµÝÔö˳ÐòÅÅÁУº

w(ei1)?w(ei2)???w(eim)

µÚ2²½£ºÁîl(vj)?j,j?1,2,?,n£¬E1??£¬Ñ­»·±äÁ¿¸³Öµk?1£» µÚ3²½£ºÉèeik?[u,v]£¬Èôl(u)?l(v)£¬×ªµÚ6²½£¬·ñÔòÁîE1?E1?{eik}£» µÚ4²½£º¶ÔÂú×ãl(vj)?max{l(u),l(v)}µÄvj£¬Áîl(vj)?min{l(u),l(v)}£» µÚ5²½£ºÈôE1ÖеıߵÄÌõÊý|E1|?n?1£¬Ëã·¨ÖÕÖ¹£¬·ñÔò¼ÌÐøµÚ6²½£» µÚ6²½£ºÈô|E1|?m?n?1£¬ÖÕÖ¹£¬Í¼GΪ·ÇÁ¬Í¨Í¼£¬ÎÞÖ§³ÅÊ÷£¬·ñÔò£¬Áî

k?k?1£¬×ªµÚ3²½¡£

Àý9-1 ÓÃKruskalËã·¨¹¹Ôìͼ9-1µÄ×îС֧³ÅÊ÷¡£

v8v1513 134181v5v11 12 10 14138 1432vvv717v6

ͼ9-1

½â£º¸ù¾ÝKruskalËã·¨£¬²»¶ÏÑ¡ÔñȨ×îСµÄ±ß£¬Í¬Ê±ÐÂÔö±ß±ØÐëÓëÒÑÑ¡±ß²»¹¹³É»Ø·£¬ËùÑ¡±ß˳Ðò£º[v2,v7]£¬[v3,v4]£¬[v7,v8]£¬[v1,v2]£¬[v2,v3]£¬£¬[v5,v6]¡£¾ßÌå²½Öè¼ûͼ9-2(a)~(g)¡£

7

v8v1513 134181v5vv8v1513 134181v5v11 12 10 14138 143211 12 10 14138 1432vvvvv7v8v17v6v5vv7v8v17v6 v5v(a) (b)

1513 13418111 12 10 14138 14321513 13418111 12 10 14138 1432vvvvv717v6v717v6

(c) (d)

v8v1513 134181v5vv8v1513 134181v5v11 12 10 14138 143211 12 10 14138 1432vvvvv717v6v8v17

(e) (f)

1513 13418111 12 10 14138 1432v5vvvv717v6

(g)

ͼ9-2

2¡¢PrimËã·¨

PrimËã·¨ÀàËÆÓÚKruskalËã·¨£¬²»Í¬µÄÊÇÿ´Î¼ÓÉϵı߱ØÐëÓëÇ°ÃæÒѾ­¼ÓÉϵıßÁ¬Í¨¡£

¶ÔÓÚ¸³È¨Á¬Í¨Í¼G?(V,E,w)£¬ÇóGµÄ×îСÉú³ÉÊ÷µÄPrimËã·¨²½ÖèÈçÏ£º

8