设G=(V，E)是连通无向图,则(1)去掉G中任意简单回路C上的一条边e得到的图G-e连通。(2)去掉度数为1的节点V得到的图G-v连通。

A.简单图

B.连通图

C.不连通图

D.多重图

若AOE网络的每一项活动都是关键活动。令G是将该网络的边去掉方向和权后得到的无向图。

(1)如果图中有一条边处于从开始顶点到完成顶点的每一条路径上，则仅加速该边表示的活动就能减少整个工程的工期。这样的边称为桥(bridge)。证明若从连通图中删去桥，将把图分割成两个连通分量。

(2)编写一个时间复杂度为O(n+e)的使用邻接表表示的算法，判断连通图G中是否有桥，若有。输出这样的桥。

给定简单无向图G=，且|V|=n，|E|＞(1/2)(n-1)(n-2)，试证G是连通图。试给出|V|=n，|E|=(1/2)(n-1)(n-2)的简单无向图G=是不连通的例子。

设|V|=n(n＞1)，当且仅当______，G=＜V，E＞是强连通图。

A．G中至少有一条路

B．G中至少有一条回路

C．G中有通过每个节点至少一次的路

D．G中有通过每个节点至少一次的回路

树去掉任意一条边则不连通()

设G为n个结点的无向简单图,若x(G)≥k,则称G是k-连通图,k为非负整数.证明以下结论:

(1)当时,正明G连通.

(2)当时,证明G是k-连通图.

设G=(V，E)是简单无向连通图，但不是完全图．证明G中必存在三个结点u，v，ω∈V，使得(u，v)，(v，ω)∈E，但(u，ω)

A.3

B.5

C.7

D.9

设G是恰含2k(k≥1)个奇度顶点的无向连通图。证明：G中存在k条边不重的简单通路使得

设G是恰合2k(k₂≥1)个奇度顶点的无向连通图,证明G中存在k条边不重的简单通路使得