|
以文本方式查看主题 - 中文XML论坛 - 专业的XML技术讨论区 (http://bbs.xml.org.cn/index.asp) -- 『 计算机考研交流 』 (http://bbs.xml.org.cn/list.asp?boardid=67) ---- 问一个图论课后题(2) (http://bbs.xml.org.cn/dispbbs.asp?boardid=67&rootid=&id=36513) |
|
-- 作者：carroty -- 发布时间：8/7/2006 5:39:00 PM -- 问一个图论课后题(2) 标定完全图kn,e为其中任意一边,证明,kn-{e}的生成树的数目为:(n-2)n^(n-3) 完全没思路~ 谁知道?谢谢~ |
|
-- 作者：Logician -- 发布时间：8/7/2006 6:29:00 PM -- 思路提示： 1、对于K_n中的某条边e，K_n-e的生成树恰好是K_n的所有生成树中，不含边e的那些树。 2、K_n中每个边是“对称的”，所以每条边在K_n的所有生成树中出现的“概率”（或者说出现的总次数）是相同的。 3、K_n共有n^(n-2)棵生成树，每棵生成树有n-1条边。 |
|
-- 作者：carroty -- 发布时间：8/7/2006 10:36:00 PM -- 奥,谢谢,1,3我都知道了,2的提示比较有价值:) |
|
-- 作者：carroty -- 发布时间：8/8/2006 9:18:00 AM -- 我想了想,是不是这样的: 考虑通过e的边,在所有边中取n-1个边,且有一边同过e的可能性为:C(n-2)(n(n-1)/2))/(C(n-1)(n(n-1)/2))=2/n,C(m)(n)是从n中取m的组合数.但是似乎不能说明:过e的生成树占所有生成树的比例也是2/n. |
|
-- 作者：carroty -- 发布时间：8/8/2006 9:26:00 AM -- 有了,因为生成树的总数是n^(n-2),每个生成树都有n-1条边,所有n^(n-2)个生成树总共用边(n-1)n^(n-2)次,因为每条边的位置都是"平等的",则每条边出现的次数是相等的,所以,在n(n-1)/2条边中,过e的边有(n-1)n^(n-2)/(n(n-1)/2)=2n^(n-3) 所以不过e的数目为:(n-2)n^(n-3). :) (头都快想暴了....) |
|
-- 作者：Logician -- 发布时间：8/8/2006 1:31:00 PM -- Nod. 就是这样。这里还用了一个显然的结论：一条边在同一棵树中至多出现一次。所以e总共出现2n^(n-3)，说明恰好有2n^(n-3)棵过e的生成树。:) |
|
-- 作者：carroty -- 发布时间：8/8/2006 6:13:00 PM -- 谢谢~,你怎么什么都会啊~ 啧啧~ |
|
-- 作者：creating -- 发布时间：8/8/2006 8:08:00 PM -- 大家多发些这样的东西...有得想...呵呵,不错!一会还想不出来 |
|
W 3 C h i n a ( since 2003 ) 旗 下 站 点 苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》 |
62.500ms |