图的连通性.doc

图的连通性图的连通性2010-07-23 21：02图的连通性第十三章图的基本概念第三节图的连通性一.连通性概念图中两点的连通：如果在图G中u、v两点有路相通，则称顶点u、v在图G中连通。连通图(connected graph)：图G中任二顶点都连通。图的连通分支(connected brch,component)：若图G的顶点集V(G)可划分为若干非空子集V 1,V 2,V w,使得两顶点属于同一子集当且仅当它们在G中连通，则称每个子图G为图G的一个连通分支(i=1,2,w)。注：(1)图G的连通分支是G的一个极大连通子图。(2)图G连通当且仅当w=1。例13.5设有2n个电话交换台，每个台与至少n个台有直通线路，则该交换系统中任二台均可实现通话。证明：构造图G如下：以交换台作为顶点，两顶点间连边当且仅当对应的两台间有直通线路。问题化为：已知图G有2n个顶点，且(G)n，求证G连通。事实上，假如G不连通，则至少有一个连通分支的顶点数不超过n。在此连通分支中，顶点的度至多是n 1。这与(G)n矛盾。证毕。例13.6若图中只有两个奇度顶点，则它们必连通。证明：用反证法。假如u与v不连通，则它们必分属于不同的连通分支。将每个分支看成一个图时，其中只有一个奇度顶点。这与推论13.1矛盾。证毕。在连通图中，连通的程度也有高有低。例如后面将定义一种参数来度量连通图连通程度的高低。二.割点定义13.2设vV(G)，如果w(G v)w(G)，则称v为G的一个割点。(该定义与某些著作有所不同，主要是在有环边的顶点是否算作割点上有区别)。例如定理13.3如果点v是图G的一个割点，则边集E(G)可划分为两个非空子集E 1和E 2，使得GE 1和GE 2恰好有一个公共顶点v。推论13.2对连通图G，顶点v是G的割点当且仅当G v不连通。以上两个结论的证明留作习题。三.顶点割集定义13.3对图G，若V(G)的子集V使得w(G V)w(G),则称V为图G的一个顶点割集。含有k个顶点的顶点割集称为k-顶点割集。注：(1)割点是1-顶点割集。(2)完全图没有顶点割集。四.连通度k(G)=min|V|V是G的顶点割集称为图G的连通度。完全图的连通度定义为k(Kv)=v 1。空图的连通度定义为0。注：(1)使得|V|=k(G)的顶点割集V称为G的最小顶点割集。(2)若k(G)k，则称G为k连通的。(3)若G不连通，则k(G)=0。(4)若G是平凡图，则k(G)=0。(5)所有非平凡连通图都是1连通的。例如五.割边定义13.4设eE(G)，如果w(G e)w(G)，则称e为G的一条割边。定理13.4边e是G的割边当且仅当e不在G的任何圈中。证明：证其逆否命题：e不是割边当且仅当e含在G的某个圈中.必要性：设e=xy不是割边。假定e含在G的某个连通分支G 1中，则G 1 e仍连通。故在G 1 e中有(x,y)路P，P+e便构成G 1中一个含有e的圈。充分性：设e含在G的某个圈C中，而C含于某连通分支G 1中，则G 1 e仍连通。故w(G e)=w(G)，这说明e不是割边。证毕。六.边割集定义13.5对图G，若E(G)的子集E使得w(G E)w(G)，则称E为图G的一个边割集。含有k条边的边割集称为k-边割集。注：(1)对非平凡图G，若E是一个边割集，则G E不连通。(2)一条割边构成一个1-边割集。(3)设S V(G),SV(G),S,S，记号S,S表示一端在S中另一端S在中的所有边的集合。对图G的每个边割集E，必存在非空的S V(G),使得是G的一个边割集，其中。七.边连通度称为图G的边连通度。完全图的边连通度定义为k(K v)=v-1。空图的边连通度定义为0。注：(1)对平凡图或不连通图G，k(G)=0。(2)若图G是含有割边的连通图，则k(G)=1。(3)若k(G)k，则称G为k-边连通的。(4)所有非平凡连通图都是1-边连通的。(5)使得|E|=k(G)的边割集称为G的最小边割集。定理13.5 k(G)k(G)(G)。证明：先证k(G)k(G)。若G不连通，则k(G)=k(G)=0。若G是完全图，则k(G)=k(G)=n 1。下设G连通但不是完全图。则G有边割集含有k(1kv-1)条边。设这个边割集为E。对E中每条边，选取一个端点，去掉这些端点(至多个k)后，G便成为不连通图，故这些端点构成一个点割集V，|V|k。因此k(G)|V|k(G)。再证k(G)(G)。设d(v)=。删去与v关联的条边后，G变成不连通图，故这条边构成G的一个边割集。因此k(G)(G)。证毕。例13.8见教材280页例13.7.八.有向图的连通性定义13.6设D=V,E为一个有向图。对,V(D)，若从到存在有向通路，则称到是可达的。定义13.7设D=V,E为一个有向图。若D的基础图(即D的各弧去掉方向后所得无向图)是连通图，则称D是弱连通图；若对D中任意两点u和v，要么u到v可达，要么v到u可达，则称D是单向连通的；若对D中任意两点u和v，u与v之间都是相互可达的，则称D是双向连通的(强连通的)。例如：在下列图中，(a)是强连通的，(b)是单向连通的，(c)是弱连通的。注：按照定义，强连通图一定是单连通的，单连通图一定是弱连通的。定理13.6设有向图D=V,E，V=,。D是强连通图当且仅当D中存在经过每个顶点至少一次的回路。证：充分性显然。下证必要性。由于D是强连通的，故对i=1,2,n-1