15、如图中从v至各点均有唯一的最短路,则连接v至其他各点后,恰好构成该图的最小支撑树。

题目

15、如图中从v至各点均有唯一的最短路,则连接v至其他各点后,恰好构成该图的最小支撑树。

相似考题

1.下面关于图(网)的叙述，正确的是( )。A．连通无向网的最小生成树中，顶点数恰好比边数多1B．若有向图是强连通的，则其边数至少是顶点数的2倍C．可以采用AOV网估算工程的工期D．关键路径是AOE网中源点至汇点的最短路径

2.点A(10,15,18),则该点对V面的距离为( )。A.10B.15C.18D.25

3.连通图的最小支撑树是唯一的()

4.连通图的各边权值均不相同，则该图的最小生成树是唯一的。()

更多“15、如图中从v至各点均有唯一的最短路,则连接v至其他各点后,恰好构成该图的最小支撑树。”相关问题

  • 第1题：

    阅读下列说明，回答问题l和问题2，将解答填入答题纸的对应栏内。

    【说明】

    现需在某城市中选择一个社区建一个大型超市，使该城市的其他社区到该超市的距离总和最小。用图模型表示该城市的地图，其中顶点表示社区，边表示社区间的路线，边上的权重表示该路线的长度。

    现设计一个算法来找到该大型超市的最佳位置：即在给定图中选择一个顶点，使该顶点到其他各顶点的最短路径之和最小。算法首先需要求出每个顶点到其他任一顶点的最短路径，即需要计算任意两个顶点之间的最短路径；然后对每个顶点，计算其他各顶点到该顶点的最短路径之和；最后，选择最短路径之和最小的顶点作为建大型超市的最佳位置。

    下面是求解该问题的伪代码，请填充其中空缺的(1)至(6)处。伪代码中的主要变量说明如下：

    W：权重矩阵

    n：图的顶点个数

    sP：最短路径权重之和数组，SP[i]表示顶点i到其他各顶点的最短路径权重之和，i从1到n

    rain_SP：最小的最短路径权重之和

    min_v：具有最小的最短路径权重之和的顶点

    i：循环控制变量

    j：循环控制变量

    k：循环控制变量

    LOCATE-SHOPPINGMALL(W，n)

    1 D(0)=W

    2 for(1)

    3 for i=1 t0 n

    4 for j=1 t0 n

    5

    6 (2)

    7 else

    8 (3)

    9 for i=1 to n

    10 sP[i] =O

    11 for j=1 to n

    12 (4)

    13 min sP=sP[1]

    14 (5)

    15 for i=2 t0 n

    16 if min sP>sP[i]

    17 min sP=sP[i]

    18 min V=i

    19 return (6)


    正确答案：(1) k=1 tO n (5)rain_v=1(6)min_v
    (1) k=1 tO n (5)rain_v=1(6)min_v

  • 第2题：

    如果一个图 G 从 V1 到各点的最短路是唯一的,则连接 V1 到各点的最短路,再去掉重复边, 得到的图即为最小支撑树。 ()

    此题为判断题(对，错)。


    正确答案:正确

  • 第3题：

    已知电路中A点的电位为5V，A、B两点间的电压UAB=—10V，则B点电位为（）V。

    A5

    B15

    C10

    D—15


    B
    略

  • 第4题：

    电路中两点的电位分别是V1=10V、V2=-5V，则1点对2点的电压是15V。


    正确答案:正确

  • 第5题：

    如电路中参考点的选择改变后，则（）

    • A、各点电位值不变
    • B、各点电位值都变
    • C、各点间电压都变
    • D、各点间电压部分不变

    正确答案:B

  • 第6题：

    从连通图中生成树，以下叙述（）正确。

    • A、任一连通图必有支撑树
    • B、任一连通图生成的支撑树必唯一
    • C、在支撑树中再增加一条边后必含圈
    • D、任一连通图生成的各个支撑树其边数必相同

    正确答案:A,C,D

  • 第7题：

    互在任一图G中，当点集V确定后，树图是G中边数最少的连通图。


    正确答案:正确

  • 第8题：

    流量图中从起点到终点的流量能力（）

    • A、等于该图各连线中最大的流量能力
    • B、大于该图各连线中最小的流量能力
    • C、小于该图各连线中最大流量能力
    • D、大于等于该图各连线中的最小流量能力

    正确答案:D

  • 第9题：

    若连通网络上各边的权值均不相同，则该图的最小生成树有（）棵。


    正确答案:1

  • 第10题：

    判断题
    求图的最小支撑树以及求图中一点到另一点的最短路问题，都可以归结为求解整数规划问题。
    A

    对

    B

    错


    正确答案： 对
    解析： 暂无解析

  • 第11题：

    单选题
    流量图中从起点到终点的流量能力（）
    A

    等于该图各连线中最大的流量能力

    B

    大于该图各连线中最小的流量能力

    C

    小于该图各连线中最大流量能力

    D

    大于等于该图各连线中的最小流量能力


    正确答案： C
    解析： 暂无解析

  • 第12题：

    单选题
    如电路中参考点的选择改变后，则（）
    A

    各点电位值不变

    B

    各点电位值都变

    C

    各点间电压都变

    D

    各点间电压部分不变


    正确答案： B
    解析： 暂无解析

  • 第13题：

    求图的最小支撑树以及求图中一点至另一点的最短路问题，都可以归结为求解整数规划问题。()


    参考答案：正确

  • 第14题：

    图 G 的最小支撑树中从 V1 到 Vn 的通路一定是图 G 从 V1 到 Vn 的最短路。 ()

    此题为判断题(对，错)。


    正确答案:错误

  • 第15题：

    树状管网水力计算，可分为干线和支线计算。所谓干线是指（）。

    • A、自配水点至最远用水户的沿途各管段的集合
    • B、自配水点至支线起点的沿途各管段的集合
    • C、自配水点至水压控制点的沿途各管段的集合
    • D、自配水点至调节构筑物的沿途各管段的集合

    正确答案:C

  • 第16题：

    同一电路中两点的电位分别是V1=10V、V2=-5V，则1点对2点的电压是15V。


    正确答案:正确

  • 第17题：

    求图的最小支撑树以及求图中一点到另一点的最短路问题，都可以归结为求解整数规划问题。


    正确答案:正确

  • 第18题：

    从带连数长度的连通图中生成的最小支撑树，叙述不正确的是（）

    • A、任一连通图生成的各个最小支撑树总长度必相等
    • B、任一连通图生成的各个最小支撑树连线数必相等
    • C、任一连通图中具有最短长度的连线必包含在生成的最小支撑树中
    • D、最小支撑树中可能包括连通图中的最长连线

    正确答案:C

  • 第19题：

    在任一图G中，当点集V确定后，树图是G中边数最少的连通图。（）


    正确答案:正确

  • 第20题：

    若把电路中原来为－3V的点改为电位的参考点，则其他各点的电位将（）

    • A、变高
    • B、变低
    • C、不变
    • D、不能确定

    正确答案:A

  • 第21题：

    若把电路中原来为6V的点改为电位的参考点，则其他各点的电位将（）。

    • A、降低
    • B、不变
    • C、升高

    正确答案:A

  • 第22题：

    多选题
    从连通图中生成树，以下叙述（）正确。
    A

    任一连通图必有支撑树

    B

    任一连通图生成的支撑树必唯一

    C

    在支撑树中再增加一条边后必含圈

    D

    任一连通图生成的各个支撑树其边数必相同


    正确答案： B,A
    解析： 暂无解析

  • 第23题：

    单选题
    树状管网水力计算，可分为干线和支线计算。所谓干线是指（）。
    A

    a、自配水点至最远用水户的沿途各管段的集合

    B

    b、自配水点至支线起点的沿途各管段的集合

    C

    c、自配水点至水压控制点的沿途各管段的集合

    D

    d、自配水点至调节构筑物的沿途各管段的集合


    正确答案： D
    解析： 暂无解析

  • 第24题：

    判断题
    求图的最小支撑树以及求图中一点至另一点的最短路问题，都可以归结为求解整数规划问题。
    A

    对

    B

    错


    正确答案： 错
    解析： 暂无解析

相关内容