找回密码
 欢迎注册
查看: 14261|回复: 7

[原创] 随机图中的完全子图

[复制链接]
发表于 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%$?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2018-4-5 23:36:11 | 显示全部楼层
写了一个生成随机图的程序和一个搜寻完全子图的程序,求得前面几项的结果如下。

  K   N   概率
  1   1    1
  2   2    0.5
  3   5    0.62109375
  4   9    0.6151...
  5  14   0.521...
  6  22   0.510...
  7  34   0.523...
  8  51   0.51...
  9  76   0.50...
10 113  0.50...
11 168  0.50...
12 250  0.51...
13 371  0.50...
14 553  0.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)$,出乎意料
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2018-4-6 10:37:11 | 显示全部楼层
你可以使用GNU的igraph看看
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2018-4-6 15:27:36 | 显示全部楼层
根据楼上的提示,安装了igraph,然后写了下面的代码:

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

  3. int main()
  4. {
  5.         igraph_rng_seed(igraph_rng_default(), 42);
  6.         while (1)
  7.         {
  8.                 igraph_integer_t cn;
  9.                 igraph_t graph;
  10.                 igraph_erdos_renyi_game(&graph, IGRAPH_ERDOS_RENYI_GNP, 168, 0.5, IGRAPH_UNDIRECTED, IGRAPH_NO_LOOPS);
  11.                 igraph_clique_number(&graph, &cn);
  12.                 printf("%d ", (int)cn);
  13.                 igraph_destroy(&graph);
  14.         }
  15.         return 0;
  16. }
复制代码

代码虽短,但是运行效率堪忧呀~

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

我自己写的代码如下:
  1. #include<ctime>
  2. #include<cstdio>
  3. #include<cstdlib>
  4. #include<cstring>

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

  6. unsigned int a[n][d],todo[d],done[d];
  7. unsigned __int64 g,h,p,q;
  8. unsigned char i,j,s;

  9. unsigned char rd()
  10. {
  11.         g=g*g/3+h+rand();
  12.         return(g&32767)>>14;
  13. }

  14. void ad(unsigned char i,unsigned char j)
  15. {
  16.         a[i][j>>5]|=1<<(j&31);
  17.         a[j][i>>5]|=1<<(i&31);       
  18. }

  19. unsigned char r(unsigned int p)
  20. {
  21.         for(unsigned char i=0;;i++)
  22.                 if(p&1<<i)return i;
  23. }

  24. void mce(unsigned char c,unsigned int *todo,unsigned int *done)
  25. {
  26.         unsigned char i,j,k;
  27.         unsigned int doing[d];
  28.         for(i=0;i<d;i++)
  29.                 if(todo[i]||done[i])
  30.                 {
  31.                         i=i<<5|r(todo[i]?todo[i]:done[i]);
  32.                         for(j=0;j<d;j++)
  33.                                 doing[j]=~a[i][j]&todo[j];
  34.                         for(j=0;j<n;j++)
  35.                         {
  36.                                 unsigned char jh=j>>5;
  37.                                 unsigned int jl=1<<(j&31);
  38.                                 if(doing[jh]&jl)
  39.                                 {
  40.                                         todo[jh]&=~jl;
  41.                                         unsigned int nt[d],nd[d];
  42.                                         for(k=0;k<d;k++)
  43.                                                 nt[k]=todo[k]&a[j][k],nd[k]=done[k]&a[j][k];
  44.                                         mce(c+1,nt,nd);
  45.                                         done[jh]|=jl;
  46.                                 }
  47.                         }
  48.                         return;
  49.                 }
  50.         if(c>s)s=c;
  51. }

  52. int main()
  53. {
  54.         for(g=time(NULL),srand(g);;memset(a,0,sizeof(a)))
  55.         {
  56.                 for(i=0;i<n-1;i++)
  57.                         for(j=i+1;j<n;j++)
  58.                                 if(rd())ad(i,j);
  59.                 for(i=0;i<n;i++)
  60.                         todo[i>>5]|=1<<(i&31);
  61.                 mce(0,todo,done);
  62.                 p+=s>11,q++,s=0;
  63.                 if(q%2<1)printf("%I64u %I64u %c",p,q,13),h+=time(NULL)+p;
  64.         }
  65.         return 0;
  66. }
复制代码

点评

我用了比特位来表示邻接矩阵,一次位运算就可以处理32个比特,我想这是我的代码效率高的缘故。我猜测标准库没有用位运算。  发表于 2018-4-7 22:32
猜测作为通用库,可能更加擅长处理一些常用的图而不是随机图  发表于 2018-4-7 21:55
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 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,这个近似值应该是可以的
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2018-4-7 10:04:58 | 显示全部楼层
虽然该数列的第$6$、$7$、$8$、$9$项与参考数列相同,

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

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

用楼上分析得到的$\Theta(\sqrt{2}^K)$来近似该数列更靠谱。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2024-3-29 02:40 , Processed in 0.043345 second(s), 17 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

快速回复 返回顶部 返回列表