shshsh_0510 发表于 2010-1-13 09:14:51

无圈子图的概率

一个完全2分图，就是图的顶点分为A,B两个集合，中任意 $a \in A$和$b \in B$都有边相连。
设|A|=m,|B|=n,则共有m*n条边
从这些边随机挑k个，组成一个子图，

求此子图不含圈的概率。(k<m+n)
对于完全图我会求，但完全2分图好像复杂很多，没想清楚。各位有空帮想想 :)

litaoye 发表于 2010-1-14 22:30:31

帮顶一下吧，LZ先说说完全图的，我学习一下，再看二分图的！
乱问一句，用递推有戏么？或者把选边变化为选点，可行么？

mathe 发表于 2010-1-15 13:06:59

是一个计数问题,完全图的确应该简单很多

shshsh_0510 发表于 2010-1-15 22:21:16

是啊，完全图容易多了
我的方法是从cayley计数定理+lagrange反演求出k树森林计数，再建立一个映射到原问题。
对二分图好像难不少，实际上我并不想求精确计数，我只想求其数量级，我猜数量级和完全图的差不多，但还没证明。

litaoye 发表于 2010-1-17 12:27:51

看了shshsh_0510说的几个词，暂时不是我能搞明白的，还是等大牛们吧！

ztfreedom 发表于 2010-1-29 21:37:17

版主女儿甚是可耐...题难...
页: [1]
查看完整版本: 无圈子图的概率