结点v是简单连通图G的割点,当且仅当G中存在两个结点动v₁,v₂,使v₁到v₂的所有通路都经过结点v试证明之.

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

A.G中至少有一条路

B.G中至少有一条回路

C.G中有通过每个结点至少一次的路

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

设图G连通，并设S是N的非空真子集，证明边割是G的割集当且仅当点导出子图G[S]和都连通。

A、D中至少有一条通路

B、D中至少有一条回路

C、D中有通过每个结点至少一次的通路

D、D中有通过每个结点至少一次的回路

图2-36是带权的有向图G的邻接表。以结点V1出发深度遍历图G所得的结点序列为(1)；广度遍历图G所得的结点序列为(2)；G的一种拓扑序列是(3)；从结点V1到V8结点的最短路径是(4)；从结点V1到V8结点的关键路径是(5)。

A．V1，V2，V3，V4，V5，V6，V7，V8

B．V1，V2，V3，V8，V4，V5，V6，V7

C．V1，V2，V3，V8，V4，V5，V7，V6

D．V1，V2，V3，V8，V5，V7，V4，V6