資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學證明從團問題到頂點覆蓋問題的多項式時間歸約。
頂點覆蓋是指覆蓋圖中所有邊的頂點子集。它用於確定給定圖是否具有3SAT到頂點覆蓋的歸約。
團是指所有頂點都直接連線的頂點子集。它用於確定圖中是否存在大小為k的團。
要證明——頂點覆蓋可以歸約為團問題。
證明
給定一個圖G=(V,E)和整數k。
獲取其補圖G'=(V,E')。
求解CLIQUE(G',|V|-k)。
如果存在解，則返回yes；否則，返回no。
為了證明這種歸約，我們需要證明以下幾點：
如果VERTEX-COVER(G,k)存在解，則CLIQUE(G',|V|-k)必須存在解，反之亦然。
假設G有一個頂點覆蓋V' ⊆ V，其中|V|' = k。那麼，對於所有u, v ε V，如果(u, v) ε E，則u ε V'或v ε V'或兩者兼有，因為頂點覆蓋必須覆蓋所有邊。
逆否命題是：對於所有u, v ε V，如果u不屬於V'，則(u, v) ε/ E，因此(u, v) ε E。
對於任何一對都不在G的頂點覆蓋V'中的頂點，它們之間在G中有一條邊。
所有都不在V'中的頂點對的並集只是V − V'。因此，根據定義，V − V'是G中的一個團，並且V − V'的大小為|V| − k。
此操作可以在多項式時間內完成。由於VERTEX-COVER可以在多項式時間內歸約到CLIQUE，CLIQUE ε NP並且VERTEX-COVER是NP完全的，因此CLIQUE也是NP完全的。
更新於：2021年6月15日
2K+ 瀏覽量
廣告