### 鍥捐��鐨勬�傝堪涓庡簲鐢�
#### 涓�銆佸紩瑷�
鍥捐��锛圙raph Covering锛夋槸鍥捐�轰腑鐨勪竴涓�閲嶈�佹�傚康锛屽箍娉涘簲鐢ㄤ簬璁＄畻鏈虹�戝�︺�佺綉缁滃垎鏋愩�佺粍鍚堜紭鍖栫瓑澶氫釜棰嗗煙銆傚浘琚�鐮旂┒鐨勬槸濡備綍鐢ㄦ煇绉嶈�勫垯瑕嗙洊鍥剧殑鑺傜偣鎴栬竟锛屼互杈惧埌鐗瑰畾鐨勭洰鐨勩�傞殢鐫�澶ф暟鎹�鏃朵唬鐨勫埌鏉ワ紝鍥捐��鐨勭爺绌跺拰搴旂敤瓒婃潵瓒婂彈鍒伴噸瑙嗭紝涔熷紩鍙戜簡浼楀�氬�﹁�呯殑鍏虫敞銆�
#### 浜屻�佸浘琚�鐨勫畾涔�
鍦ㄥ浘璁轰腑锛屽浘 G = (V, E) 鐢变竴涓�椤剁偣闆� V 鍜屼竴涓�杈归泦 E 缁勬垚銆傚浘琚�闂�棰樼殑鏍稿績鏄�鐢ㄤ竴涓�瀛愰泦 C锛堢О涓衡�滆��鈥濓級鏉ヨ�嗙洊鍥句腑鐨勫厓绱犮�傝��鐨勭被鍨嬪彲浠ュ垎涓鸿妭鐐硅��鍜岃竟琚�锛�
1. **鑺傜偣琚�**锛氫竴涓�鑺傜偣琚�绉颁负琚�瑕嗙洊鐨勮妭鐐癸紝濡傛灉璇ヨ妭鐐硅��鏌愪釜琚�鍖呭惈銆傝妭鐐硅��鐨勪竴涓�缁忓吀渚嬪瓙鏄�椤剁偣瑕嗙洊锛圴ertex Cover锛夛紝鍗冲湪涓�涓�鍥句腑锛岄�夋嫨鏈�灏忕殑椤剁偣闆嗗悎锛屼娇寰楁瘡鏉¤竟鑷冲皯鏈変竴涓�绔�鐐瑰湪杩欎釜闆嗗悎涓�銆�
2. **杈硅��**锛氳竟琚�鏄�鎸囬�夋嫨涓�涓�杈圭殑瀛愰泦锛屼娇寰楀浘涓�鐨勬煇浜涙�ц川琚�婊¤冻銆傛瘮濡傦紝杈硅�嗙洊锛圗dge Cover锛夋槸閫夋嫨鏈�灏忕殑杈归泦鍚堬紝浣垮緱姣忎釜椤剁偣閮戒笌鑷冲皯涓�鏉¤竟鐩歌繛銆�
#### 涓夈�佸浘琚�鐨勫垎绫�
鍥捐��鍙�浠ユ牴鎹�鍏舵�ц川鍜屽簲鐢ㄥ垎涓哄嚑绫伙細
1. **鏈�灏忚��闂�棰�**锛氬�绘壘鏈�灏忕殑鑺傜偣鎴栬竟琚�銆傝繖绫婚棶棰橀�氬父鏄� NP-闅剧殑锛屼絾鏈夊緢澶氱殑鍚�鍙戝紡绠楁硶鍜岃繎浼肩畻娉曞彲浠ヤ娇鐢ㄣ��
2. **绾︽潫琚�闂�棰�**锛氬湪瑕嗙洊鐨勫悓鏃舵弧瓒充竴浜涚壒瀹氱殑绾︽潫鏉′欢銆備緥濡傦紝鍦ㄧぞ浜ょ綉缁滀腑锛屽彲鑳介渶瑕佹弧瓒虫煇浜涚敤鎴蜂箣闂寸殑鍏崇郴鎴栦簰鍔ㄣ��
3. **闅忔満琚�闂�棰�**锛氬湪涓�浜涙儏鍐典笅锛屽浘琚�闂�棰樺彲鑳芥秹鍙婇殢鏈烘�э紝姣斿�傚湪缃戠粶涓�寮曞叆闅忔満閫夋嫨鑺傜偣杩涜�岃�嗙洊锛屼互渚挎彁楂樺叾椴佹�掓�с��
4. **鍔ㄦ�佽��闂�棰�**锛氶殢鐫�鏃堕棿鐨勬帹绉伙紝鍥剧殑缁撴瀯鍙�鑳戒細鍙戠敓鍙樺寲锛屾�ゆ椂闇�瑕佸姩鎬佸湴鏇存柊琚�鐨勯�夋嫨銆傝繖鍦ㄨ�稿�氱綉缁滃簲鐢ㄤ腑闈炲父閲嶈�侊紝濡備紶鎰熷櫒缃戠粶鍜屼氦閫氬浘銆�
#### 鍥涖�佸浘琚�鐨勭畻娉�
瑙ｅ喅鍥捐��闂�棰樼殑鏂规硶澶氱�嶅�氭牱锛屾兜鐩栦簡绮剧‘绠楁硶銆佽繎浼肩畻娉曞拰鍚�鍙戝紡绠楁硶绛夈�備互涓嬫槸鍑犵�嶅父瑙佺殑绠楁硶锛�
1. **璐�蹇冪畻娉�**锛氳椽蹇冪畻娉曟槸涓�绉嶅父鐢ㄧ殑鏂规硶锛岄�氳繃鍦ㄦ瘡涓�姝ラ�夋嫨瀵瑰綋鍓嶉棶棰樻渶浼樼殑瑙ｅ喅鏂规�堬紝鏉ラ�愭�ユ瀯寤烘暣涓�琚�闆嗗悎銆傚�傚湪姹傝В椤剁偣瑕嗙洊鏃讹紝閫夋嫨搴︽渶澶х殑椤剁偣锛岀洿鍒版墍鏈夎竟閮借��瑕嗙洊銆�
2. **鍔ㄦ�佽�勫垝**锛氬湪鏌愪簺鐗瑰畾绫诲瀷鐨勫浘涓婏紙濡傛爲褰㈢粨鏋勶級锛屽彲浠ヤ娇鐢ㄥ姩鎬佽�勫垝鐨勬柟娉曟潵瑙ｅ喅鍥捐��闂�棰樸�傞�氳繃鍒嗚В闂�棰樹负瀛愰棶棰橈紝閫愭�ユ眰瑙ｏ紝浠庤�屽緱鍒版渶缁堣В銆�
3. **鏁存暟绾挎�ц�勫垝锛圛LP锛�**锛氬�逛簬涓�浜涘�嶆潅鐨勮��闂�棰橈紝鍙�浠ュ皢鍏跺缓妯′负鏁存暟绾挎�ц�勫垝闂�棰橈紝鍒╃敤鐜版湁鐨勭嚎鎬ц�勫垝姹傝В宸ュ叿鏉ュ�绘壘鏈�浼樿В銆�
4. **闅忔満鍖栫畻娉�**锛氬湪鏌愪簺鎯呭喌涓嬶紝浣跨敤闅忔満鍖栫瓥鐣ュ彲浠ュ緱鍒版帴杩戞渶浼樼殑瑙ｏ紝灏ゅ叾鏄�鍦ㄥ�勭悊澶ц�勬ā鏁版嵁鏃讹紝鍙�浠ユ樉钁楁彁楂樿�＄畻鏁堢巼銆�
#### 浜斻�佸浘琚�鐨勫簲鐢�
鍥捐��鍦ㄧ幇瀹炵敓娲讳腑鏈夊箍娉涚殑搴旂敤锛岀壒鍒�鏄�鍦ㄤ互涓嬪嚑涓�鏂归潰锛�
1. **缃戠粶璁捐��**锛氬湪璁＄畻鏈虹綉缁滃拰閫氫俊缃戠粶涓�锛屽浘琚�鍙�浠ョ敤鏉ヤ紭鍖栬妭鐐瑰拰杈圭殑閰嶇疆锛屼互鎻愰珮缃戠粶鐨勮�嗙洊鐜囧拰鍐椾綑鎬с��
2. **绀句氦缃戠粶鍒嗘瀽**锛氬湪绀句氦缃戠粶涓�锛屽浘琚�鍙�浠ュ府鍔╄瘑鍒�鍏抽敭鐢ㄦ埛鎴栫兢浣擄紝浠庤�屼究浜庝俊鎭�浼犳挱鎴栫ぞ鍖哄彂鐜般��
3. **鐢熺墿淇℃伅瀛�**锛氬湪鍩哄洜缃戠粶鍒嗘瀽涓�锛屽浘琚�鍙�浠ョ敤浜庤瘑鍒�瀵规煇涓�鐢熺墿杩囩▼杩涜�岃皟鎺х殑鍏抽敭鍩哄洜銆�
4. **浜ら�氱綉缁滀紭鍖�**锛氶�氳繃鍥捐��鐞嗚�猴紝鍙�浠ヤ紭鍖栦氦閫氱嚎璺�鐨勮�剧疆锛屾彁楂樿繍杈撴晥鐜囷紝鍑忓皯鎷ュ牭銆�
5. **鏁版嵁闅愮�佷繚鎶�**锛氬湪鏁版嵁鍏变韩鍜岄殣绉佷繚鎶や笂锛屽浘琚�鍙�浠ョ敤浜庤�捐�℃暟鎹�鍏变韩绛栫暐锛岀‘淇濇晱鎰熸暟鎹�寰楀埌閫傚綋鐨勪繚鎶ゃ��
#### 鍏�銆佺粨璁�
鍥捐��浣滀负鍥捐�轰腑鐨勯噸瑕佺爺绌堕�嗗煙锛屽凡缁忓湪澶氫釜瀛︾�戜腑鎵惧埌浜嗗簲鐢ㄣ�傝櫧鐒惰�稿�氬浘琚�闂�棰樻槸 NP-闅剧殑锛屼絾鍊熷姪鐜颁唬璁＄畻鎶�鏈�鍜岀畻娉曡�捐�＄殑杩涙�ワ紝鎴戜滑宸茬粡鑳藉�熻В鍐冲叾鍦ㄥ疄闄呭簲鐢ㄤ腑鐨勪竴浜涘叧閿�闂�棰樸�傞殢鐫�鎶�鏈�鐨勪笉鏂�鍙戝睍锛屾湭鏉ョ殑鍥捐��鐮旂┒灏嗘洿鍔犳繁鍏ワ紝搴旂敤灏嗘洿鍔犲箍娉涳紝鍊煎緱鎴戜滑鎸佺画鍏虫敞鍜屾帰绱�銆�
鍦ㄦ暟鎹�绉戝�﹀拰鏈哄櫒瀛︿範绛夐�嗗煙锛屽浘琚�鐞嗚�轰篃灏嗙户缁�鎻愪緵鏂扮殑瑙嗚�掑拰鏂规硶锛屽府鍔╂垜浠�鏇村ソ鍦扮悊瑙ｅ�嶆潅绯荤粺鐨勭粨鏋勫拰鍔ㄦ�併�傚挨鍏舵槸鍦ㄩ渶瑕佸�勭悊娴烽噺鏁版嵁鐨勪粖澶╋紝瀹屽杽鐨勫浘琚�鐞嗚�轰笌绠楁硶灏嗕负鎴戜滑甯︽潵鏇撮珮鏁堝拰鏅鸿兘鐨勮В鍐虫柟妗堛��
---
閫氳繃瀵瑰浘琚�鐨勬帰璁�锛屾垜浠�涓嶄粎浜嗚В浜嗗叾鍩烘湰姒傚康鍜屽簲鐢�锛岃繕璁よ瘑鍒颁簡杩欎竴棰嗗煙鏈�鏉ョ殑骞挎硾娼滃姏鍜屽彂灞曡秼鍔裤�傚笇鏈涜兘婵�鍙戞洿澶氬�﹁�呭拰鐮旂┒鑰呭�硅繖涓�鐮旂┒鏂瑰悜鐨勫叧娉ㄥ拰娣卞叆鎺㈢储銆�