2009-07-20 14:35| 
38 Comments | 本文内容遵从假设我们俩各自独立地随机选取一个有无穷多个顶点的图（两点之间1/2的概率有边1/2的概率没有边）。那么，我们俩选到相同的图的概率是多少？
令人难以置信、但想通了之后又异常显然的是，两个图相同的概率为1。并且，我可以精确地告诉你，这个相同的图是什么样子的。考虑这样一个无穷大的图，我们用自然数1, 2, 3, ...给所有顶点标号，然后如果y的二进制表达中的右起第x位为1，就在顶点x和顶点y之间连一条线。比如，顶点5就和顶点1、顶点3相连。我可以证明，我们俩都100%地会选取到上述这个图。
我们先来定义一个东西。我们说一个图是“任意连通”的，如果对于任意两个不相交的有限点集U和V，总能找到一个顶点x，使得x和U里面的所有顶点都相连，但和V里面的任一顶点都不相连。下面我们先证明，随机选取一个无穷大的图，该图满足任意连通性的概率为1；其次我们说明，所有满足任意连通性的图都是同构的。
为什么一个随机选取的无穷大图具有任意连通性的概率为1呢？我可以反过来说明，一个随机图不满足该性质的概率为0。考虑两个任意的有限点集U和V，假设这两个点集一共有n个点。那么，随便选取一个点x，它和U里所有点都相连，但和V里所有点都不相连的概率显然为1/2^n（因为两点之间是否相连是独立确定的，且概率为1/2）。不管n有多大，1/2^n总是一个不为0的数，但供我选的点有无穷多个。在我第k次选点后还找不到满足条件的点的概率为(1-1/2^n)^k，它是一个最终趋于0的值。
然后我们来证明，只要两个图都满足这个性质，我一定能为它们的顶点适当编号，使得图A的点x点y之间有边当且仅当图B的点x点y之间有边。这个证明是构造性的。假设我们已经找到了一个图A和图B的同构子图，这个子图有6个顶点，分别标号为1, 2, 3, 4, 5, 6。在图A当中选取下一个未编号的顶点，把它标号为顶点7。假设顶点7和前面6个顶点中的2, 4相连，和1, 3, 5, 6都不相连。由于图B满足任意连通性，因此图B当中必然也存在一个点，它和自己图里的那个2, 4相连，和1, 3, 5, 6都不相连。于是，把图B中的这个新的点编号为顶点7。不断执行该操作，就可以给图里的每个顶点确定一个适当的编号。
有一个问题是，不断这样操作后，虽然图A里的所有顶点都能找到图B中的对应顶点，但图B中可能还剩有顶点一直未被编号。问题的解决办法也很简单：利用任意连通性找到图B中与图A中的顶点7相对应的点后，立马换成让B选取下一个未编号的顶点并命其为顶点8，让图A利用任意连通性来找它的对应点。如此交替变更图A和图B的角色，就能保证两个图中的每个点都能编上号了。
那么，为什么我刚才说，我们选出的图都和第二段中描述的那个图相同呢？因为，那个图显然满足任意连通性。
来源：http://blogs.warwick.ac.uk/dangoodman/entry/something_completely_ridiculous/
相同改成同构比较合适。。
其实仔细想一想确实是“异常显然”。。。
对于两个n个顶点构成的随机图，两者同构的概率“约等于”1-(1-(1/2)^(n*(n-1)/2))^(n!)。n取无穷大时极限为1
嗯~拜托帮忙把links里的地址改一下，http://www.asyanyang.com/
楼上 >_<
仔细研究了一下，这个证明似乎是有问题的，简单的讲就是有限个1乘起来还是1但无限个1乘起来就未必是1了。
从另一个角度考虑，对于两个n个顶点构成的随机图，定义两者同构的概率p(n)。p(n)小于两者边数相同的几率，显然地，后者在n->∞时为0。之前对于p(n)的估计比较粗糙。
这个证明的最后一步好像有问题
你最后一步只证明了包含有限点的“任意连通”图是同构的
其中使用的是数学归纳法
但是, 注意数学归纳法只能证明有限集合的命题
对于无限集 数学归纳法是不适用的
最后一步的证明两个“任意连通”图同构是有问题的
证明过程使用了数学归纳法
但是数学归纳法只适用于证明有限集的命题
对于无限集数学归纳法是不适用的
唉
恩... asyanyang.com 即将成为OI人访问最多的非OI blog了.
数学归纳法基于反证法和最小数原理，可以应用于无限集，假设原命题不成立，必然存在最小的n使得p(n)不成立，然后可以将其证伪
不錯～
地基的数学归纳法定义不知从何而来？
http://zh.wikipedia.org/w/index.php?title=%E6%95%B0%E5%AD%A6%E5%BD%92%E7%BA%B3%E6%B3%95&variant=zh-cn
这个是一般被认同的数学归纳法的定义。
那么，随机选取两个无穷大的方阵，它们相似的概率是不是也是1呢？赫赫，如果是，它们的特征值排序后构成一个什么样的无穷序列呢？（注：可以从简单的情况开始，设方阵中的每个数都是满足正态分布的实数。并且方阵是对称的，好让它的特征值可以排序。赫赫。）
3L……M67MS以前说过什么话……
看来高估了这里的水平.我再来解释下,普通的数学归纳法是不适用无限集的
只有超限归纳法适用于无限集, 超限归纳法是数学归纳法在序数上的扩展
现在来尝试用超限归纳法证明
1. 假设任意连通图A拥有α个点时候 图A与构造图同构
2. 则任意连通图B拥有β=α+1个点的时候 图B与构造图同构
(α, β为序数)
两步都有问题.
步骤1问题: 构造图只构造了顶点数小于ω的图, 所以当α > ω时图A不可能与构造图同构
步骤2问题: 若要在图A中加入第β个定点, 那么要把α个点分为U,V两个集合, 如果α >= ω, 那么U,V中必然有一个集合拥有无穷个点, 但是原证明中只证明了有限个点连通性(原文:考虑两个任意的有限点集U和V).
对于α = ω的情况, 无法用数学归纳法证明 也无法用超限归纳法证明
所以在ZFC集合论中, 楼主的命题对所有图都不成立
(ZFC集合论包含选择公理, 选择公理等价于良序公理, 所以集合顶点数必然是个良序的, 所以必然是一个序数)
关于 超限归纳法 序数 ω 的定义 ZFC集合论 选择公理 良序公理 请自行wikipedia
回10楼: 我不知道你强调"数学归纳法"本身的证明有什么意义
回12楼: 要懂得尊重别人 多考虑考虑再回复 人家知道啥是数学归纳法
祝贺Blog四周年~~
数学归纳法显然不适用于无穷的情况，记得大一上数理逻辑的时候老师举的例子，考虑集合{1,2,...,n},n有限的情况下，该集合均有最大的数，n为无穷的时候（虽然不能这么说，但相信大家明白我的意思），就没有了。这个例子或许不太好，不过15楼解释的比较清楚了～
@15楼
首先我当时似乎没有什么态度问题，陈述事实而已。
你的表述自然是会引起误解的。“不适用于无限集”的说法显然违背数学归纳法的一般理解，而我当然无从猜想你究竟是什么意思。
另外，我认为这里是可以转化为数学归纳法的叙述形式的，只是表面上不符合而已。
15楼可以啊！学中文的不能小觑。你问问数学的学生，是不是每个人都知道超限归纳。
不好意思 我浏览器显示出了问题，把15楼和16楼弄混了。
[...] 所以我今天要学习这样一个有趣的图论定理。它看起来似乎有悖直观，但是实际上由于它涉及到无穷，任何有足够经验的数学人都会在心里留些surprise的准备。这里是本篇主要内容的来源。我是在matrix 67看到了他的译文。由于描述起来很简单，我猜想这个应该是一个随即图中熟知的定理。总之简单易学，值得行业内外的人看看。 [...]
我还是没弄懂哪里使用了数学归纳法
@15
我不明白为什么不能用普通的数学归纳法（原命题基于自然数的啊），请解释下，谢谢。
对于你步骤二中的问题，原文只是举了有限集为例子说明概率的求法，再求极限后求出无限图任意联通的的概率。
我水平比较低，才升高中，请多指教
我来个简化到极点的例子：
证明(0, 1)中一个随机实数以概率1与0.1111111111111111111111.............同构。
首先可证明：随机实数小数点后只有有限个1的概率为0（对应于“任意连通”：）。
选一个“n点同构子图”0.1...1，得到“n+1点同构子图”0.1...11的概率为1，按数学归纳法原理，证毕。
前面的极简例子上下文是：通过改变数字顺序达成一致叫做同构。这是在别的地方讨论时的上下文。
顿悟~楼主的证明方法只能证明存在无穷大同构子图，不能证明所有的点都包括进来了，就象我证明随机实数与0.11111......同构的实质一样。
还是不准确，更准确表述为：
楼主的证明方法只能证明以概率1存在无穷大同构子图，不能证明以概率1将所有的点都包括进来了，就象我证明随机实数与0.11111......以概率1同构的实质一样。
我是文盲，我不知道啥叫超限归纳，但是我觉得如果一个图边集是空的，另一个有边它们怎么能同构呢……
两个随机选取的n点有穷图同构的概率应当是随n的增长而减小直至趋于0的，如果到实无穷图时反而突变为以概率1同构，本身就否定了归纳法在这种情况下的适用性。
@24
选一个“n点同构子图”0.1...1，得到“n+1点同构子图”0.1...11的概率为1,这步如何归纳
首先我承认这个证明我没看懂。下面的文字只是就命题而言
我认为出现争议的核心原因在于将“相等”应用到无限的时候所导致的矛盾。
最简单的例子：设把硬币抛阿列夫零次为一次试验，则两次试验中正反面个数分别相同的概率为p。
1.定义p（n）为把硬币抛n次，正反面个数一样的概率。
我们可以定义p=p（n）|n->∞。p=0
2.正面的个数是阿列夫零的概率为1，反面亦然。阿列夫零与阿列夫零相等。从而两个试验的结果相同的概率为1。
这两种解释在似乎都没错。只是因为命题表达不严密（如何严密化？？）所造成互相矛盾的结果。这篇文章应该是采取了后种解释吧。
不过不知道大家对我前面提出过的“有限个1乘起来还是1；但无限个1乘起来就未必是1了”这一论点有何想法？
pp评论的有道理。严格地说，就是这样：
样本空间为所有的随机图：{A:V(A)=N,E(A)=...}
定义事件S为{A:∀U,V⊂V(A)，∃x，x与U相连而与V分离}，而将A的子集对编号为U_i,V_i后令事件S_i为{A:∃x，x与U_i相连而与V_i分离}，则显然S=⋂S_i。
我们的证明只给出了对每一个i，P(S_i)=1
于是就有两个问题：
各S_i未必互相独立
aleph0个1相乘未必为1（概率论中的1都是极限意义上的）
[ZT]我现在想到一个证明，但仍有一个尾巴，等着老大的测度论。
引理：两个可数个顶点的无穷图A、B都可以用自然数将全部顶点无遗漏地标上号。（不证自明吧）
1、A{0}和B{0}是同构的，tsy所说的找不到归纳起点问题不存在，不过博主一开始就用了6个顶点的起点，是有点迷惑人的。
2、然后，找到与A{0，1}同构的—假定为—B{0，5}
3、接下来，从A、B中找出未取出的最小编号点，这里是B{2}
4、接下来，找出与B{0，2，5}同构的—也是假定为—A{0，1，8}
5、接下来重复第2步，这次找到的是A{2}
6、重复第4步，找出与A{0，1，2，8}同构的—假定为—B{0，2，5，9}
……
这样，如果每一步是必然事件而非以概率1找到下一个同构顶点，则A、B的任意顶点N都将在不迟于第2N步被取出，A、B同构被证明。
可是，如果某一步就是找不到下一个同构顶点，而除此之外的无穷次寻找都能找到，似乎这个测度为零的事件不会破坏以概率1找到下一个顶点的说法。
如果无穷次寻找中以非0概率发生1次找不到下个顶点的情况，就破坏了A、B同构概率为1的结论，但并不破坏每一步找到下一个同构顶点的概率为1的性质。
第3步找到的应是B{1}，痴呆了~
pp 无限个1相乘 最简单的例子就是e=lim(1+1/n)^n (n->∞)
sss 引理：两个可数个顶点的无穷图A、B都可以用自然数将全部顶点无遗漏地标上号。（不证自明吧） 这个是错的 存在不可数图的
@35
引理是对的啊，他只针对顶点可数
@31、32
很有道理，原来是证明任意连通性成立时，每次选点不是必然事件，而是概率为1，无限个1相乘未必是1.
@35
你那个例子有问题，这里的无限个1相乘未必是1，每个1的极限都要是1，而不是这串1的极限是1
[...] http://www.matrix67.com/blog/archives/2168 此条目发表在 数学 分类目录。将固定链接加入收藏夹。 ← 智商测验 [...]