任取v∈v(G),令G=G-({vUN(v)。由归纳假设,存在G的一个独立集S,对 r(G)-S"中任何顶点,可从S中的某顶点出发,经过长度≤2的有向路到达它。 (1)若存在v∈S,使vv∈A(G),则N(v)中每个顶点可从v出发,经过长度≤2的有 向路到达(G中其它点都在G中,本来就长2路可达) (2)否则,对Vv∈S",wvAO),而且因N(v)∩S'=Φ 故vgA(G),因此在底图G中v与S中的点不相邻 此时S=S∪{v}满足定理的要求 N"(y) §8.3有向图的连通性 定义8.3.1设G是一个有向图 (1)若G的底图G是连通图,则称G是弱连通的。 (2)若对G的任二顶点u,v,要么存在有向路P(u,v),要么存在有向路P(v,u),则称G是单 连通的。 (3)若对G的任二顶点,v,既存在有向路P(u,v),又存在有向路P(v,l),则称G是强连通 的(或称双向连通的)。 注:易见,强连通→单连通→弱连通。 例 不连通 弱连通 单连通 强连通 定理831G是强连通有向图的充要条件是G的所有顶点在一个有向闭途径上。 证明:必要性:设G是强连通有向图,(G)={v12n2…,"},则存在有向路P(v1,"2) P("2n),…,P1(-,,),P(,n),于是UP即为含所有顶点的有向闭途径。 充分性:设G的顶点共处于一个有向闭途径C上,则对v,v∈V(G),在C上必有u到v 的一段有向路P(,v),也有v到u的一段有向路P(v,u),故G是强连通的。证毕 定理832无向图G可定向成强连通图的充分必要条件为:G中无割边(即G是2边连通图) 证明:必要性:用反证法。若G中有割边,则无论如何对G的各边定向,都无法使割边两 端的点在所形成的有向图中双向连通。这与G可定向成为强连通有向图矛盾。 充分性:设G无割边,则G中存在圈。取其一个圈C,记G1=C。给G1定向为顺时针方 向。若G1不是生成子图,则存在v∈(G)-(G1),由第二章 Menger定理,存在两条无3 任取 v VG ∈ ( ) G , 令 G G v Nv ({ } ( )) + ′ = − G G ∪ 。由归纳假设，存在 G′ G 的一个独立集 S′ ，对 VG S ( )′ ′ − G 中任何顶点，可从 S′中的某顶点出发，经过长度 ≤ 2 的有向路到达它。 (1) 若存在 0 v S ∈ ′ ，使 0 vv AG ∈ ( ) G ，则 N v( ) + 中每个顶点可从 0 v 出发，经过长度 ≤ 2 的有 向路到达（G G 中其它点都在G′ G 中，本来就长 2 路可达）。 (2) 否则，对 0 ∀ v S ∈ ′ ， 0 vv AG ∉ ( ) G ，而且因 Nv S ( ) + ∩ ′ = Φ ， 故 0 vv A G ∉ ( ) G ，因此在底图 G 中v S 与 ′中的点不相邻。 此时 SS v = ′∪{ }满足定理的要求。 证毕。 §8.3 有向图的连通性 定义 8.3.1 设G G 是一个有向图， (1) 若G G 的底图 G 是连通图，则称G G 是弱连通的。 (2) 若对G G 的任二顶点 u, v，要么存在有向路 P(u, v)，要么存在有向路 P(v, u)，则称G G 是单 连通的。 (3) 若对G G 的任二顶点 u, v，既存在有向路 P(u, v)，又存在有向路 P(v, u)，则称G G 是强连通 的（或称双向连通的）。 注：易见，强连通⇒单连通⇒弱连通。 例： 定理 8.3.1 G G 是强连通有向图的充要条件是G G 的所有顶点在一个有向闭途径上。 证明：必要性：设 G G 是强连通有向图， 1 2 VG vv v {, , , } = ν G （ ） " ，则存在有向路 112 Pv v ( , ), 223 Pv v (,) , ", -1 1 Pv v ( , ), νν ν − 1 Pv v (,) ν ν ，于是 1 i i P ν − ∪ 即为含所有顶点的有向闭途径。 充分性：设G G 的顶点共处于一个有向闭途径 C 上，则对∀ ∈ uv VG , () G ，在 C 上必有 u 到 v 的一段有向路 1Puv (,) ，也有 v 到 u 的一段有向路 1P vu (, ) ，故 G 是强连通的。证毕。 定理 8.3.2 无向图 G 可定向成强连通图的充分必要条件为：G 中无割边(即 G 是 2 边连通图)。 证明：必要性：用反证法。若 G 中有割边，则无论如何对 G 的各边定向，都无法使割边两 端的点在所形成的有向图中双向连通。这与 G 可定向成为强连通有向图矛盾。 充分性：设 G 无割边，则 G 中存在圈。取其一个圈 C，记G C 1 = 。给G1定向为顺时针方 向。若G1不是生成子图，则存在 1 1 v VG VG ∈ () ( ) − ，由第二章 Menger 定理，存在两条无 不连通 弱连通 单连通 强连通 S′ v0 N + (v) v