一个非连通图(无自回路和多重边)有66条边,那么它至少有()个顶点
A.11
B.12
C.13
D.14
正确答案是 C
既然是不连通图,那么就从节点中减去1个,然后剩下的节点有66条边,根据排列组合算,当节点数为12时,从中选取2个节点,边数是66,所以总得节点数是12+1=13
在大学没有那么优秀的经历怎么办
这题默认的是无向图。 若可以是有向图,10个顶点就可以了
因为是非连通图,所以最少有一个结点没有连通,故在原有的边结点上,加一个结点。
非连通图, 在原来12个节点的连通图基础上加上一个人节点。则为所求、、
因为G为非连通图,所以G中至少含有两个连通子图,由于题目问至少有几个顶点,而且该图不含自回路和多重边,所以一个连通图可看成是一个点构成,另一个连通图可看成是一个完全图(因为完全图在最少顶点的情况下能得到的边数最多),这样该问题转化为这个36条边的完全图有多少个顶点,由公式可知:66=n×(n-1)/2,则n=12,加上另一个连通图(只有一个点),则图G至少有13个顶点.
连通图n=e*(e-1)/2 e=12 非连通则加1
n个结点的 非连通图的边数 = n-1个结点的连通图的边数。C(12,2) = 66,所以n = 13。
北京有一条1公里长的街道,你认为一天能收多少钱的停车费?
什么是 Cookie?它的作用是什么?
解释一下TCP的滑动窗口。
微信公众号中服务号和订阅号合二为一,你怎么看?
在大学没有那么优秀的经历怎么办
这题默认的是无向图。 若可以是有向图,10个顶点就可以了
因为是非连通图,所以最少有一个结点没有连通,故在原有的边结点上,加一个结点。
非连通图, 在原来12个节点的连通图基础上加上一个人节点。则为所求、、
因为G为非连通图,所以G中至少含有两个连通子图,由于题目问至少有几个顶点,而且该图不含自回路和多重边,所以一个连通图可看成是一个点构成,另一个连通图可看成是一个完全图(因为完全图在最少顶点的情况下能得到的边数最多),这样该问题转化为这个36条边的完全图有多少个顶点,由公式可知:66=n×(n-1)/2,则n=12,加上另一个连通图(只有一个点),则图G至少有13个顶点.
连通图n=e*(e-1)/2 e=12 非连通则加1
n个结点的 非连通图的边数 = n-1个结点的连通图的边数。
C(12,2) = 66,所以n = 13。