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

设G=(V,E)起简单连通无向图δ(G)=k≥1。

(1)若G中最长的路径的长度为1,则l≥k。

(2)对于任意的G中最长的路径为是连通图。

(3)举例说明,对于G中最长的轨迹(2)中结论不成立。

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

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

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

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

设简单图,其中

做出各图.试问:

(1)哪些图是有向图？哪些图是无向图？

(2)哪些是强连通图？哪些是单向连通图？哪些是弱连通图？

设图G_i=＜V,E＞(i=1，2，…，6)，其中

画出各图，试问：

(1)哪些图是有向图？哪些图是无向图？

(2)哪些是强连通图？哪些是单向连通图？哪些是弱连通图？