首页 > 建筑工程类考试

题目内容（请给出正确答案）

[主观题]

问题描述:给定有向图G=（V,E).设P是G的一个简单路（顶点不相交)的集合.如果V中每个顶点恰好在P的

问题描述:给定有向图G=(V,E).设P是G的一个简单路(顶点不相交)的集合.如果V中每个顶点恰好在P的条路上,则称P是G的一个路径覆盖.P中路径可以从V的任何一个项点开始,长度也是任意的,特别地,可以为0.G的最小路径覆盖是G的所含路径条数最少的路径覆盖.

设计一个有效算法求一个有向无环图G的最小路径覆盖.

[设V={1,2,...,n},如下构造网络G₁=(V1,E₁):

问题描述:给定有向图G=（V,E).设P是G的一个简单路（顶点不相交)的集合.如果V中每个顶点恰好在

每条边的容量均为1.求网络G₁的(x₀,y₀)最大流.]

算法设计:对于给定的有向无环图G,找出G的一个最小路径覆盖.

数据输入:由文件input.txt提供输入数据.文件第1行有2个正整数n和m.n是给定有向无环图G的顶点数,m是G的边数.接下来的m行,每行有2个正整数i和j,表示一条有向边(i,j).

结果输出:将最小路径覆盖输出到文件output.txt.从第1行开始,每行输出一条路径.文件的最后一行是最少路径数.

问题描述:给定有向图G=（V,E).设P是G的一个简单路（顶点不相交)的集合.如果V中每个顶点恰好在

查看答案

如果结果不匹配，请联系老师获取答案

您可能会需要：

重置密码查看订单联系客服

安装优题宝APP，拍照搜题省时又省心！

更多“问题描述:给定有向图G=（V,E).设P是G的一个简单路（顶…”相关的问题

第1题

设G=＜v，E)为无向简单图，|v|=n， Δ(G)为图G中结点的最大次数，请指出下面4个不等式中哪个是正确

设G=＜v，E)为无向简单图，|v|=n， Δ（G)为图G中结点的最大次数，请指出下面4个不等式中哪个是正确

的。

设G=＜v，E)为无向简单图，|v|=n， Δ（G)为图G中结点的最大次数，请指出下面4个不等式中哪

点击查看答案

第2题

设e=(u，v)为无向图G中一桥，证明：u是割点当且仅当u不是悬挂顶点。

设e=（u，v)为无向图G中一桥，证明：u是割点当且仅当u不是悬挂顶点。

点击查看答案

第3题

McCabe环路复杂度的计算可以通过()方法获得。

A.环路复杂性计算连通区法，靠计算有向退化图中的连通区的个数计算环路复杂度

B.判定条件计算法：从退化图中的判定个数计算环路复杂度。V(G)=判定条件个数+1

C.V(G)=m-n+1说明：V(G)为有向图G中环路复杂度;m为图G中弧数;n为图G中节点数

D.V(G)=m-n+p说明：V(G)为有向图G中环路复杂度;m为图G中弧数;n为图G中节点数;根据图论有向图G强连通分量p，添加图G中强连通分量后，p值为2

点击查看答案

第4题

问题描述:设计一个用回溯法搜索一般解空间的函数,参数包括:生成解空间中下一扩展结点的函数、

结点可行性判定函数和上界函数等必要的函数,并将此函数用于解图的m着色问题.

图的m着色问题描述如下:给定无向连通图G和m种不同的颜色.用这些颜色为图G的各顶点着色,每个顶点着一种颜色.如果有一种着色法,使G中每条边的2个顶点着不同颜色,则称这个图是m可着色的.图的m着色问题是对于给定图G和m种颜色,找出所有不同的着色法.

算法设计:对于给定的无向连通图G和m种不同的颜色,计算图的所有不同的着色法.

数据输入:由文件input.txt给出输入数据.第1行有3个正整数n,k和m,表示给定的图G有n个项点和k条边,m种颜色.顶点编号为1,2,...,n接下来的k行中,每行有2个正整数u、v,表示图G的一条边(u,v).

结果输出:将计算的不同的着色方案数输出到文件output.txt.

问题描述:设计一个用回溯法搜索一般解空间的函数,参数包括:生成解空间中下一扩展结点的函数、结点可行性

点击查看答案

第5题

证明定理15.8.定理15.8：设u,v为n阶无向图简单图G中两个不相邻的顶点,且d（u)+d（v)≥n,则G为哈密

证明定理15.8.

定理15.8：设u,v为n阶无向图简单图G中两个不相邻的顶点,且d(u)+d(v)≥n,则G为哈密顿图证明定理15.8.定理15.8：设u,v为n阶无向图简单图G中两个不相邻的顶点,且d（u)+d（v) GU(u,v)为哈密顿图((u,v)是加的新边.

点击查看答案

第6题

设G=（V，E)是一个简单图，（称δ（G)为G的最小次)。证明：（1)若δ（G)≥2，则G必有圈;（2)若δ（G)≥2，则G必有

设G=(V，E)是一个简单图，设G=（V，E)是一个简单图，（称δ（G)为G的最小次)。证明：（1)若δ（G)≥2，则G必有圈;（ (称δ(G)为G的最小次)。证明：(1)若δ(G)≥2，则G必有圈;

(2)若δ(G)≥2，则G必有包含至少δ(G)+1条边的圈。

点击查看答案

第7题

设简单图G所有顶点的度之和为12，则G一定有（)条边。

A.3

B.4

C.5

D.6

点击查看答案

第8题

G=＜V，E＞是无向连通图，若|V|=100，|E|=100，则从G中能找到______条回路．

点击查看答案

第9题

图论是应用数学的一个分支，它以图为研究对象，图一般用二维组G=（V，E）来描述。（）

点击查看答案

第10题

无向图G=（V，E)是（7，28)图（即n=7，m=28)，问G是简单图还是多重图？说明理由．

无向图G=(V，E)是(7，28)图(即n=7，m=28)，问G是简单图还是多重图？说明理由．

点击查看答案

第11题

已知一无向图G=（V,E)，其中V={a，b，c，d,e}E={（a，b)，（a，d)，（a，c)，（d,c)，（b，e)}现用某一种图遍历方法

已知一无向图G=(V,E)，其中V={a，b，c，d,e}E={(a，b)，(a，d)，(a，c)，(d,c)，(b，e)}现用某一种图遍历方法从顶点a开始遍历图，得到的序列为abecd，则采用的是__________遍历方法。【南京理工大学1996二、2(2分)】

点击查看答案

湖南优积谷网络科技有限公司版权所有 ©2024

湘ICP备16018319号-1 湘公安备案43019002000613号营业执照

违法和不良信息举报电话：400-118-7898

举报/反馈/投诉邮箱：deng＃ujigu.com（请将＃替换成@）