[演算](2008/06/18修正)vertex cover & independent set
說明問題
vertex cover problem
給定一個G(V,E)和整數k
是否存在一個G上點的子集合S,對G的每個edge至少會有一點屬於S,使S的點數<=k?
independent set problem
給定一個G(V,E)和整數k
是否存在一個G上點的子集合S,對G的每個edge至多會有一點屬於S,使S的點數<=k?
"vertex cover" can be reduced to "max independent set".
1.轉換的演算法
給vertex cover的input為G(V,E)和整數k
則給independent set的input為G(V,E)和整數V-k
若independent set output是yes則vertex cover的 output為yes
反之亦然
2.轉換的演算法在多項式時間之內
input轉換演算法只需要O(1)
output轉換演算法只需要O(1)
3.轉換的方法是對的
令S是任何的independent set
則對G的每個edge(u,v)而言,最多會有一點屬於S,
所以對G的每個edge(u,v)而言,最少會有一點屬於V-S
所以V-S是vertex cover
"independent set" can be reduced to "vertex cover".
1.轉換的演算法
給independent set的input為G(V,E)和整數k
則給vertex cover的input為G(V,E)和整數V-k
若vertex cover output是yes則independent set的 output為yes
反之亦然
2.轉換的演算法在多項式時間之內
input轉換演算法只需要O(1)
output轉換演算法只需要O(1)
3.轉換的方法是對的
令S是任何的vertex cover
則對G的每個edge(u,v)而言,最少會有一點屬於S
所以對G的每個edge(u,v)而言,最多會有一點屬於V-S,
所以V-S是independent set
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.7.59
※ 編輯: ajnightmare 來自: 140.112.7.59 (05/24 14:56)
※ 編輯: ajnightmare 來自: 58.114.208.7 (06/18 22:26)