若图G的顶点取自平面上的点，各顶点间均有联边且权重就是其间的欧氏距离，则G的最小支撑树亦称作

设G是一个用邻接表表示的连通无向图。对于G中某个顶点v，若从G中删去顶点v及与顶点v相关联的边后，G变成由两个或两个以上非空连通分量所组成的图，则称v是原来图G的一个关节顶点。如下图中，只有顶点4和顶点6是关节顶点，而其他顶点都不是关节顶点。试叙述寻找图G的所有关节顶点的算法，并用算法语言(Pascal或C)编写一个实现你所给出的算法的程序。【复旦大学1996八(20分)】

关于图，下列说法正确的是_________?

A 图的每一个顶点可以与多个其它顶点相关联，各顶点之间的关系是任意的。

B 图可以分为有向图和无向图。

C 在有向图中，顶点对(x，y)是有序的，称为从x到y的一条有向边，这里(x，y)与(y， x)是不同的两条边。

D 在无向图中，顶点对(x，y)是无序的，(x，y)和(y，x)是同一条边。

令G=(X，△，Y)为一个二分图。设有正整数p，使X的每一个顶点至少与p条边关联，并且Y的每一个顶点最多与p条边关联。试证明Y至少与X有同样多的顶点。

给定无向图G=，且C(x)={z|x∈V?(x=z或者x≠z且x与z由一链联结)}。证明：

①对任何结点x和y，有C(x)=C(y)或者C(x)∩C(y)=?。

②若C(x)∩C(y)=?，则不存在一条边，它联结C(x)的结点与C(y)的结点。

A、2

B、3

C、4

D、5

两点之间带箭头的联线称为()

A、边

B、弧

C、图

D、链

关联矩阵(incidence matrix)是描述和实现图算法的另一重要方式，对于含有n个顶点、e条边的图，对应的关联矩阵I[][]共有n行e列。在无向图中，对于任意的0≤i<n和0≤j<e，若第i个顶点与第j条边彼此关联，则定义I[[i][j]=1;否则，定义I[[i][j]=0。

a)关联矩阵与邻接矩阵有何联系?

b)有向图的关联矩阵应如何定义?

c)有向图的关联矩阵，与邻接矩阵又有何联系?

d)基于关联矩阵，可以解决哪些问题?试举一例。

构成骨盆出口平面界限，错误的为

A．前顶点为耻骨联合下缘

B．两边为趾骨降支

C．后顶点为骶尾关节

D．两边为骶结节韧带

E．共同底边为坐骨棘间径

两点之间不带箭头的联线称为()

A、边

B、弧

C、图

D、链