离散数学第7章.ppt

第7章图的基本概念7.1无向图及有向图7.2通路、回路、图的连通性7.3图的矩阵表示7.4最短路径及关键路径7.1无向图及有向图定义7.1一个图G为一个二元组V，E，记作G=V，E=V(G)，E(G)。图G的点集V=V(G)={v1,v2,…,vn}，是个非空集合，它的元素vi称为结点；图G的边集E=E(G)={e1,e2,…,en}，其元素称为边，其中ei=(vi,vj)，vi,vj?V。定义7.3边(或弧)e与vj关联、独立点、环定义7.4邻接：viadjvj、始点、终点图的分类有限图按结点对分：有向图、无向图、混合图定义7.6平行边按同一结点对间的边数分：多重图：含有平行边伪图：含有平行边或环或两者皆有简单图：不含有平行边和环线图：不含有平行边度数定义7.5在有向图G=V，E中，对?v∈V，以v为始点的弧的条数称为v的出度，记为d+(v)；以v为终点的弧的条数称为v的入度，记作d-(v)；结点v的出度与入度之和，称为结点的度数，记为d(v)，显然d(v)=d+(v)+d-(v)。对于无向图G=V，E，结点v∈V的度数等于联结它的边数，也记为d(v)。若v点有环，规定该点度数因环而增加2。定理7.1给定图G=V，E，则?d(vi)=2m。定理在任何图中，奇度结点的数目为偶数。度数序列k度正则图n阶图完全图零图、平凡图定义7.9设简单无向图G=V,E，E’={(u,v)|u?v,u.v?V,(u,v)?E}，图G’=V,E’称为图G的补图。子图定义7.8设图G=V,E，G’=V’,E’,如果V’?V且E’?E，则G’是G的子图；如果V’?V且E’?E且G’≠G，则G’是G的真子图；如果V’=V且E’?E，则G’是G的生成子图。权图定义图G=V，E，对每条边e?E，都有唯一的实数w(e)与其相对应（w(e)称为边e的权），图G称为权图，记为G=V，E，W，其中W表示各边之权的集合。图的运算定义G1=V1,E1，G2=V2,E2G1∪G2=G3=V3,E3,V3=V1∪V2,E3=E1∪E2G1∩G2=G3=V3,E3,V3=V1∩V2,E3=E1∩E2G1-G2=G3=V3,E3,E3=E1-E2，V3=(V1∩V2)∪{E3中边所关联的结点}删除边e删除结点vG1?G2=G3=V3,E3=(G1∪G2)-(G1∩G2)图的同构定义7.10图G1=V1，E1,G2=V2，E2。若存在双射函数f:V1?V2,使得对?u,v∈V1,有e=u,v∈E1?e’=f(u)，f(v)∈E2，并且e和e’有相同的重数，则称G1同构于G2，记为G1?G2。图同构的必要条件：(1)结点数目相等；(2)边数相等；(3)度数相同的结点数目相等。7.2通路、回路、图的连通性定义7.11图G=V，E,v1,v2,…,vn?V，e1,e2,…,en?E，其中vi-1，vi是ei的结点，交替序列v0e1v1e2v2…envn称为一条连接v0到vn的通路(或链)。v0和vn分别称为路的始结点和终结点，而边的数目称为路的长度。若v0=vn时，该路称为回路。定义在一条路中，若出现的边都是不相同的，称该路为简单路；若出现的结点都是不相同的，称该路为基本路（初级通路）。在一回路中，若出现的边都不相同，称该回路为简单回路；若除v0=vn外,出现的结点都不相同，称该回路为基本回路（初级回路或圈)。定理7.3在一个n阶图中，若从结点vi到结点vj(vi≠vj)存在一条路，则必有一条从vi到vj的长度不大于n-1的路。定理7.4在一个n阶图中，若存在结点vi到自身的一条回路，则必有一条从vi到自身的长度不大于n的回路。定义7.12在一个无向图G中，若从vi到vj存在通路，则称vi与vj是连通的。在一个有向图中，若从vi到vj存在通路，则称从vi到vj是可达的，或简称vi可达vj。定义在无向图G中，若vi与vj是连通的，则称vi与vj之间长度最短的通路为vi与vj之间的短程线（测地线)，其长度称为vi与vj之间的距离。连通图定义7.13若无向图G中任意两顶点都是连通的，则称G是连通图。定