KeyTo9_Fans 发表于 2012-5-7 10:38:57

随机图中的完全子图

图$G$是一个包含$N$个顶点的无向图。

对于任意一对顶点$(u,v)$，有边的概率是$50%$，且相互独立。

我们希望$G$中存在$K$个顶点的完全子图的概率至少为$50%$。

求顶点数$N$至少是多少。

例$1$：当$K=1$时，$N=1$，存在$1$个顶点的完全子图的概率为$100%$。

例$2$：当$K=2$时，$N=2$，存在$2$个顶点的完全子图的概率为$50%$。

当$K$比较大的时候，如何找最小的$N$，使得$G$中存在$K$个顶点的完全子图的概率至少为$50%$？

KeyTo9_Fans 发表于 2018-4-5 23:36:11

写了一个生成随机图的程序和一个搜寻完全子图的程序，求得前面几项的结果如下。

K   N   概率
1   1    1
2   2    0.5
3   5    0.62109375
4   9    0.6151...
514   0.521...
622   0.510...
734   0.523...
851   0.51...
976   0.50...
10 1130.50...
11 1680.50...
12 2500.51...
13 3710.50...
14 5530.50...

参考数列（第6、7、8、9项相同）：
http://oeis.org/search?q=22%2C34%2C51%2C76

本数列：
Minimum m such that the probability that there is a clique with size n in the Erdos-Renyi random graph with m vertices and parameter p=0.5 is at least 0.5
1, 2, 5, 9, 14, 22, 34, 51, 76, 113, 168, 250, 371, 553

数列的增长速度竟然是$\Theta(1.5^K)$，不是$\Theta(2^K)$，出乎意料:Q:

mathe 发表于 2018-4-6 10:37:11

你可以使用GNU的igraph看看

KeyTo9_Fans 发表于 2018-4-6 15:27:36

根据楼上的提示，安装了igraph，然后写了下面的代码：

#include <stdio.h>
#include "igraph.h"

int main()
{
        igraph_rng_seed(igraph_rng_default(), 42);
        while (1)
        {
                igraph_integer_t cn;
                igraph_t graph;
                igraph_erdos_renyi_game(&graph, IGRAPH_ERDOS_RENYI_GNP, 168, 0.5, IGRAPH_UNDIRECTED, IGRAPH_NO_LOOPS);
                igraph_clique_number(&graph, &cn);
                printf("%d ", (int)cn);
                igraph_destroy(&graph);
        }
        return 0;
}
代码虽短，但是运行效率堪忧呀~

当$N=168$时，我自己写的代码$0.9$秒就能跑$1$个图，上述代码要$2.0$秒才能跑$1$个图……

我自己写的代码如下：
#include<ctime>
#include<cstdio>
#include<cstdlib>
#include<cstring>

const int n=249,d=n+31>>5;

unsigned int a,todo,done;
unsigned __int64 g,h,p,q;
unsigned char i,j,s;

unsigned char rd()
{
        g=g*g/3+h+rand();
        return(g&32767)>>14;
}

void ad(unsigned char i,unsigned char j)
{
        a|=1<<(j&31);
        a|=1<<(i&31);       
}

unsigned char r(unsigned int p)
{
        for(unsigned char i=0;;i++)
                if(p&1<<i)return i;
}

void mce(unsigned char c,unsigned int *todo,unsigned int *done)
{
        unsigned char i,j,k;
        unsigned int doing;
        for(i=0;i<d;i++)
                if(todo||done)
                {
                        i=i<<5|r(todo?todo:done);
                        for(j=0;j<d;j++)
                                doing=~a&todo;
                        for(j=0;j<n;j++)
                        {
                                unsigned char jh=j>>5;
                                unsigned int jl=1<<(j&31);
                                if(doing&jl)
                                {
                                        todo&=~jl;
                                        unsigned int nt,nd;
                                        for(k=0;k<d;k++)
                                                nt=todo&a,nd=done&a;
                                        mce(c+1,nt,nd);
                                        done|=jl;
                                }
                        }
                        return;
                }
        if(c>s)s=c;
}

int main()
{
        for(g=time(NULL),srand(g);;memset(a,0,sizeof(a)))
        {
                for(i=0;i<n-1;i++)
                        for(j=i+1;j<n;j++)
                                if(rd())ad(i,j);
                for(i=0;i<n;i++)
                        todo|=1<<(i&31);
                mce(0,todo,done);
                p+=s>11,q++,s=0;
                if(q%2<1)printf("%I64u %I64u %c",p,q,13),h+=time(NULL)+p;
        }
        return 0;
}

mathe 发表于 2018-4-6 21:16:45

$C_N^K \frac{1}{2^{C_K^2}} ~=1/2$
$C_N^K~=2^{C_K^2-1}$
$N~=\root{K}{2^{C_K^2-1}K!}~=K/e\sqrt{2}^{K+1}$
然后可以查看对于这种逼近，K+1个点完全图的概率大概为$C_N^{K+1}\frac{1}{2^{C_{K+1}^2}}~=N/{K2^K}C_N^K \frac{1}{2^{C_K^2}}~=N/{K2^{K+1}}~=1/{e\sqrt{2}^{K+1}}->0$
所以对于比较大的K,这个近似值应该是可以的

KeyTo9_Fans 发表于 2018-4-7 10:04:58

虽然该数列的第$6$、$7$、$8$、$9$项与参考数列相同，

但是该数列从第$10$项起，增长速度比参考数列慢，而且与参考数列的差距越来越大，

说明用$\Theta(1.5^K)$来近似该数列，还是高估了它的增长速度。

用楼上分析得到的$\Theta(\sqrt{2}^K)$来近似该数列更靠谱。
页: [1]
查看完整版本: 随机图中的完全子图