首页 > 代码库 > 最大团问题的小思考&算法demo
最大团问题的小思考&算法demo
/* fore
今天挖维基百科的图论（NP问题那么多，我最爱看这个八卦了）
挖了挖完全NP问题，找到了个最大团问题。
这个名字有点怪，维基百科也没有相关词条，度娘是这样解释的——
给定无向图G=(V,E)，其中V是非空集合，称为顶点集；E是V中元素构成的无序二元组的集合，称为边集，无向图中的边均是顶点的无序对，无序对常用圆括号“( )”表示。如果UÍV，且对任意两个顶点u，v∈U有(u,v)∈E，则称U是G的完全子图。G的完全子图U是G的团当且仅当U不包含在G的更大的完全子图中。G的最大团是指G中所含顶点数最多的团。
如果UÍV且对任意u，v∈U有(u,v)不属于E，则称U是G的空子图。G的空子图U是G的独立集当且仅当U不包含在G的更大的空子图中。G的最大独立集是G中所含顶点数最多的独立集。
对于任一无向图G=(V,E)，其补图G‘=(V‘,E‘)定义为：V‘=V，且(u,v)∈E‘当且仅当(u,v)∉E。
如果U是G的完全子图，则它也是G‘的空子图，反之亦然。因此，G的团与G‘的独立集之间存在一一对应的关系。特殊地，U是G的最大团当且仅当U是G‘的最大独立集。
*/
假如我没有搞错，那么这个完全NP问题就是在一堆麻线球中，找一个完全图咯？
打开脑洞，建立一个物理模型。
假设每一个顶点是一个小池，边是渠道，A顶点装有a流体，以此类推，这种流体有一个神奇的性质——它只能流过一个渠道。
然后按顺序图遍历一次//为什么不能画图啊摔！
1, 按路径遍历图/*路径（X,Y）指X连通Y*/
比如 A, B，C，D，E……X,Y,Z，假设图GG有n个顶点，G[n]
G[0]=A ,G[1]=B...
2，每一个顶点建立一个缓存池，存放其中流体。
有路径(A,B)(B,C)(A,D)(B,D)(C,D)(B,C)用集表示
A{a,b, , d}
B{a,b, c,d}
C{ ,b,c,d}
D{ ,b, ,d}
for(i=0;i<n;i++){
if (A[i]^B[i]^C[i]^D[i]==1)
printf("%d,%c",i,GG[i]);
}
3，{GG[i]}就是最大团咯？
写得很混乱，不知道对不对……
一起说是随笔，不如说是草稿。
最大团问题的小思考&算法demo
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。