Question

如何找一个点数最少的极大独立集？高分求助！

请看清题目，不是求点数最多的极大独立集噢~
如果题目答的好，还有加分噢~
倒~这个就是老师给我留的题目...怎么能去问老师呢...

Answer 1

　　最大独立集的分布式近似算法（基于最高节点度算法）
　　===========================================================================================
　　点的状态：候选点，从节点，支配点，非支配点。
　　信息种类：people信息，worker信息，leader信息，degree信息，hello信息
　　维护列表：leader列表，degree列表，competitor列表
　　===========================================================================================
　　研究目的：簇与簇之间都是通过分布式网关相连接，可以使得簇头数目尽量少，从而使得源节点和目的节点之间的平均跳数较少，减少分组投递时延。
　　===========================================================================================
　　注：以下步骤仅为概要设计，很多延迟问题的细节问题尚未考虑周全。
　　===========================================================================================
　　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",则更新自己的"competitor列表"
　　若非支配点接收到"degree信息+ID"，则丢弃。

　　7. 经过一个延迟后，候选点观察自己是否收到"leader信息+ID"，如果有，则更新自己为从节点；如果没有，则通过观察"competitor列表"来判断自己是不是所有邻居节点中节点度数最大的，如果是，则更新自己为支配点。

　　循环2-7，并且每次循环前，competitor列表需要清空。直到图中所有节点全部为支配点或从节点。

Answer 2

太专业了吧，去学校问问教授吧，他们也许能
具体方法：去教室门口堵他
有奇效
呵呵

````
问别的老师啊~~~
````
高招吧

Answer 3

求独立集：
在图中求这样的一个定点集合I，I中任两个顶点不相邻且这样独立的顶点数最多。
例如应用在8皇后问题上，对于64个格，能攻击到的格之间有一条边。
放置尽可能少的皇后，使他们控制棋盘上全部格，这是一个最小支配集的问题。
放置尽可能多的皇后，而互相不攻击地共处，这是一个最大独立集问题。

覆盖集：
K是G图的一个顶点子集，且G的每一边至少有一个端点属于K，则称K是G的一个覆盖。(
顶点覆盖全体边)。若在K中去除任一顶点后将不再是覆盖，则K为极小覆盖。在所有的极
小覆盖中含顶点数最少的是最小覆盖，此时顶点数即为覆盖数。

独立集：
I是G的一个顶点子集，I中任两个顶点不相邻，则I是图G的一个独立集。若独立集I中增加任一
除I集外的顶点后I不再是独立集，则I是极大独立集。在所有极大独立集中含顶点数最多的为最
大独立集，此时的顶点数称为独立数。

独立集的性质：
1) 一个独立集是极大独立集，当且仅当它是一个支配集。
2) I是独立集，当且仅当G中除I集外所有顶点是一个覆盖集。
I是极大独立集，当且仅当G中除了I集外的所有顶点是一个极小覆盖。
3)极大独立集必为极小支配集，但极小支配集未必是极大独立集。

由于极大独立集与极小覆盖集有互补性，可以求极小覆盖集来达到求极大独立集的目标。
某顶点的所有相邻顶点进行积运算后在与与改顶点进行和运算，构成一个因子项，根据
逻辑运算得到结果便是一切极小覆盖。

/*求极小覆盖集 实际上是为了求独立集，他们互为补集
*与支配集相比，就是初试化不同，即形成的因子不通，但
*运算方法是一样的，注意find()方法
*/
＃i nclude <string>
＃i nclude <memory.h>
＃i nclude <iostream>
using namespace std;
#define maxn 100
typedef struct
{
string con[maxn];
int cnt;
}S;
S gene[maxn];
S res;
bool g[maxn][maxn];
int n,m;
string dir[]={"0","1","2","3","4","5","6","7","8","9"};
string inttostring(int num)
{
string s="";
int t,i;
char c;
while(num){
t=num%10;
s+=dir[t];
num/=10;
}
t=s.length()/2;
for(i=0;i<t;i++){
c=s;
s=s[t-i-1];
}
return s;
}
void init()
{
int i,j;
for(i=1;i<=n;i++){
gene.cnt=2;
gene.con[0]=inttostring(i);
for(j=1;j<=n;j++){
if(g[j] && i!=j) {
gene.con[1]+=inttostring(j);
}
}
}
}
void insert_into(S &temp,string str)
{
int cnt=temp.cnt;
int i,t;
string s;
for(i=0;i<cnt;i++){
s=temp.con;
t=str.find(s);
if(t!=-1) {
return;
}
}
temp.con[temp.cnt++]=str;
}
//find函数是为了滤去s2中的所有字符被包含的情况
bool find(string s1,string s2)
{
bool flag[maxn];
memset(flag,false,sizeof(flag));
int n1=s1.length(),n2=s2.length(),i,cnt=0;
for(i=0;i<n1;i++)flag[s1-'0']=1;
for(i=0;i<n2;i++)if(flag[s2-'0'])cnt++;
if(cnt==n2) return true;
return false;
}
void modify(S &temp)
{
int cnt=temp.cnt,i,j;
bool flag[maxn];
S s;
string s1,s2;
memset(flag,true,sizeof(flag));
for(i=0;i<cnt;i++){
if(!flag)continue;
s1=temp.con;
for(j=0;j<cnt;j++){
if(i==j) continue;
if(!flag) break;
s2=temp.con[j];
if(find(s2,s1))
flag[j]=false;
else if(find(s1,s2))
flag=false;
}
}
for(i=0,s.cnt=0;i<cnt;i++){
if(!flag) continue;
s.con[s.cnt++]=temp.con;
}
temp=s;
}
string add(string a1,string a2)
{
string temp;
int i=0;
bool flag[maxn];
temp="";
memset(flag,false,sizeof(flag));
int len1=a1.length(),len2=a2.length();
for(i=0;i<len1;i++) if(!flag[a1-'0']) flag[a1-'0']=true;
for(i=0;i<len2;i++) if(!flag[a2-'0']) flag[a2-'0']=true;
for(i=1;i<=n;i++)if(flag)temp+=dir;
return temp;
}
void muti(S s1)
{
S temp;
temp.cnt=0;
string a1,a2,a3;
int i,j,cnt1,cnt2;
cnt1=res.cnt;cnt2=s1.cnt;
for(i=0;i<cnt1;i++){
a1=res.con;
for(j=0;j<cnt2;j++){
a2=s1.con[j];
a3=add(a1,a2);
insert_into(temp,a3);
}
}
modify(temp);
res=temp;
}
void proceed()
{
res=gene[1];
int i;
for(i=2;i<=n;i++){
muti(gene);
}
for(i=0;i<res.cnt;i++)
cout<<res.con<<endl;
}
void read_graph()
{
cout<<"Vertex Num "<<" Edge Num"<<endl;
cin>>n>>m;
int i,j,k;
memset(g,false,sizeof(g));
for(k=0;k<m;k++){
scanf("%d%d",&i,&j);
g[j]=true;
g[j]=true;
}
for(i=1;i<=n;i++)g=true;
init();
proceed();
}
int main()
{
while(true){
read_graph();
}
return 0;
}
/*
6 9
1 4
1 2
2 3
3 4
1 5
2 5
3 6
5 6
4 6
*/

Answer 4

上天

Answer 5

你给他写个错误答案不就行了吗？然后你在让他教你，即完成了作业，又学到了知识．变通一下啊

Answer 6

地方病地方