资源描述：
《离散数学复辅导之三.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、离散数学复习辅导之三第3章图的基本概念与性质一、重点内容1．图的基本概念h图是一个有序对，V是结点集，E是边集，当½V½,½E½有限时，称为有限图；否则称无限图.h有向边——若图中的边e所对应的结点偶对是有序的，记为，简称弧．a，b分别称为弧的始点与终点，并均称为e的端点．称e是关联于结点a和b的，结点a和结点b是相、邻的，或称结点a和结点b是邻接的．h无向边——若图中的边e所对应的结点偶对是无序的，记为（a，b），简称棱．a，b称为e的端点．称e是关联于结点a和b的，结点a和结点b是相邻的，或称结点a和结点b是邻接的．h无向图—
2、—每条边都是无向边的图，记作G＝．h有向图——每条边都是有向边的图，记作D＝.h底图——如果把有向图中每条有向边都看作无向边，就得一个无向图，此无向图称为原有向图的底图．h弧立结点——图中不与任何相邻的结点．h零图——边集为空集的图，即全由孤立结点构成的图．h自回路(环——关联于同一个结点的边．h无向平行边——联结相同两个结点的多于1条的无向边．h有向平行边——联结两个结点之间的多于1条且方向相同的有向边．h多重图——含平行边的图.h线图（简单图）——非多重图．h最大度——D(G)=max{deg(v)½vÎV}．h最小度——d(
3、G)=min{deg(v)½vÎV}．h在无向图G＝中，与结点v(ÎV)关联的边数，即为结点度数deg(v).；在有向图D＝中，以v(ÎV)为起点的边之条数为出度deg＋(v)；以v(ÎV)为终点的边之条数为入度deg－(v).结点v的出度和入度之和为度数.h二部图——若能将V分成两个互不相交的子集V1与V2使得G中任一边的两端点都不在同一个Vi（i=1,2）中的n阶无向图，记G=．h完全图——若每一对结点间都有边相连的简单图；有n个结点的无向完全图记为Kn.此时有；有n个结点的且每对结点之间都有两条方向相反的边相关连的有
4、向图为有向完全图，.此时有．hk-正则图——每个结点的度均为某个固定整数k的无向简单图．．h赋权图——图G是一个三重组或四重组，其中V是结点集合，E是边的集合，f是定义在V上的函数，g是定义在E上的函数．h补图`G=——设G＝,，以V为结点集，以使G成为完全图所添加的边为边集E¢的图，就是图G的补图G¢，即是完全图，其中EÇE¢＝Æ．h子图（真子图）——设G＝,V，E的子集V¢,E¢构成的图G¢=是图G的子图；若G¢ÍG且G¢¹G，(V¢ÌV或E¢ÌE)，G¢是G的真
5、子图．h生成子图——设图G＝,若E¢ÍE,则图<.V,E¢>是的生成子图．即结点与原图G相同的子图，为生成子图．h图的同构——设G1=和G2=,存在双射f：V1®V2，"(vi,vj)ÎE1,当且仅当(f(vi),f(vj))ÎE2，且(vi,vj)与(f(vi),f(vj))的重数相同.则G1≌G2．同构充分条件：建立两个图的对应关系，这个关系是双射函数．同构必要条件：①结点数相同；②边数相同；③度数相同的结点个数相同．h握手定理设G=，有,握手定理推论：奇数度结点的个数为偶数个．h在图D＝
6、中，，＝2½E½.h在任何有向图中，所有的入度之和等于所有结点的出度之和．2．通路、回路、图的连通性h通路与通路的长度——设图G＝，V＝{v0,v1,…,vn},E={e1,e2,…,em},结点与边的交替序列v0e1v1e2…vi－1eivi,为结点v0到结点vi的通路.v0,vi是通路的起点和终点．通路中边的数目就是通路的长度.h回路——起点和终点重合的通路.h边不重复的通路(回路)称简单通路(回路)；结点不重复的通路(回路)，称基本通路(回路)．.h连通与连通图——无向图G中，结点u,v存在通路，则u,v是连通的，G中任意结点u,v都是连通的，
7、G是连通图.h连通分支P(G)——设G＝，V的连通等价类V1，V2，…，Vm,子图G(V1)，G(V2)，…，G(Vm)称为连通分支.h短程线——设u与v是图G的两个结点，若u与v连通，则称u与v之间的长度最短的路为u与v之间的短程线，短程线的长度可作为结点u与v间的距离，记作d(u,v).h有向图的连通——有向图中，任意一对结点之间至少有一个结点可达另一结点是单侧连通；任何一对结点都相互可达是强连通；略去有向图D边的方向成为无向连通图是弱连通.由定义可知：强连通单侧连通弱连通.h在简单有向图G=中，G’是G的子图，如G’是强连通的（单向连
8、通的，弱连通的），且没有包含G’的更大
