.拓扑排序算法仅能适用于有向无环图。( )【南京航空航天大学 一、( 分)】
&无环有向图才能进行拓扑排序。( )【青岛大学 一、( 分)一、
( 分)】
&有环图也能进行拓扑排序。( )【青岛大学 四、( 分)】
.拓扑排序的有向图中,最多存在一条环路。( )【大连海事大学 一、(
分)】
.任何有向图的结点都可以排成拓扑排序,而且拓扑序列不唯一。( )【上海交通大
学 一、】
&既使有向无环图的拓扑序列唯一,也不能唯一确定该图。( )【合肥工业大学
二、( 分)】
.若一个有向图的邻接矩阵对角线以下元素均为零,则该图的拓扑有序序列必定存在。
( )
【中科院软件所 一、( 分)】
. 网的含义是以边表示活动的网。( )【南京航空航天大学 五、(
分)】
.对一个 网,从源点到终点的路径最长的路径称作关键路径。【南京航空航天大
学 五、 分)】
&关键路径是 网中从源点到终点的最长路径。( )【青岛大学 四、
( 分)】
& 网一定是有向无环图。( )【青岛大学 一、( 分)】
&在表示某工程的 网中,加速其关键路径上的任意关键活动均可缩短整个工程的完
成时间。( )
【长沙铁道学院 一、 分】
.在 图中,关键路径上某个活动的时间缩短,整个工程的时间也就必定缩短。(
)
【大连海事大学 一、( 分)】
.在 图中,关键路径上活动的时间延长多少,整个工程的时间也就随之延长多少。
( )
【大连海事大学 一、( 分)】
.当改变网上某一关键路径上任一关键活动后,必将产生不同的关键路径。【上海交通
大学 一、】
三、填空题
&判断一个无向图是一棵树的条件是777777。
.有向图 ' 的强连通分量是指777777。【北京科技大学 一、】
.一个连通图的777777是一个极小连通子图。【重庆大学 一、】
.具有 个顶点的无向图,边的总数最多为777777。【华中理工大学 一、
( 分)】
.若用 表示图中顶点数目,则有7777777条边的无向图成为完全图。【燕山大学
一、( 分)】
&设无向图 '有 个顶点和 /条边,每个顶点 #的度为 .#(<(#<(〉,则
/(777777
【福州大学 二、 分】
.' 是一个非连通无向图,共有 条边,则该图至少有777777个顶点。