Karp 21个规约问题 笔记 （1~13个规约问题）
0? 證明格式
0.1 證明一個問題屬于NP
0.2 多項式時間內將一個問題歸約到另一個?
0.3 證明一個問題是NP完全的
0.4 要證明的規約
?1 SAT —> 0-1 整數規范
1.1 問題描述
?1.2 規約
?1.3 等價性證明
?2 SAT->CLIQUE
2.1 SAT->3SAT->independent set->clique
MAS 714 筆記20：規約和SAT_UQI-LIUWJ的博客-CSDN博客
MAS 714筆記： NP完全問題_UQI-LIUWJ的博客-CSDN博客
2.2 規約過程
?想象成3SAT->independent set 構造的圖的補圖
2.3 證明等價性
?3 clique -> Set packing
?3.1 clique->independent set->set packing
MAS 714 筆記20：規約和SAT_UQI-LIUWJ的博客-CSDN博客
MAS 714筆記： NP完全問題_UQI-LIUWJ的博客-CSDN博客
????????每個集合對應一個點。如果兩個集合有交集，那么這兩個集合對應的點在圖上有連邊。找k個independent set等價于k個互不相交的集合
3.2 規約
3.3 等價性證明?
?4 Clique ->vertex cover（node cover）
4.1 clique->independent set->vertex cover
MAS 714 筆記20：規約和SAT_UQI-LIUWJ的博客-CSDN博客
MAS 714筆記： NP完全問題_UQI-LIUWJ的博客-CSDN博客
4.2 規約過程
這里一步到位，clique->independent set是圖變成補圖，點不變；independent set 到 node cover是點變成補的點，圖不變
4.3 證明等價性
5 node cover->set cover
MAS 714筆記： NP完全問題_UQI-LIUWJ的博客-CSDN博客?4.3
6 node cover ->feedback node? set
6.1 問題描述
?6.2 規約過程
?將一條無向邊轉化成兩個方向的有向邊
6.3 等價性證明
?7 node cover->feedback? arc set
7.1 問題描述
7.2 規約過程
大致思路和6差不多，唯一不同的是，6中要求的是，我沒構造出來的一個有向環，對應的是一個點。而這里要求的是對應一條有向邊，那么怎么對應呢？我們就構建一個如下的內容：
?
?7.3 證明等價性
?8 node-cover—>directed Hamilton circuit
這個比較繁瑣，略過，可以用3SAT->independent set->node-cover->->Hamiliton
MAS 714筆記： NP完全問題_UQI-LIUWJ的博客-CSDN博客
MAS 714總復習_UQI-LIUWJ的博客-CSDN博客
?
?
?9 有向哈密頓圖-> 無向哈密頓圖
9.1 規約方法
?
?9.2 等價性證明
?
?10 SAT->3SAT
MAS 714 筆記20：規約和SAT_UQI-LIUWJ的博客-CSDN博客
11 3SAT->Chromatic number
11.1 問題描述
后者即k-染色問題，相鄰的兩個點不能染同一種顏色。
’
11.2 規約過程
?以為例：
?
?11.3 等價性證明
11.3.1 3SAT->
?11.3.2 ->3SAT
?12 chromatic number -> clique cover
12.1 問題描述
12.2 規約問題?
?12.3 證明等價性
?13 chromatic number -> exact cover
13.1 問題描述
?13.2 問題規約
?13.3 證明等價性
13.3.1 ->
?13.3.2 <-
?
后續的可見
?0Reducibility among Combinatorial Problems問題之間的規約證明 - 百度文庫 (baidu.com)
《新程序員》：云原生和全面數字化實踐50位技術專家共同創作，文字、視頻、音頻交互閱讀總結
以上是生活随笔為你收集整理的Karp 21个规约问题 笔记 （1~13个规约问题）的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 摘抄 :methodology 怎么写
- 下一篇： NTU课程笔记 mas714复习：例题