《离散数学-耿素云PPT(第5版)5.1.ppt》由会员分享，可在线阅读，更多相关《离散数学-耿素云PPT(第5版)5.1.ppt（27页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、1 图论图论 2图论部分图论部分 n第第5章章图的基本概念图的基本概念n第第6章章特殊的图特殊的图n第第7章章树树3第第5章章 图的基本概念图的基本概念 5.1无向图及有向图无向图及有向图5.2通路通路,回路和图的连通性回路和图的连通性5.3图的矩阵表示图的矩阵表示5.4最短路径最短路径,关键路径和着色关键路径和着色45.1无向图及有向图无向图及有向图无向图与有向图无向图与有向图顶点的度数顶点的度数握手定理握手定理简单图简单图完全图完全图子图子图补图补图 5无向图无向图 多重集合多重集合:元素可以重复出现的集合元素可以重复出现的集合无序积无序积:A B=(x,y)|x A y B定义定义无向图
2、无向图G=,其中其中(1)顶点集顶点集V是非空有穷集合是非空有穷集合,其其元素称为元素称为顶点顶点(2)边集边集E为为V V的多重子集，的多重子集，其元素称为其元素称为无向边无向边，简称，简称边边.例如例如,G=,其中其中V=v1,v2,v5,E=(v1,v1),(v1,v2),(v2,v3),(v2,v3),(v2,v5),(v1,v5),(v4,v5)6有向图有向图定义定义有向图有向图D=,其中其中(1)顶点集顶点集V是非空有穷集合是非空有穷集合,其元素称为其元素称为顶点顶点(2)边集边集E为为V V的多重子集，其的多重子集，其元素称为元素称为有向边有向边，简称，简称边边.D的的基图基图:
3、用无向边代替有向边用无向边代替有向边如如D=,其中其中 V=a,b,c,dE=,图图的数学定的数学定义义与与图图形表示形表示,在同构意在同构意义义下下一一对应一一对应 7无向图与有向图无向图与有向图(续续)通常用通常用G表示无向图表示无向图,D表示有向图表示有向图,也常用也常用G泛指泛指无向图和有向图无向图和有向图.V(G),E(G),V(D),E(D):G和和D的顶点集的顶点集,边集边集.n 阶图阶图:n个顶点的图个顶点的图零图零图:E=平凡图平凡图:1阶零图阶零图空图空图:V=8顶点和边的关联与相邻顶点和边的关联与相邻定义定义设设e=(u,v)是无向图是无向图G=的一条边的一条边,称称u,
4、v为为e的的端点端点,e与与u(v)关联关联.若若u v,则称则称e与与u(v)的的关联次数为关联次数为1;若若u=v,则则称称e为为环环,此时称此时称e与与u 的的关联次数为关联次数为2;若若w不是不是e端点端点,则称则称e与与w 的的关联次数为关联次数为0.无边关联的顶点称作无边关联的顶点称作孤立点孤立点.定定义义设设无无向向图图G=,u,v V,e,eE,若若(u,v)E,则则称称u,v相邻相邻;若若e,e 至少有一个公共端点至少有一个公共端点,则称则称e,e 相邻相邻.对对有有向向图图有有类类似似定定义义.设设e=u,v 是是有有向向图图的的一一条条边边,又又称称u是是e的的始点始点,
5、v是是e的的终点终点,u邻接到邻接到v,v邻接于邻接于u.9顶点的度数顶点的度数 设设G=为无向图为无向图,v V,v的度数的度数(度度)d(v):v作为边的端点次数之和作为边的端点次数之和 悬挂顶点悬挂顶点:度数为度数为1的顶点的顶点悬挂边悬挂边:与悬挂顶点关联的边与悬挂顶点关联的边 G的最大度的最大度(G)=maxd(v)|v V G的最小度的最小度(G)=mind(v)|v V例如例如d(v5)=3,d(v2)=4,d(v1)=4,(G)=4,(G)=1,v4是悬挂顶点是悬挂顶点,e7是悬挂边是悬挂边,e1是环是环10顶点的度数顶点的度数(续续)设设D=为有向图为有向图,v V,v的出度
6、的出度d+(v):v作为边的始点次数之和作为边的始点次数之和 v的入度的入度d(v):v作为边的终点次数之和作为边的终点次数之和 v的度数的度数(度度)d(v):v作为边的端点次数之和作为边的端点次数之和 d(v)=d+(v)+d-(v)D的最大出度的最大出度+(D)=maxd+(v)|v V最小出度最小出度+(D)=mind+(v)|v V最大入度最大入度 (D)=maxd(v)|v V最小入度最小入度 (D)=mind(v)|v V最大度最大度(D)=maxd(v)|v V最小度最小度(D)=mind(v)|v V11例例例例d+(a)=4,d-(a)=1,d(a)=5,d+(b)=0,d
7、-(b)=3,d(b)=3,+(D)=4,+(D)=0,(D)=3,(D)=1,(D)=5,(D)=3.12图论基本定理图论基本定理握手定理握手定理 定定理理任任意意无无向向图图和和有有向向图图的的所所有有顶顶点点度度数数之之和和都都等等于于边边数数的的2倍倍,并并且且有有向向图图的的所所有有顶顶点点入入度度之之和和等等于出度之和等于边数于出度之和等于边数.证证G中每条边（包括环）均有两个端点，所以在计中每条边（包括环）均有两个端点，所以在计算算G中各顶点度数之和时，每条边均提供中各顶点度数之和时，每条边均提供2度，度，m条边共提供条边共提供2m度度.有向图的每条边提供一个入度有向图的每条边提
8、供一个入度和一个出度和一个出度,故所有顶点入度之和等于出度之和等故所有顶点入度之和等于出度之和等于边数于边数.推论推论任意无向图和有向图的奇度顶点个数必为偶数任意无向图和有向图的奇度顶点个数必为偶数.13图的度数列图的度数列 设无向图设无向图G的顶点集的顶点集V=v1,v2,vnG的度数列的度数列:d(v1),d(v2),d(vn)如右图度数列如右图度数列:4,4,2,1,3设有向图设有向图D的顶点集的顶点集V=v1,v2,vnD的度数列的度数列:d(v1),d(v2),d(vn)D的出度列的出度列:d+(v1),d+(v2),d+(vn)D的入度列的入度列:d(v1),d(v2),d(vn)
9、如右图度数列如右图度数列:5,3,3,3出度列出度列:4,0,2,1入度列入度列:1,3,1,214握手定理的应用握手定理的应用例例1(3,3,3,4),(2,3,4,6,8)能成为图的度数列吗能成为图的度数列吗?解解 不可能不可能.它们都有奇数个奇数它们都有奇数个奇数.例例2已知图已知图G有有10条边条边,4个个3度顶点度顶点,其余顶点的度其余顶点的度数均小于等于数均小于等于2,问问G至少有多少个顶点至少有多少个顶点?解解 设设G有有n个顶点个顶点.由握手定理由握手定理,4 3+2(n-4)2 10解得解得n 815握手定理的应用握手定理的应用(续续)例例3证明不存在具有奇数个面且每个面都具
10、有奇数证明不存在具有奇数个面且每个面都具有奇数条棱的多面体条棱的多面体.证证用反证法用反证法.假设存在这样的多面体假设存在这样的多面体,作无向图作无向图G=,其中其中V=v|v为多面体的面为多面体的面,E=(u,v)|u,v V u与与v有公共的棱有公共的棱 u v.根据假设根据假设,|V|为奇数且为奇数且 v V,d(v)为奇数为奇数.这与握这与握手定理的推论矛盾手定理的推论矛盾.16多重图与简单图多重图与简单图 定定义义 (1)(1)在在无无向向图图中中,如如果果有有2 2条条或或2 2条条以以上上的的边边关关联联同同一一对对顶顶点点,则则称称这这些些边边为为平平行行边边,平平行行边边的的
11、条数称为条数称为重数重数.(2)(2)在在有有向向图图中中,如如果果有有2 2条条或或2 2条条以以上上的的边边具具有有相相同同的的始始点点和和终终点点,则则称称这这些些边边为为有有向向平平行行边边,简简称称平行边平行边,平行边的条数称为平行边的条数称为重数重数.(3)(3)含平行边的图称为含平行边的图称为多重图多重图.(4)(4)既无平行边也无环的图称为既无平行边也无环的图称为简单图简单图.注意注意:简单图是极其重要的概念简单图是极其重要的概念 17实例实例e5和和e6是平行边是平行边重数为重数为2不是简单图不是简单图e2和和e3是平行边是平行边,重数为重数为2e6和和e7不是平行边不是平行
12、边不是简单图不是简单图18图的同构图的同构 定义定义设设G1=,G2=为两个无向图为两个无向图(有有向图向图),若存在双射函数若存在双射函数f:V1V2,使得对于任意的使得对于任意的vi,vj V1,(vi,vj)E1（E1）当且仅当）当且仅当(f(vi),f(vj)E2（E2），），并且并且,(vi,vj)（）与）与(f(vi),f(vj)（）的重数相同，则称的重数相同，则称G1与与G2是是同构同构的，记作的，记作G1 G2.同构实例同构实例 19彼得森图彼得森图例例1证证明下述明下述2对图对图是同构的是同构的20同构实例同构实例(续续)例例2试画出试画出4阶阶3条边的所有非同构的无向简单图
13、条边的所有非同构的无向简单图例例3判断下述每一对图是否同构判断下述每一对图是否同构:(1)度数列不同度数列不同不同构不同构21同构实例同构实例(续续)(2)(3)不同构不同构入入(出出)度列不同度列不同不同构不同构(左左边边没有没有三角形三角形,右右边边有三有三角形角形)注意注意:度数列相同度数列相同 (1)(2)22图的同构图的同构(续续)几点说明：几点说明：图之间的同构关系具有自反性、对称性和传递性图之间的同构关系具有自反性、对称性和传递性.能找到多条同构的必要条件能找到多条同构的必要条件,但它们都不是充分条件但它们都不是充分条件:边数相同，顶点数相同边数相同，顶点数相同度数列相同度数列相
14、同(不计度数的顺序不计度数的顺序)对应顶点的关联集及邻域的元素个数相同，等等对应顶点的关联集及邻域的元素个数相同，等等若破坏必要条件，则两图不同构若破坏必要条件，则两图不同构至今没有找到判断两个图同构的多项式时间算法至今没有找到判断两个图同构的多项式时间算法23完全图完全图 n阶阶无无向向完完全全图图Kn:每每个个顶顶点点都都与与其其余余顶顶点点相相邻邻的的n阶无向简单图阶无向简单图.简单性质简单性质:边数边数m=n(n-1)/2,=n-1n阶阶有有向向完完全全图图:每每对对顶顶点点之之间间均均有有两两条条方方向向相相反反的的有向边的有向边的n阶有向简单图阶有向简单图.简单性质简单性质:边数边
15、数m=n(n-1),=2(n-1),+=+=-=-=n-1 K53阶有向完阶有向完全图全图24子图子图 定义定义设设G=,G =是两个图是两个图(1)若若V V且且E E,则称则称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 为顶点集为顶点集,以两端点都在以两端点都在V 中的所有边为边集的中的所有边为边集的G的子图称作的子图称作V 的导的导出子图出子图，记作，记作GV (5)设设E E且且E,以以E 为边集为边集
16、,以以E 中边关联的中边关联的所有顶点为顶点集的所有顶点为顶点集的G的子图称作的子图称作E 的导出子的导出子图图,记作记作GE 25生成子图实例生成子图实例 K4的所有非同构的生成子图的所有非同构的生成子图导出子图实例导出子图实例 26GDGv1,v2Ge1,e3,e4De1,e3Dv1,v227补图补图 定定义义设设G=为为n阶阶无无向向简简单单图图，以以V为为顶顶点点集集,所所有有使使G成成为为完完全全图图Kn的的添添加加边边组组成成的的集集合合为为边边集集的的图，称为图，称为G的的补图补图，记作，记作.若若G,则称则称G是是自补图自补图.例例对对K4的的所所有有非非同同构构子子图图,指指出出互互为为补补图图的的每每一一对对子图子图,并指出哪些是自补图并指出哪些是自补图.