全然图中的圈数

2024-01-21 05:20
文章标签 图中 全然 圈数

本文主要是介绍全然图中的圈数,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

今天问了 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

这篇关于全然图中的圈数的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/628470

相关文章

【408DS算法题】039进阶-判断图中路径是否存在

Index 题目分析实现总结 题目 对于给定的图G,设计函数实现判断G中是否含有从start结点到stop结点的路径。 分析实现 对于图的路径的存在性判断,有两种做法:(本文的实现均基于邻接矩阵存储方式的图) 1.图的BFS BFS的思路相对比较直观——从起始结点出发进行层次遍历,遍历过程中遇到结点i就表示存在路径start->i,故只需判断每个结点i是否就是stop

最短路径算法:迪杰克斯拉(Dijkstra)算法(基于贪心思想)【从一个顶点到其余各顶点的最短路径算法,解决的是有权图中最短路径问题】【能得出最短路径的最优解,但由于它遍历计算的节点很多,所以效率低】

Dijkstra算法是典型最短路算法,用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止。Dijkstra算法能得出最短路径的最优解,但由于它遍历计算的节点很多,所以效率低。 Viterbi和Dijkstra算法看起来比较像,两者的区别: Dijkstra算法适应范围更广。Viterbi算法用在特殊的有向无环图中,而Dijkstra算法可以用在

DFS、BFS、Union-Find:找出图中省份数量的最佳方法

题目理解 问题描述: 有 n 个城市,其中一些城市之间直接相连,另一些则不相连。如果城市 a 和城市 b 直接相连,且城市 b 和城市 c 直接相连,那么城市 a 和城市 c 间接相连。省份被定义为一组直接或间接相连的城市,组内不包含与之不相连的其他城市。给定一个 n x n 的矩阵 isConnected,其中 isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直

【uml】之类图中的关系

uml早就画完了图,但是自己迟迟没有总结,因为总觉的自己把握的不到位,虽然现在也还是不到位,废话少说,上篇博客总结了用例图中的几种关系,这篇就讨论一下类图中的几种关系。           在uml的所有图中,就我目前的水平,我觉得用例图和类图是最重要的,用例图上次已经介绍过了,这篇主要介绍类图,想要画好类图,就要先学会抽象类!之前我一直纠结于类图该如何抽象,问了几个人

关于图中节点间的概率求解问题-1

前提:节点是含有若干特征(小节点)的大节点,大节点间连接实际为特征间的连接 在一个网络图中,若干节点之间的概率问题有以下几种: 设现有A,B,C等若干大节点,其内特征为ai,bj,ck; P(A); //数出A节点发散的所有边的数量除以图中出现的总边数 P(AB); //即P(A)*P(B),原理同上 P(A,B); //此为联合概率,如果AB之间不相联系,则直接为零 P(

关于图中节点间的概率求解问题-2,未完探究中

最近在贝叶斯网络上遇到了难题,简单而言就是怎么求两个节点间的概率。 此问题的前提是,节点为大节点,内有若干特征,节点间的连接(或称为连线)实际为特征之间的连线。且两节点不是孤立的,而是在一个网络(或称一个图)中。 现在的方法是: 利用已知的特征之间的边,来分别计算边的条数,直接用条数来计算概率。 example: 求条件概率P(A|B),A内有 a0,a1,a2;B内有b0,b1;

关于图中节点间的概率求解问题

(本文年代久远,请谨慎阅读)前提:节点是含有若干特征(小节点)的大节点,大节点间连接实际为特征间的连接 在一个网络图中,若干节点之间的概率问题有以下几种: 设现有A,B,C等若干大节点,其内特征为ai,bj,ck; P(A); //数出A节点发散的所有边的数量除以图中出现的总边数P(AB); //即P(A)*P(B),原理同上P(A,B); //此为联合概率,如果AB之间不相联系,则直接为零P

如何从用户旅程图中挖掘差异化需求?

同一品类产品往往数量庞大,作为新入局的产品,需要打造差异化,才能脱颖而出。具体该如何做?本文作者从用户旅程图出发,结合相关案例,对不同阶段如何打造差异点展开了分析总结,与大家分享。 一个产品往往不止满足一个用户需求,或者说一个产品是多种用户需求的集合。简单的产品如笔,基本就是拿来写字的,满足写字一种需求。复杂的产品如手机,满足了非常多的用户需求,如通话、视频、音乐、娱乐、游戏、社交等等

图中有几个三角形

让我们先把三角形进行分类:1块组成的三角形、2块组成的三角形、依此类推。 1块组成的三角形有4个: 2块组成的三角形有:1+2,1+3,1+4,2+3,2+4,3+4.其中,1+4,2+3构不成三角形. 3块组成的三角形有:1+2+3,1+2+4,1+3+4,2+3+4。但是这些都无法构成三角形。 4块组成的三角形是1+2+3+4. 所以,总计有4+4+1=9个三角形。

2024.4.27力扣每日一题——查询网格图中每一列的宽度

2024.4.27 题目来源我的题解方法一 遍历方法二 优化 题目来源 力扣每日一题;题序:2639 我的题解 方法一 遍历 遍历每一列的所有数字,并计算长度,取其中最大的作为这一列的结果 时间复杂度:O(nmC)。C表示数字的最大 字符串长度 空间复杂度:O(1) public int[] findColumnWidth(int[][] grid)