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

设G=＜V，E＞为无向图，命题均有，则G中存在哈密顿通路”的真值为（)。

设G=＜V，E＞为无向图，命题均有，则G中存在哈密顿通路”的真值为()。

A.G'为G的子图

B.G'为G的连通分量

C.G'为G的极小连通子图且V'=V

D.G'是G的无环子图

设有无向图G=(v，E)和G’=(V’，E’)，如果G’是G的生成树，则下列不正确的是（）。 I,G’为G的连通分量 II,G’为G的无环子图 III,G’为G的极小连通子图且V’=V

A．I、II

B．只有III

C．II、III

D．只有I

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

设G=(V，E)是一个简单图，令

(称δ(G)为G的最小次)。证明：(1)若δ(G)≥2，则G必有圈；(2)若δ(G)≥2，则G必有包含至少δ(G)+1条边的圈。

本题给出二部图（bipartitegraph)的概念。设G=（V，E)是一类无向图，可以把它们的顶点划分为两个互

不相交的子集A和B=V-A，并且这两个子集具有下列性质：

(a)A中任何两个顶点在G中都不是相互邻接的;(b)B中任何两个顶点在G中都不是相互邻接的。例如，图8-34就是二部图。对V(G)的一个划分可能是A=(0，3，4，6)和B=(1，2，5，7).

(1)试编写一个算法，判断图G是否是二部图。如果图G是二部图，则你的算法应当把项点划分成为具有上述性质的两个互不相交的子集A和B。证明：当用邻接表表示图G时，这个算法的复杂度可以做到O(n+e)。其中n是图G的顶点个数，e是边数。

(2)证明：任何-棵树都是二部图

(3)证明：当且仅当图G不包含奇数条边的回路时.它是二部图。

E，否则，返回FALSE(注：本算法中可以调用以下几个函数：FIRSTADJ(G，V)——返回图G中顶点V的第一个邻接点的号码，若不存在，则返回0；NEXTADJ(G，W)——返回图G中顶点V的邻接点中处于W之后的邻接点的号码，若不存在，则返回0；NODES(G)——返回图G中的顶点数)。【合肥工业大学1999五、5(8分)】

无向图G=（V,E)的边连通度为k是指最少需要移去G的k条边才能使G成为不连通图.例如,树的边连通度为1;循环链的边连通度为2.试用网络最大流算法求给定图G的边连通度.