割边 定义设无向图G〈V,E)为连通的,若有边集E1是E 的真子集,使得图G删除了E1所有边后,所得的子 图是不连通的,而删除了E1的任意真子集后,所得 的子图仍然是连通图。则称集合E1为图G的边割集 若某一边构成边割集,则称该边为割边(或桥)。 G的割边也就是G中的一条边e使得W(G-e) W(G)。与点连通度相似,我们定义非平凡图G的边 连通度为:A(G=mi{E1E1是G的边割集},边连 通度λ(G是为了产生一个不连通需要删去边的最少 数目。对于平凡图A(G)=0,此外一个不连通图也有 A(G)=0。 Guoyongfang.2006@yahoo.com.cn
Guoyongfang.2006@yahoo.com.cn 定义 设无向图G=〈V,E〉为连通的，若有边集E1是E 的真子集，使得图G删除了E1所有边后，所得的子 图是不连通的，而删除了E1的任意真子集后，所得 的子图仍然是连通图。则称集合E1为图G的边割集。 若某一边构成边割集，则称该边为割边(或桥)。 G的割边也就是G中的一条边e使得W(G-e)＞ W(G)。与点连通度相似，我们定义非平凡图G的边 连通度为：λ(G)=min{| E1 ||E1是G的边割集}，边连 通度λ(G)是为了产生一个不连通需要删去边的最少 数目。对于平凡图λ(G)=0，此外一个不连通图也有 λ(G)=0。 割边
定理 定理对于任何一个图G=〈V,E〉,有 k(G≤凵(G≤6(G 证明若G不连通,则k=(O=0,故上式成立。 若G连通, ①证明4(≤6(。若G是平凡图,则A(O=0≤6(G,若 G是非平凡图,则因每一结点的所有关连边必含 个边割集,故凵(G≤6(G。 Guoyongfang.2006@yahoo.com.cn
Guoyongfang.2006@yahoo.com.cn 定理 对于任何一个图G =〈V,E〉，有 k(G)≤λ(G)≤δ(G) 证明 若G不连通，则k(G)=λ(G)=0，故上式成立。 若G连通， ①证明λ(G)≤δ(G)。若G是平凡图，则λ(G)=0≤δ(G)，若 G是非平凡图，则因每一结点的所有关连边必含一 个边割集，故λ(G)≤δ(G)。 定理
续 ②再证和G 设耳G=1,即G有一割边,显然此时利G=1,上式 成立。 设型G≥2,则必可删去某G条边,使G不连通,而 删除-1条边,它仍然连通,而且有一条桥e=( U。对G)-1条边中每一条边都选取一个不同于u U的端点,将这些端点删去必至少删去G)-1条边 若这样产生的图是不连通的,则刈≤G)-1≤, 若这样产生的图是连通的,则e=(U,训仍然是桥, 此时再删去u,υ,就必产生一个不连通图,故 K(G≤A(G。 由此得k(O)≤(O)≤6(G) Guoyongfang.2006@yahoo.com.cn
Guoyongfang.2006@yahoo.com.cn ②再证k(G)≤λ(G) .设λ(G)=1，即G有一割边，显然此时k(G)=1，上式 成立。 .设λ(G)≥2，则必可删去某λ(G)条边，使G不连通，而 删除λ(G)-1条边，它仍然连通，而且有一条桥e=(u， v)。对λ(G)-1条边中每一条边都选取一个不同于u， v的端点，将这些端点删去必至少删去λ(G)-1条边。 若这样产生的图是不连通的，则k(G)≤λ(G)-1≤λ(G)， 若这样产生的图是连通的，则e=(u，v)仍然是桥， 此时再删去u，v，就必产生一个不连通图，故 k(G)≤λ(G)。 由此得k(G)≤λ(G)≤δ(G)。 续：
定理 定理一个连通无向图G=〈VE〉的某一点U是 图G的割点的充分必要条件是存在两个结点L 和U,使得结点L和的每一个路都通过结点 Guoyongfang.2006@yahoo.com.cn
Guoyongfang.2006@yahoo.com.cn 定理 一个连通无向图G =〈V,E〉的某一点v是 图G的割点的充分必要条件是存在两个结点u 和w，使得结点u和w的每一个路都通过结点 v。 定理
有向图的连通性 、有向图的连通性 定义设G=<V,E>是一个有向图,对v;,v;∈V,从 V:到v如存在一条路,则称结点v:到v是可达的。 在有向图中,如从v;到v:可达,但从v:到v则不一定是 可达的。 为此,若将可达性看成是图G=<V,E>的结点集 合V上的二元关系的话,对有向图来说,该可达性关 系仅是自反的、传递的关系,但不一定是对称的关系 也不一定是反对称的关系。 Guoyongfang.2006@yahoo.com.cn
Guoyongfang.2006@yahoo.com.cn 三、有向图的连通性 三、有向图的连通性 定义 设G＝<V，E>是一个有向图，对vi，vjV，从 vi到vj如存在一条路，则称结点vi到vj是可达的。 在有向图中，如从vi到vj可达，但从vj到vi则不一定是 可达的。 为此，若将可达性看成是图G＝<V，E>的结点集 合V上的二元关系的话，对有向图来说，该可达性关 系仅是自反的、传递的关系，但不一定是对称的关系、 也不一定是反对称的关系