A、图的一棵最小生成树的代价不一定比该图其他任何一棵生成树的代价小
B、带权连通图的最小生成树可能不唯一,但权值最小的边一定出现在解中
C、若带权连通图上各边上的权值互不相同,则该图的最小生成树是唯一的
D、一个带权连通图的最小生成树的权值之和不是唯一的
在一个有n个顶点的带权连通图中,有条边,则应该选用()算法来求这个图的最小生成树,从而使计算时间较少,
A、Prim
B、Kruskal
A.图中若不存在圈,则可能是已经得到最小支撑树
B.图中若不存在圈,则可能是网络不存在最小支撑树
C.其中一个步骤就是在网络图中寻找圈
D.去掉该圈中权数最小的边
下面是求无向连通图的最小生成树的一种算法:
//设图中总顶点数为n,总边数为m
将图中所有的边按其权值从大到小排序为;
若图不再连通,则恢复e1;(m=m+1);I=i+1;
(1)试间这个算法是否正确,并说明原因。
(2)以图8-44所示的图为例,写出执行以上算法的过程。
a)图7-21中的边能剖分为两条路(边不相重),试给出这样的剖分。
b)设G是一个具有k个奇数度结点(k>0)的连通图,证明在G中的边能剖分为k/2条路(边不相重)。
c)设G是一个具有k个奇数度结点的图,问最少加几条边到G中,而使所得的图有一条欧拉回路,说明对于图7-21如何能做到这一点。
d)在c)中如果只允许加平行于G中已存在的边,问最少加几条边到G中,使所得的图中有一条欧拉回路,这事总能做到吗?叙述能做到这事的充分必要条件。
令G是一个至少有三个结点的连通图,下列命题是等价的。
a)G没有桥。
b)G的每两个结点在一条公共的闭迹上。
c)G的每一个结点和一条边在一条公共的闭迹上。
d)G是每两条边在一条公共的闭迹上。
e)对G的每一对结点和每一条边,有一条联结这两个结点而且含有这条边的迹。
f)对G的每一对结点和每一条边,有一条联结这两个结点而不含有这条边的通路。
g)对每三个结点,有一条联结任何两个结点而且含第三个结点的迹。