如何找一个点数最少的极大独立集？高分求助！
更大独立集的分布式近似算法（基于更高节点度算法）
===========================================================================================
点的状态：候选点，从节点，支配点，非支配点。
信息种类：people信息，worker信息，leader信息，degree信息，hello信息
维护列表：leader列表，degree列表，compe *** 列表
===========================================================================================
研究目的：簇与簇之间都是通过分布式网关相连接，可以使得簇头数目尽量少，从而使得源节点和目的节点之间的平均跳数较少，减少分组投递时延。
===========================================================================================
注：以下步骤仅为概要设计，很多延迟问题的细节问题尚未考虑周全。
===========================================================================================
1. 所有节点初始状态为候选点。
2. 候选点每经过一段大的延迟（保证234567步能完成一次遍历），则向周围节点发送"people信息+ID"。
3. 若支配点接收到"people信息+ID"，则返回"leader信息+ID"。
若从节点接收到"people信息+ID"，则返回"worker信息+ID"。
若候选点接收到"people信息+ID"，则返回"hello信息+ID"。
若非支配点接收到"people信息+ID",则返回"hello信息+ID"。
4. 若候选点接收到"leader信息+ID",则把自己变成从节点,并更新自己的"leader列表"
若候选点接收到"worker信息+ID"，则在一个延迟后，判断自己的degree是否为1，不为1，则更新自己为非支配点；为1的话，则更新自己为支配点。
若候选点接收到"hello信息+ID"，则自己的degree+1。
5. 候选点向周围所有邻居发送"degree信息+ID"
6. 若支配点接收到"degree信息+ID",则将返回"leader信息+ID"。
若从节点接收到"degree信息+ID",则丢弃。
若候选点接收到"degree信息+ID",则更新自己的"compe *** 列表"
若非支配点接收到"degree信息+ID"，则丢弃。
7. 经过一个延迟后，候选点观察自己是否收到"leader信息+ID"，如果有，则更新自己为从节点；如果没有，则通过观察"compe *** 列表"来判断自己是不是所有邻居节点中节点度数更大的，如果是，则更新自己为支配点。
循环2-7，并且每次循环前，compe *** 列表需要清空。直到图中所有节点全部为支配点或从节点。
如何求最小支配集，更大独立集
有一个图G，现在希望在一些点建立控制站，每个控制站能控制与它相临的点（直接相连），现在希望有选择的在一些点建立控制站，使得以最小得控制站数，控制所有的点；
输入：之一行，N（表示图中点的个数）
接下来有若干行`每行两个数
A，B（表示A点与B点是相临的，注意，是无向图）
输出：之一行，K（表示最小支配集的个数）；
接下来输出每个最小支配集，每个支配集一行，支配集内点与点用空格隔开。
样例：in
4
1 2
1 3
2 4
3 4
out
2
1 2
1 3
1 4
2 4
2 3
3 4
请回答者附上源程序`用搜索，贪心的兄弟就别回答了`我这里是想寻求一个适用所有情况通用算法；
数据规模：N400
{$i-}{$s-}{$r-}
var
min,esc,esc2,t,m,total,count,e,a,b,c,n,d:longint;
j:array[0..4000,0..40] of longint;
out:array[0..400] of longint;
dian:Array[0..40] of longint;
data,temp,use:Array[0..40] of longint;
procedure try(q:integer);
var
w:integer;
begin
esc:=0;
if count=min-1 then exit;
for w:=1 to n do
if (j[q,w]=1)and(dian[w]=0) then begin dian[w]:=q; inc(m); inc(esc);end;
if dian[q]=0 then inc(esc);
if (esc=0) then exit;
IF DIAN[Q]=0 THEN
begin
dian[q]:=q;
inc(m);
end;
INC(count);
temp[count]:=q;
if (m=n)
then
begin
if countmin then
begin
min:=count;
for w:=1 to count do
out[w]:=temp[w];
out[0]:=count;
if dian[q]=q then
begin
dec(m); dian[q]:=0;
end;
dec(count);
for w:=1 to n do
if (j[q,w]=1) and (dian[w]=q) then begin dian[w]:=0; dec(m); end;
exit;
end;
end;
for w:=q+1 to n do
if kill[w]+countmin then
try(w);
if dian[q]=q then
begin
dian[q]:=0;
dec(m);
end;
for w:=1 to n do
if (j[q,w]=1) and (dian[w]=q) then begin dian[w]:=0; dec(m); end;
dec(count);
end;
begin
assign(input,'ray.in');
reset(input);
assign(output,'ray.out');
rewrite(output);
readln(n);
while not eof do
begin
readln(a,b);
if (aB)and(ioresult=0) then
begin
j[a,b]:=1;
j[b,a]:=1;
data[a]:=1;
data[b]:=1;
end;
end;
min:=maxlongint;
for a:=1 to n do
try(a);
writeln(out[0]);
for b:=1 to out[0] do
write(out[b],' ');
close(input);
close(output);
end.
problem:
有个图有n个结点，y条边
任选图中一个顶点，把它染成黑色，则和它相连的顶点必须都被染成白色，但与被染成白色的顶点相连的顶点可以被染成白色也可以被染成黑色，问：这个图最多有多少个顶点能被染成黑色？
---------------------------------------------------------------
相当于求图的更大独立集。
独立集: 图的顶点集的子集，其中任意两点不相邻。
求一般图的更大独立集是NP hard。
具体程序实现可以通过求最小覆盖集来求更大独立集。
图G(V,E)的覆盖集D是顶点集的一个子集,并满足:任意 vi,vj属于E,vi属于D或vj属于D
定义 *，+ 满 *** 换率，结合率，
且 *对+分配 (a+b)*c = a*c + b*c
吸收率：
a+ab = a
a*a = a
a+a = a
这样，求极小覆盖集：
M(连乘)( (v[i] + M(所有与v[i]相邻的点) )
i=0 to n
结果化简后的每个因子项即对应一个极小覆盖集。
for example:
a---b---c
\ / \ /
d e
(a+bd)(b+acde)(c+be)(d+ab)(e+bc)
= acde+abe+bcd+abc+bde
acde,abe,bcd,abc,bde 既是G的各个极小覆盖集。
因为极小覆盖集和极大独立集互补，用abcde 减去各个极小覆盖集，
既得到极大独立集：
b dc ae de ac
其中dc ae de ac是更大独立集。
两个例题,自己揣摩吧~~~
n阶零图的点着色数是
n阶零图的点着色数是2。
证明取树G的任意一点P，对树中所有结点按下面方式着色：如果结点与P的路径长为偶数，则该结点着某种颜色C1，如果结点与P的路径长为奇数，该结点着另外一种颜色C2，不可能有相邻的两点着同一种颜色，用C1，C2两种颜色对树G进行了正常着色，G的着色数为2。
构造的图
找出全部的极大独立集．冉类似地重复第二步。当某一步得到的子图是个零图时，这个零图的结点构成图的一个独立集，从原图得到这个零图的过程中每次删去的极大独立集全体构成了结点集的一个独立分划。
上述 *** 就是找出所有的这种分划，其中由分块数最少的分划给出图的色数。这种 *** 的工作量太大，经过改进，人们证明只需在上述 *** 中把求全部极大独立集改为求包含图的更大度结点的全部极大独立集就行了。
