必考题

考点

数据结构-图-图的属性

面5笔5

一个n个顶点的连通无向图，其边的个数至少为___。

A.n+1

B.n-1

C.n

D.nlogn

前往“校招VIP”小程序，刷题更快

最新校招难题刷题，快来进刷题群吧

解答

正确答案是 B

直接n=2,两个顶点一条边，代入就是只有n-1符合。故选B

评论

企鹅哥哥

2018-10-13 11:16:44

无向图G=<E,V> 边的数目大于等于顶点数目减1. 可以举个例子，当只有两点时候，只有一条边

0 0

柠檬很甜

2018-10-13 11:16:35

看错了==，

0 0

繁星知晓

2018-10-13 11:16:29

n个顶点的连通图至少有n-1条边，再少就不连通了，连通是指任意两个顶点之间都有路径，而不要求都有边相连．有路径是指从一个顶点沿着某些边可以到达另一个顶点．

0 0

碎梦不是梦碎

2018-10-13 11:16:22

最小生成树就是最小的连通图

0 0