首页 > 试题广场 >

含n个顶点的连通图中的任意一条简单路径，其长度不可能超过（）

[单选题]

查看答案及解析

codersong

简单路劲就是指路径中不含有重复的节点，节点只经过一次，最长的路径肯定就说所有节点都走一次，也就是边的条数，就是n-1

发表于 2015-10-09 10:30:13 回复(1)

起名可真的是太难了

举具体的实例，如对于无向图1-2-3，显然是连通图，节点数n=3.针对路径1-3来比较题目给出的选项，已知路径1-3的长度为2.

对于A选项，n/3=1

对于B选项，n/2=1

对于C选项，为1

对于D选项，n-1=2

显然选D

发表于 2018-04-24 21:58:26 回复(2)

huixieqingchun

简单路径就是一条路径中无重复结点。

发表于 2016-05-08 16:21:38 回复(2)

Flowermoon

对于这个问题，可以假设u到v，其中有简单路径，那么肯定存在最短路径P。那么在P中，所有的点都不重复。如果P包含n个点，所有的点都不重复，构成的路长度为n-1。所以对于P中，存在的点是<=n的，所以它的长度也就是<=n-1，所以长度不可能超过n-1。

发表于 2022-12-19 22:21:30 回复(0)

JobsLee

一个无向图 G=(V,E) 是连通的，那么边的数目大于等于顶点的数目减一：|E|>=|V|-1，而反之不成立。

如果 G=(V,E) 是有向图，那么它是强连通图的必要条件是边的数目大于等于顶点的数目：|E|>=|V|，而反之不成立。

没有回路的无向图是连通的当且仅当它是树，即等价于：|E|=|V|-1。

发表于 2016-04-10 15:30:18 回复(1)

tutuqie

难道是两边之和大于第三边，三边之和大于第四边，四边之和。。。。。。？？？所以任何一边不可能大于其他变加起来，不然就重叠了，y or n。。。

发表于 2015-09-09 21:38:00 回复(2)

提交观点

问题信息

图

来自：C++入门级笔试题合集（二）

难度：

6条回答 173收藏 17797浏览

扫一扫，把题目装进口袋