●4,例(点连通度和边连通度的用处) n个顶点表示n个站,e条边表示铁路 或者电话线。 为了使η个站连接得“最好”,必须 构造一个具有个顶点e条边的连通图, 使其具有最大的点连通度和边连通度
4，例（点连通度和边连通度的用处） n个顶点表示n个站，e条边表示铁路 或者电话线。 为了使n个站连接得“最好”，必须 构造一个具有n个顶点e条边的连通图， 使其具有最大的点连通度和边连通度
5,定理111(点连通度,边连通度与最小顶 点度数的关系) 对任何一个图G,k(G)≤4(G)≤o(G)。 ●证明方法:分历治之
5，定理11.1（点连通度，边连通度与最小顶 点度数的关系） 对任何一个图G，k(G)(G)(G)。 证明方法：分而治之
●证明: ●(1)证明A(G)≤8(G)。 若G没有边,则(G)=G)=0; 否则,存在顶点v,d(v)=(G)。删除v的 所有关联边,得到的图必定不连通,所 以(G)≤G)
证明： （1）证明(G)(G)。 若G没有边，则(G)=(G)=0； 否则，存在顶点v，d(v)=(G)。删除v的 所有关联边，得到的图必定不连通，所 以(G)(G)
(2)证明kG)≤2(G)。 ●若G是不连通图或平凡图,则k(G)=G)=0 若G是连通图,取断集E=刈E(记E关 联于V,中的点集为V,关联于中的点集为V”, 分三种情况分析
（ 2）证明k(G)(G) 。 若 G是不连通图或平凡图，则k(G)= (G)=0 。 若 G是连通图，取断集 ，记 E’关 联于 V 1中的点集为 V’，关联于 中的点集为 V ” ， 分三种情况分析。 1 1 E' ( ),| '| ( ) EV V E G 1 | | V
●1)VV或V"中至少有一个非空。不失一般性, 设V1V≠,则GV不连通,于是有k(G|V|s E1=2(G成立。 ●2)-=1-=但 min(VIvID=1不失一般性,设=1, 则GV为平凡图。于是有k(G)≤E1=(G成立 3V1V=1V”=a,但miV山Z)≥>1,则从V和 中各取若干与E中边关联的顶点,这些顶点构成子 集V2,且使得∨-V2≠,-V2,V2中顶点关联E 中全部边,ⅣV2E1,那么G-V2不连通。于是 k(G)s|VsE|=4(G成立
1) V 1-V’或 中至少有一个非空。不失一般性， 设 V 1-V’，则G-V’不连通，于是有k(G) |V’| |E’|= (G)成立。 2) 但 不失一般性，设 =1 ， 则G-V 1为平凡图。于是有k(G) |V 1| |E’|= (G)成立。 3) V 1-V’= -V ” = ，但min(|V 1|, )>1，则从 V 1 和 中各取若干与 E’中边关联的顶点，这些顶点构成子 集 V2，且使得 V 1-V2， -V2， V2中顶点关联 E’ 中全部边，|V2| |E’|，那么G-V2不连通。于是 k(G) |V2| |E’|= (G)成立。 1 V V " 1 1 VV VV ' ", min(| |,| |) 1, V V 1 1 1 | | V V 1 1 | | V V1 V 1