高教_离散数学耿素云+屈婉玲图论部分

本章的主要内容图及相关的诸多概念通路与回路图的连通性图的矩阵表示预备知识多重集合——元素可以重复出现的集合无序集——AB={(x,y)|xAyB}第十四章图的基本概念一、无向图与有向图的定义1．无向图的定义定义14.1无向图G=V,E,其中（1）V为顶点集，元素称为顶点（2）E为VV的多重集，其元素称为无向边，简称边设V={v2,v2,…,v5},E={(v1,v1),(v1,v2),(v2,v3),(v2,v3),(v2,v5),(v1,v5),(v4,v5)}则G=V,E为一无向图，用图1表示G第一节图图12.有向图的定义定义14.2有向图D=V,E,只需注意E是VV的多重子集图2表示的是一个有向图，试写出它的V和E图2注意：图的数学定义与图形表示，在同构（待叙）的意义下是一一对应的3．关于无向图和有向图诸多定义或表示（1）图①可用G泛指图（无向的或有向的）②V(G),E(G),V(D),E(D)③n阶图（2）有限图（3）n阶零图与平凡图（4）空图——（5）用ek表示无向边或有向边（6）顶点与边的关联关系①关联、关联次数②环③孤立点（7）顶点之间的相邻与邻接关系（8）邻域与关联集①vV(G)(G为无向图)}{)()(})(),()(|{)(vvNvNvvuGEvuGVuuvNv的闭邻域的邻域v的关联集})(|{)(关联与veGEeevI②vV(D)(D为有向图)}{)()()()()(})(,)(|{)(})(,)(|{)(vvNvNvvvvNvvuDEvuDVuuvvvuDEuvDVuuvvDDDDDDD的闭邻域的邻域的先驱元集的后继元集（9）标定图与非标定图（10）基图二、多重图与简单图定义14.3（1）无向图中的平行边及重数（2）有向图中的平行边及重数（注意方向性）（3）多重图（4）简单图在定义14.3中定义的简单图是极其重要的概念三、顶点的度数及握手定理1．顶点的度数（度）定义14.4及衍生的概念（1）设G=V,E为无向图,vV,d(v)——v的度数,简称度（2）设D=V,E为有向图,vV,d+(v)——v的出度d(v)——v的入度d(v)——v的度或度数（3）(G),(G)（4）+(D),+(D),(D),(D),(D),(D)（5）奇顶点度与偶度顶点2.图论基本定理——握手定理定理14.1设G=V,E为任意无向图，V={v1,v2,…,vn},|E|=m,则证G中每条边（包括环）均有两个端点，所以在计算G中各顶点度数之和时，每条边均提供2度，当然m条边共提供2m度.定理14.2设D=V,E为任意有向图，V={v1,v2,…,vn},|E|=m,则本定理的证明类似于定理14.1mvdnii2)(1mvdvdmvdniiniinii111)()(,2)(且推论任何图（无向的或有向的）中，奇度顶点的个数是偶数.证设G=V,E为任意图，令V1={v|vVd(v)为奇数}V2={v|vVd(v)为偶数}则V1V2=V,V1V2=，由握手定理可知由于2m,2)(Vvvd均为偶数，所以1)(Vvvd为偶数，但因为V1中顶点度数为奇数，所以|V1|必为偶数.握手定理为图论中最重要的定理，因而必须牢记它的内容并且会应用它.VvVvVvvdvdvdm21)()()(23.图的度数列（1）V={v1,v2,…,vn}为无向图G的顶点集，称d(v1),d(v2),…,d(vn)为G的度数列（2）V={v1,v2,…,vn}为无向图D的顶点集，D的度数列：d(v1),d(v2),…,d(vn)D的出度列：d+(v1),d+(v2),…,d+(vn)D的入度列：d(v1),d(v2),…,d(vn)（3）非负整数列d=(d1,d2,…,dn)是可图化的，是可简单图化的.易知：(2,4,6,8,10)，(1,3,3,3,4)是可图化的，后者又是可简单图化的（为什么？），而(2,2,3,4,5)，(3,3,3,4)都不是可简单图化的，特别是后者也不是可图化的（为什么？）四、图的同构定义14.5设G1=V1,E1,G2=V2,E2为两个无向图（两个有向图），若存在双射函数f：V1V2,对于vi,vjV1,(vi,vj)E1（vi,vjE1）当且仅当(f(vi),f(vj))E2（f(vi),f(vj)E2），并且,(vi,vj)（vi,vj）与(f(vi),f(vj))（f(vi),f(vj)）的重数相同，则称G1与G2是同构的，记作G1G2.几点说明：图之间的同构关系具有自反性、对称性和传递性.能找到多条同构的必要条件，但它们全不是充分条件：①边数相同，顶点数相同②度数列相同③对应顶点的关联集及邻域的元素个数相同，等等若破坏必要条件，则两图不同构判断两个图同构是个难题试画出4阶3条边的所有非同构的无向简单图（答案为3个）（1）（2）（3）（4）图3图3中，（1）与（2）不同构（度数列不同），（3）与（4）也不同构.（1）（2）图4图4中（1）与（2）的度数列相同，它们同构吗？为什么？五、完全图与竞赛图1．定义14.6（1）n(n1)阶无向完全图——每个顶点与其余顶点均相邻的无向简单图.简单性质：边数1,2)1(nnnm（2）n(n1)阶有向完全图——每对顶点之间均有两条方向相反的有向边的有向简单图.简单性质：1),1(2),1(nnnnm（3）n(n1)阶竞赛图——基图为Kn的有向简单图.简单性质：边数1,2)1(nnnm图5中，（1）为K5，（2）为3阶有向完全图，（3）为4阶竞赛图.图5六、正则图定义14.7n阶k正则图——==k的无向简单图简单性质：边数2nkm（由握手定理得）Kn是n1正则图，彼得松图（见书上图14.3（1）所示，记住它）七、子图定义14.8G=V,E,G=V,E（1）GG——G为G的子图，G为G的母图（2）若GG且V=V，则称G为G的生成子图（3）若VV或EE，称G为G的真子图（4）V（VV且V）的导出子图，记作G[V]（5）E（EE且E）的导出子图，记作G[E]例画出K4的所有非同构的生成子图图6八、补图定义14.9设G=V,E为n阶无向简单图，以V为顶点集，以所有使G成为完全图Kn的添加边组成的集合为边集的图，称为G的补图，记作G.若GG,则称G是自补图.相对于K4,求图6中所有图的补图，并指出哪些是自补图.问：互为自补图的两个图的边数有何关系？一、通路与回路的定义定义14.11给定图G=V,E（无向或有向的），G中顶点与边的交替序列=v0e1v1e2…elvl，vi1,vi是ei的端点.（1）通路与回路：为通路；若v0=vl，为回路，l为回路长度.（2）简单通路与回路：所有边各异，为简单通路，又若v0=vl，为简单回路（3）初级通路（路径）与初级回路（圈）：中所有顶点各异，则称为初级通路（路径），又若除v0=vl，所有的顶点各不相同且所有的边各异，则称为初级回路（圈）（4）复杂通路与回路：有边重复出现第二节通路与回路几点说明表示法①定义表示法②只用边表示法③只用顶点表示法（在简单图中）④混合表示法环（长为1的圈）的长度为1，两条平行边构成的圈长度为2，无向简单图中，圈长3，有向简单图中圈的长度2.不同的圈（以长度3的为例）①定义意义下无向图：图中长度为l（l3）的圈，定义意义下为2l个有向图：图中长度为l（l3）的圈，定义意义下为l个②同构意义下：长度相同的圈均为1个试讨论l=3和l=4的情况二、图中通路与回路的长度的讨论定理14.5在n阶图G中，若从顶点vi到vj（vivj）存在通路，则从vi到vj存在长度小于或等于n1的通路.推论在n阶图G中，若从顶点vi到vj（vivj）存在通路，则从vi到vj存在长度小于或等于n1的初级通路（路径）.定理14.6在一个n阶图G中，若存在vi到自身的回路，则一定存在vi到自身长度小于或等于n的回路.推论在一个n阶图G中，若存在vi到自身的简单回路，则一定存在长度小于或等于n的初级回路.一、无向图的连通性与连通度1．无向图的连通性（1）顶点之间的连通关系：G=V,E为无向图①若vi与vj之间有通路，则vivj②是V上的等价关系R={u,v|u,vV且uv}（2）G的连通性与连通分支①若u,vV，uv，则称G连通②V/R={V1,V2,…,Vk}，称G[V1],G[V2],…,G[Vk]为连通分支，其个数p(G)=k（k1）；k=1，G连通第三节图的连通性（3）短程线与距离①u与v之间的短程线：uv，u与v之间长度最短的通路②u与v之间的距离：d(u,v)——短程线的长度③d(u,v)的性质：d(u,v)0,u≁v时d(u,v)=d(u,v)=d(v,u)d(u,v)+d(v,w)d(u,w)2.无向图的连通度（1）删除顶点及删除边①Gv——从G中将v及关联的边去掉②GV——从G中删除V中所有的顶点③Ge——将e从G中去掉④GE——删除E中所有边（2）点割集与边割集①点割集与割点定义14.16G=V,E,VVV为点割集——p(GV)p(G)且有极小性v为割点——{v}为点割集图7图7中，{v1,v4}，{v6}是点割集，v6是割点.{v2,v5}是点割集吗？②边割集与割边定义14.17G=V,E,EEE是边割集——p(GE)p(G)且有极小性e是割边（桥）——{e}为边割集在图7中，{e1,e2}，{e1,e3,e5,e6}，{e8}等是边割集，e8是桥，{e7,e9,e5,e6}是边割集吗？几点说明：Kn中无点割集Nn中既无点割集，也无边割集，其中Nn为n阶零图若G连通，E为边割集，则p(GE)=2若G连通，V为点割集，则p(GV)2（3）点连通度与边连通度①点连通度定义14.18G为连通非完全图点连通度—(G)=min{|V|V为点割集}规定(Kn)=n1若G非连通，(G)=0若(G)k，则称G为k-连通图易知，图7中图，=1，它只能是1-连通图②边连通度定义14.19设G为连通图边连通度——(G)=min{|E|E为边割集}若G非连通，则(G)=0若(G)r，则称G是r边-连通图易知，图7中图，=1，它只能是1边-连通图几点说明(Kn)=(Kn)=n1G非连通，则==0若G中有割点，则=1，若有桥，则=1若(G)=k,则G是1-连通图，2-连通图，…，k-连通图，但不是(k+s)-连通图，s1若(G)=r,则G是1-边连通图，2-边连通图，…，r-边连通图，但不是(r+s)-边连通图，s1（4）,,之间的关系.定理7.5(G)(G)(G)请画出一个的无向简单图二、有向图的连通性1．有向图顶点之间的可达关系（1）定义与性质①定义定义14.20D=V,E为有向图vivj（vi可达vj）——vi到vj有通路vivj（vi与vj相互可达）②性质具有自反性（vivi），传递性具有自反性、对称性、传递性（2）vi到vj的短程线与距离类似于无向图中，只需注意距离表示法的不同（无向图中d(vi,vj)，有向图中dvi,vj）及dvi,vj无对称性2．有向图的连通性及分类（1）定义定义14.22D=V,E为有向图①D弱连通（连通）——基图为无向连通图②D单向连通——vi,vjV，vivj或vjvi③D强连通——vi,vjV，vivj易知，强连通单向连通弱连通（2）判别法①强连通判别法定理14.8D强连通