最后的证明:8.15
题目:
最大公共子图
证明如下问题是NP-完全的:
输入:两个图G1=(V,E) 和G2=(V,E) ;预算b。
输出:两个节点集合V′1⊆V1 和V′2⊆V2 ,他们被移除后,将在两图张分别留下至少b个节点,且图的剩余部分完全一样。
证明:
可以将最大独立集问题归约到此问题。
比如若要求任意图
题目:
最大公共子图
证明如下问题是NP-完全的:
输入:两个图G1=(V,E) 和G2=(V,E) ;预算b。
输出:两个节点集合V′1⊆V1 和V′2⊆V2 ,他们被移除后,将在两图张分别留下至少b个节点,且图的剩余部分完全一样。
证明:
可以将最大独立集问题归约到此问题。
比如若要求任意图