题目内容
(请给出正确答案)
[主观题]
给定一个连通图G,所有边都没有附加权值。编写一个算法,求从顶点v能到达的最短路径长度为k的所有顶点。(最短路径长度以路径上的边数计算,找到一条即可)
给定一个连通图G,所有边都没有附加权值。编写一个算法,求从顶点v能到达的最短路径长度为k的所有顶点。(最短路径长度以路径上的边数计算,找到一条即可)
查看答案
如果结果不匹配,请 联系老师 获取答案
A.反转图中所有边的方向
B.按照设定条件取出子图
C.取两个图的公共顶点和边作为新图,并保持前一个图顶点与边的属性
D.合并边相同的属性
令G是一个至少有三个结点的连通图,下列命题是等价的。
a)G没有桥。
b)G的每两个结点在一条公共的闭迹上。
c)G的每一个结点和一条边在一条公共的闭迹上。
d)G是每两条边在一条公共的闭迹上。
e)对G的每一对结点和每一条边,有一条联结这两个结点而且含有这条边的迹。
f)对G的每一对结点和每一条边,有一条联结这两个结点而不含有这条边的通路。
g)对每三个结点,有一条联结任何两个结点而且含第三个结点的迹。
a)图7-21中的边能剖分为两条路(边不相重),试给出这样的剖分。
b)设G是一个具有k个奇数度结点(k>0)的连通图,证明在G中的边能剖分为k/2条路(边不相重)。
c)设G是一个具有k个奇数度结点的图,问最少加几条边到G中,而使所得的图有一条欧拉回路,说明对于图7-21如何能做到这一点。
d)在c)中如果只允许加平行于G中已存在的边,问最少加几条边到G中,使所得的图中有一条欧拉回路,这事总能做到吗?叙述能做到这事的充分必要条件。
设G是恰合2k(k2≥1)个奇度顶点的无向连通图,证明G中存在k条边不重的简单通路使得
已知无向图G既有割点又有桥,试确定G的点连通度和边连通度λ(G)。由已知条件能确定G的最小度δ(G)吗?