百科问答小站 logo
百科问答小站 font logo



n 座桥,连通 n+1 个岛,有多少种连法? 第1页

  

user avatar   nayilus 网友的相关建议: 
      

Cayley公式, 个顶点的不同树总数为 。个顶点,条边的连通图必然为树。因此本题答案即 。

Cayley传统上以Kirchoff定理通过线代证明,下面列出Pitman的一种比较有趣的算两次证明:

假设n个顶点可以组成的不同树总数为 。

现在从一个有个顶点,没有边的图出发,逐渐加入边,直到形成一棵有根树(有固定的根,两棵一样的树如果上面代表根的顶点不同视为不同的有根树),求这些边加入顺序的总数。

算一次:从 棵树之一开始,任选一点为根,有种选法,接下来条边有 种排法,总顺序数为

算两次:从空图开始一条条边加,假设加入 条边,则图中会有 棵互不连通的有根树,现在再增加一条边,这条边的起点可以是 顶点中的任一,终点只能是和起点不同的有根树的根,共 种选择,所以有 种选法。这里两棵树结合后形成的新树的根为起点原来所在的树的根。

所以总共的可能性有

因此 ,即




  

相关话题

  你有没有推导过一个复杂的却「贴近生活」的公式? 
  只有三维向量有向量积吗? 
  证明如果幂级数在收敛圆上一点收敛,那么从圆内沿任意不与圆周相切的方向逼近时有极限? 
  如果高考允许以一百万人民币一分的价格无限量购买分数(收入归大学所有),那对社会会有怎样的影响? 
  如何看待卡西·曼夫妇发现的可无缝密铺平面的五边形? 
  连续的周期函数都有最小正周期吗? 
  请问以下两个概率问题的答案是否一样? 
  这道定积分怎么算(据说是某211期末考试题)? 
  本人文科生 喜欢数学 大学想读数学系但没选物理 怎么办? 
  下一次数学突破会在哪里? 

前一个讨论
一水龙头在高空拧开,垂直下落,水流最细可达多少?
下一个讨论
有哪些有趣的或者是反常识的数学问题?





© 2025-04-04 - tinynew.org. All Rights Reserved.
© 2025-04-04 - tinynew.org. 保留所有权利