全然图中的圈数

今天问了 J,Z,D全然图中圈数的问题。

例如以下是K5:



当中有非常多C4,比方:


也有非常多C5,比方:


先问里面有多少环,C3 + C4 + C5的个数?

Kn里面有多少环数?


===========================================


喝杯咖啡


=================== 思维1 ====================


先想的怎样知道 Kn 里面有多少个 Cn,然后想了有多少 Cn-1,可是发现直接不好想,

可是既然能想出 Kn 里面的 Cn,能够知道Kn-1里面有多少Cn-1,且能够知道Kn里面有 C( n, m ) 个 Km,

那么 Cycle 的总数就是 m 是从 3 到 n 中 C( n, m ) * Km中Cm的个数的累加。

如今怎么求Kn里面的Cn个数呢?


用构造吧,将 A 删了,如果知道 K4 里面 C4 的个数,那么每一个K4 里的 C4不可能仅仅有一条边不一样。

比方:




那么能够删掉 C4 里面的随意一边,比方这里删了 edge( B, C ),B 和 C 都能够和 A相连,

构造出一个 C5:


因为 C4 里面,有4个这种边,那么能够构造出 4 个这种 C5。

那 K5 中有多少 C4 呢?K4 中 C4的个数 * 4 * C( 5,4 )

==============================================


类推,事实上Kn中的 Cycle 的总数就已经结束了。


==================== 思维2 ======================


在想。



原文地址:https://www.cnblogs.com/mengfanrong/p/3984641.html