必考题

小邪

2024-07-03 22:00:00

在大学没有那么优秀的经历怎么办

0 0

一零计划

2018-10-13 11:56:11

这题默认的是无向图。若可以是有向图，10个顶点就可以了

0 0

王王王

2018-10-13 11:55:50

因为是非连通图，所以最少有一个结点没有连通，故在原有的边结点上，加一个结点。

0 0

雨声敲敲

2018-10-13 11:55:42

非连通图，在原来12个节点的连通图基础上加上一个人节点。则为所求、、

0 0

碧海问舟

2018-10-13 11:55:10

一个关键的点在于，边数已经给定了，要问最少的顶点数？

则必须是边尽可能多，边在什么情况下最多，就是每两个顶点间都有一条边C（12，2）=66；由于这个图不连通，还需要额外加一个单独的顶点。

0 0

星辰大海

2018-10-13 11:54:36

因为G为非连通图，所以G中至少含有两个连通子图，由于题目问至少有几个顶点，而且该图不含自回路和多重边，所以一个连通图可看成是一个点构成，另一个连通图可看成是一个完全图（因为完全图在最少顶点的情况下能得到的边数最多），这样该问题转化为这个36条边的完全图有多少个顶点，由公式可知：66＝n×（n-1）/2，则n＝12，加上另一个连通图（只有一个点），则图G至少有13个顶点.

0 0

资深90后

2018-10-13 11:54:29

n个顶点的连通图至少有 n*(n-1)/2 条边

令 66 = n*(n-1)/2 ，n=12

题目问的是非联通图，所以至少是13个顶点

0 0

岁月长歌

2018-10-13 11:54:22

连通图n=e*（e-1）/2 e=12 非连通则加1

0 0

小小精灵

2018-10-13 11:54:01

n个结点的非连通图的边数 = n-1个结点的连通图的边数。
C(12,2) = 66，所以n = 13。

0 0