数学研发论坛

 找回密码
 欢迎注册
查看: 1215|回复: 5

[原创] 平均度为1的随机图的最大连通块大小

[复制链接]
发表于 2013-1-11 22:53:49 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有帐号?欢迎注册

x
在顶点数为$2n$的完全图中随机取$n$条边,得到的图记为$G$。

于是图$G$有$2n$个顶点,$n$条边,顶点的平均度为$1$。

设$G'$是$G$中最大的连通块(顶点数最多的连通子图)。

我们将$G'$的顶点个数的平均值记为$g$。

问题$1$:

给定$n=1,2,3,...$,求$g$的值。

问题$2$:

求证:$\lim_{n->\infty}ln(g)/ln(n)=2/3$

问题$3$:

求$\lim_{n->\infty}g^{1.5}/n$等于多少?

#####

当时论坛人少,现在人多了,我让我的朋友jsliyuan把这贴子重新顶起来,以获得更多坛友们的关注~

如果还是做不出来,我还可以去Math Overflow社区提问呀~
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2019-1-20 08:21:28 | 显示全部楼层
顶一下
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
回复

使用道具 举报

发表于 2019-1-21 03:06:03 | 显示全部楼层
G有n条边是确定的,但咋肯定有2n个顶点呢

点评

图G就是有$2n$个顶点的图,这是已知条件。图$G$可能有孤立的顶点。  发表于 2019-1-21 03:49
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2019-1-21 08:11:29 | 显示全部楼层
可以先看一看每个点上关联多少条边。
对于任意一条边,不使用某个指定的点的概率是${C_{2n-1}^2}/{C_{2n}^2}={n-1}/n$
所以对于一个指定的点,和其关联的边的数目为k的概率是$P(d(v)=k)=C_n^k ({n-1}/n)^{n-k}(1/n)^k$
然后采用极大似然估计,可以估算出关联边数最多的点关联的边的数目接近$\sqrt{2\ln(n)}$
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2019-1-21 17:28:23 | 显示全部楼层
这道题让我想到了那个连通图问题以及后面的渐近计数
https://bbs.emath.ac.cn/thread-9662-1-1.html

本质上要分析出2n个点中n条边构成的简单图中连通图的种类,以及非连通图中最大连通子图的顶点数分布。然后根据计数来计算平均值。
不过这种变递归长度的递归式如何对其结果渐近分析?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

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

GMT+8, 2019-11-22 09:56 , Processed in 0.063124 second(s), 20 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

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