SA17011125+吴燕晶+近似算法1
需积分: 0 115 浏览量
2022-08-08
22:46:43
上传
评论
收藏 13KB DOCX 举报
近似算法
Ex1. G 中最大团的 size 为 a 当且仅当 G
m
里最大团的 size 是 ma
证明：首先我们来证明充分性：G 中的最大团的 size 是 a，那么根据最大团的定义，我
们设最大团为 G’，G 中的边集合为 E，那么对于任意的顶点 u 属于 G-G’，必须顶点 v 属于
G’，使得边 uv 不属于 E。G
m
是 G 的 m 次拷贝，并且不同副本之间的任意两个顶点相连，所
以每个副本的 a 个最大团的顶点是相连的，就能形成 size 是 ma 的团。所以 G
m
最大团的 size
至少是 ma。有可能大于 ma 么？不失一般性，我们考虑 ma+1。要使得 G
m
的最大团是
ma+1，那么根据容斥原理，至少有一个图中有团 a+1，这与条件矛盾。其他情况类似，G
m
的最大团不会超过 ma。所以 G
m
的最大团的 size 是 ma。
现在来证明必要性：G
m
里的最大团的 size 是 ma。那么这 ma 个顶点必定是由 m 个 G
副本中的最大团的顶点组成，所以 G 的最大团的 size 为 ma/m=a。为什么这 ma 个顶点一定
是由 m 个副本中的最大团的顶点组成，我们从两个方面进行考虑。对于任意一个顶点，如
果它属于 G
m
的最大团但是不属于 G 的最大团，那么根据 G
m
和团的定义该顶点一定属于它
所在的 G 副本的最大团的顶点集，与假设矛盾。因此 G
m
的最大团中的顶点一定是由 m 个 G
副本中的最大团的顶点组成的。此外，对于任意的一个顶点，假设它属于 G 的最大团但是
不属于 G
m
，那么根据 G
m
的定义，该顶点与 G
m
里最大团的所有顶点都是相连的，就可以把
该顶点加进去，此时 G
m
的最大团的 size 变成了 ma+1，与条件矛盾。所以 G
m
的最大团的 ma
个顶点是由 m 个 G 副本中的最大团的顶点组成，所以 G 中最大团的大小为 a。
综上所述 G 中最大团的 size 为 a 当且仅当 G
m
里的最大团的 size 是 ma。
EX2.完善 LPT 算法的性能（近似）比：R
LPT
=4/3-1/(3m)的证明
证明：当 m=1 时，因为 A(I)=OPT(I)，所以 A(I)/OPT(I) = 1= 4/3-1/3，显然成立
当 m>1 时，假设定理不成立，即有：A(I)/OPT(I)>4/3-1/(3m)
根据 ppt 上的证明结果，易知，对于违反该定理具有最少作业数的实例 I，有：
A(I)/OPT(I)=1<=4/3-1/(3m)
与假设矛盾。换句话说，对于违反该定理的实例集合，必然存在具有最少作业数的实例
I，使其不违反定理，矛盾。如果不存在这样的实例 I，因为 I 具有最少作业数，那么也就说
明这个违反定理的实例集合为空。所以当 m>1 时，不存在违反该定理的实例。
综上所述，LPT 算法的性能比为 R
LPT
=4/3-1/(3m)
资源评论
