V。,使得两个结点v;和k是连通的，当且仅当它们属手同一个V 我们把子图G(V,),G(W)称为图G的连通分支（图），今后我们把 图G的连通分支数记作(G)。 2、连通图 定义7-2.3：若图G只有一个连通分支，则称G是连通图 显然在连通图中，任意两个结点之间必是连通的。 对于连通图，常常由于删除了图中的点或边，而影响了图的连通性。 所谓在图中别除结点V,即是把ⅴ以及与ⅴ关联的边都删去：所谓在 图中删除某边，仅需把该边删去。 3、割点 定义7-2.4：设无向图G=<V,E>为连通图，若有点集VCV,使图C 中别除了V,中的所有边后得到的子图是不连通图，而别除了V,的任 一真子集后得到的子图是连通图，则称V是G的一个点割集。若某 个点构成一个点割集，则称该边为割点。 如282页图7-2.4(a)中的点就是割点。 点连通度：是为了产生一个不连通图需要删去的点的最少数目，也称 为连通度，记为k(G)。 即k(G)=minV,IV1是G的点割集 (1)若G是平凡图则V,=D,k(G)=0 (2)k(K)=n-1 (3)若图存在割点，则k(G)=1 (4)规定非连通图的连通度k(G)=0 4、割边 定义7-2.5：设无向图G=<W,E>为连通图，若有边集E1,使图G中 删除了E中的所有边后得到的子图是不连通图，而删除了E1的任 真子集后得到的子图是连通图，则称E是G的一个边割集。若某一个 边构成一个边割集，则称该边为割边（或桥）。 边连通度1(G)是为了产生一个不连通图需要删去的边的最小数目。即 11
11 V m ，使得两个结点 v j 和 v k 是连通的，当且仅当它们属手同一个 V i 。 我们把子图 G(V1 )，.，G(V m )称为图 G 的连通分支(图)，今后我们把 图 G 的连通分支数记作 W(G)。 2、连通图 定义 7-2.3：若图 G 只有一个连通分支，则称 G 是连通图。 显然在连通图中，任意两个结点之间必是连通的。 对于连通图，常常由于删除了图中的点或边，而影响了图的连通性。 所谓在图中删除结点 v，即是把 v 以及与 v 关联的边都删去；所谓在 图中删除某边，仅需把该边删去。 3、割点 定义 7-2.4：设无向图 G＝<V，E>为连通图，若有点集 V 1 V，使图 G 中删除了 V 1 中的所有边后得到的子图是不连通图，而删除了 V 1 的任 一真子集后得到的子图是连通图，则称 V 1 是 G 的一个点割集。若某一 个点构成一个点割集，则称该边为割点。 如 282 页图 7-2.4(a)中的点就是割点。 点连通度：是为了产生一个不连通图需要删去的点的最少数目，也称 为连通度，记为 k(G) 。 即 k(G)=min{|V1 ||V1 是 G 的点割集} (1)若 G 是平凡图则 V 1 =，k(G)=0 (2)k(K n )=n-1 (3)若图存在割点，则 k(G)=1 (4)规定非连通图的连通度 k(G)=0 4、割边 定义 7-2.5：设无向图 G＝<V，E>为连通图，若有边集 E 1，使图 G 中 删除了 E 1 中的所有边后得到的子图是不连通图，而删除了 E 1 的任一 真子集后得到的子图是连通图，则称 E 是 G 的一个边割集。若某一个 边构成一个边割集，则称该边为割边(或桥)。 边连通度 (G)是为了产生一个不连通图需要删去的边的最小数目。即
入(G)=minE,IlE1是G的边割集】 (1)若G是平凡图则E,=Φ，入.(G)=0 (2)若G存在割边，则(G)=1, (3)规定非连通图的边连通度为入(G)=0 在7-2.2节定义了图的最小度： 8(G)=min(deg(v),vEV) 5、点连通度、边连通度和图的最小度之间的关系 下面是由惠特尼(：.Whitney)于1932年得到的关于结点连通度k(G) 边连通度1(G)和最小度8(G)的不等式联系的定理： 5、定理7-2.2：对于任何一个图G,有k(G)≤(G)≤8(G) 282页图7-2.3(a) k(G)=1,1(G)=2,8(G)=2 282页图7-2.4 k(G)=1,1(G)=2,δ(G)=2 证明：若G不连通，则k(G)=元(G)=0,故上式成立。 若G连通， 1)正明，(G)≤8(G):如果G是平凡图，则)(G)=0≤8(G),若G是非平 凡图，则因每一结点的所有关联边必含一个边割集，（因 (G)=min{deg(w)veV},设ueV使的deg(u)=6(G),与u相关联的8 条边必包含一个边割集，至少这8条边删除使图不连通。)故入（©）≤ 8(G)。 2)再证k(G)≤1(G): (a)设入(G)=l,即G有一割边，显然这时k(G)=l,上式成立。 (6)设1(G)≥2，则必可删去某入(G)条边，使G不连通，而删去其中 (G)-1条边，它仍是连通的，且有一条桥e=(u,v)。对入(G)-1条边 中的每一条边都选取一个不同于山，ⅴ的端点，把这些端点删去则必至 少删去入(G)-1条边。若这样产生的图是不连通的，则k(G)≤ 入(G)-1<入(G),若这样产生的图是连通的，则e仍是桥，此时再删去u 或v就必产生一个不连通图，故k(G)≤入(G)。 6、定理7-2.3：一个连通无向图G中的结点v是割点的充分必要条件 是存在两个结点u和W,使得结点u和的每一条路都通过v。 三、有向图的连通性： 1、可达：在无向图G中，从结点u到v若存在一条路，则称结点u到 结点v是可达的。 可达性是有向图结点集上的二元关系，它是自反的、传递的，但一般 来说它不是对称的。因为在有向图中如u到v可达，未必v到u可达。 如果u可达v,它们之间可能不止一条路，在所有这些路中，最短路 12
12 (G)=min{|E1 ||E1 是 G 的边割集} (1)若 G 是平凡图则 E 1 =，(G)=0 (2)若 G 存在割边，则 (G)=1， (3)规定非连通图的边连通度为 (G)=0 在 7-2.2 节定义了图的最小度： δ(G)=min(deg(v)，vV) 5、点连通度、边连通度和图的最小度之间的关系 下面是由惠特尼(H.Whitney)于 1932 年得到的关于结点连通度 k(G)、 边连通度 (G)和最小度 (G)的不等式联系的定理： 5、定理 7-2.2：对于任何一个图 G，有 k(G)≤(G)≤(G) 282 页图 7- 2.3(a) k(G)=1,(G)=2,(G)=2 282 页图 7- 2. 4 k(G)=1,(G)=2,(G)=2 证明：若 G 不连通，则 k(G)=(G)=0，故上式成立。 若 G 连通， 1)证明 (G)≤(G)：如果 G 是平凡图，则 (G)=0≤(G)，若 G 是非平 凡 图 ， 则 因 每 一 结 点 的 所 有 关 联 边 必 含 一 个 边 割 集 ， ( 因 (G)=min{deg(v)|vV}，设 uV 使的 deg(u)=δ(G)，与 u 相关联的 条边必包含一个边割集，至少这 条边删除使图不连通。)故 (G)≤ (G)。 2)再证 k(G)≤(G)： (a)设 (G)=1，即 G 有一割边，显然这时 k(G)=l，上式成立。 (b)设 (G)≥2，则必可删去某 (G)条边，使 G 不连通，而删去其中 (G)-1 条边，它仍是连通的，且有一条桥 e=(u，v)。对 (G)-1 条边 中的每一条边都选取一个不同于 u，v 的端点，把这些端点删去则必至 少删去 (G)-1 条边。若这样产生的图是不连通的，则 k(G)≤ (G)-1<(G)，若这样产生的图是连通的，则 e 仍是桥，此时再删去 u 或 v 就必产生一个不连通图，故 k(G)≤(G)。 6、定理 7-2.3：一个连通无向图 G 中的结点 v 是割点的充分必要条件 是存在两个结点 u 和 w，使得结点 u 和 w 的每一条路都通过 v。 三、有向图的连通性： 1、可达：在无向图 G 中，从结点 u 到 v 若存在一条路，则称结点 u 到 结点 v 是可达的。 可达性是有向图结点集上的二元关系，它是自反的、传递的，但一般 来说它不是对称的。因为在有向图中如 u 到 v 可达，未必 v 到 u 可达。 如果 u 可达 v，它们之间可能不止一条路，在所有这些路中，最短路