资源描述
单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考，不能作为科学依据。感谢,图 论,信息学院计算机应用技术系,讲课教师：胡静,办公地点：信息楼805,联络方式：13064013020,电子邮箱：ise_huj,1/27,1,图论起源和发展,图论是数学一个分支。它以图为研究对象。图论中图是由若干给定点及连接两点线所组成图形，这种图形通惯用来描述一些事物之间某种特定关系，用点代表事物，用连接两点线表示对应两个事物间含有这种关系。,图论最早起源于一些数学游戏难题研究，如1736年Euler所处理Knigsberg七桥问题，以及民间广为流传一些游戏难题，如迷宫问题，匿门博弈问题，棋盘上马行走路线问题等。这些古老数学难题，当初吸引了很多学者注意，在这些问题研究基础上又继续提出了著名四色猜测，汉密尔顿（周游世界）数学难题。,2/27,2,图论起源和发展,1847年，克希霍夫（Kirchhoff）用图论分析电网络，这是图论最早应用于工程科学。以后伴随科学发展，图论在处理运筹学、网络理论、信息论、控制论、博弈论以及计算机科学等各个领域问题时，显示出越来越大效果。,图论在各种物理学科，化学学科，工程领域，社会科学和经济问题广泛应用，使它受到数学界和工程界广泛支持。,3/27,3,离散数学第22讲,本讲基本知识点：,1、图论中基本概念,2、通路与回路定义,3、图连通性,4、图矩阵表示,4/27,4,第十四章 图基本概念,14.1 图,定义14.1,一个,无向图,是一个有序二元组,，记作G，其中,(1)V称为,顶点集,，其元素称为,顶点,或,结点,。,(2)E称为,边集,，它是,无序积,V&V,多重子集,，其元素称为,无向边,，简称为,边,。,设A，B为任意两个集合，称,a,b,|a,A,b,B,为A与B无序积，记作A&B,.,元素能够重复出现集合称为,多重集合,，某个元素重复出现次数称为该元素,重复度,。比如在集合,a,b,b,a,a中，a,b重复度分别为3,2.,5/27,5,第十四章 图基本概念,定义14.2,一个,有向图,是一个有序二元组,，记作D，其中,(1)V,称为,顶点集,，其元素称为,顶点,或,结点,。,(2)E称为,边集,，它是笛卡儿积VV多重子集，其元素称为,有向边,，简称为,边,。,用图形表示无(有)向图时，惯用小圆圈或实心点表示顶点，用顶点之间连线表示无向边，用有方向边表示有向边。,6/27,6,第十四章 图基本概念,v,1,。,v,2,v,3,。(1),v,4,。,v,5,a,。b,(2),d。c,例14.1 画出以下图形。,(1)G=,其中V=,v,1,v,2,v,3,v,4,v,5,E=(,v,1,v,1,),(,v,1,v,2,),(,v,2,v,3,),(,v,2,v,3,),(,v,1,v,5,),(,v,2,v,5,),(,v,4,v,5,)。,(2)D=,其中V=a,b,c,d,E=,。,7/27,7,第十四章 图基本概念,与图相关概念和要求,(1)普通用G泛指图。V(G)、E(G)分别表示G顶点集、边集，|V(G)|、|E(G)|分别表示G顶点数、边数。若|V(G)|=n,则称G为,n阶图,。,(2)若|V(G)|、|E(G)|均为有限数，则称G为,有限图,。这是本书讨论重点。,(3)在图G中，若E(G)=,则称G为,零图,.此时若|V(G)|=n，则称G为,n阶零图,，记作N,n,。特殊称N,1,为,平凡图,。,8/27,8,第十四章 图基本概念,定义14.3,在无向图中，关联一对顶点无向边假如多于1条，则称这些边为,平行边,，平行边条数称为,重数,。,在有向图中，关联一对顶点有向边假如多于1条，而且这些边始点与终点相同(即方向相同)，则称这些边为,平行边,。,含平行边图称为,多重图,，既不含平行边也不含环图称为,简单图,。,如：,。a,。b,e。,d。,c。,9/27,9,第十四章 图基本概念,定义14.4,设G=为一无向图，结点v(vV)关联边数之和称作该结点,度数,，简称为,度,，记作d,G,(v),简记作d(v).,设D=为一有向图，结点v(vV)关联边中,，,以v为边始点边数之和称作v,出度,，记作d,D,+,(v)，简记作d,+,(v)；以v为边终点边数之和称作v,入度,，记作d,D,-,(v)，简记作d,-,(v).,称d,+,(v)+d,D,-,(v)为v,度数,，记作d(v).,在无向图G中，令,(G)=maxd(v)|vV(G),(G)=mind(v)|vV(G),称，分别为G最大度和最小度。,10/27,10,第十四章 图基本概念,定理14.1握手定理,设G=为任意无向图，V=,v,1,v,2,v,n,|E|=m,则,证实：G中每条边（包含环）均提供2个端点，故在计算各顶点度数和时，每条边均提供2度，m条边共提供2m度。,=2m,即个顶点度数之和等于边数2倍。,11/27,11,定理14.2握手定理,设D=为任意有向图，V=,v,1,v,2,v,n,|E|=m,则,=2m，且,=,=m,证实：D中每条边（包含环）均关联两个顶点，故在计算各顶点度数和时，每条边均提供2度，即1个出度和1个入度，m条边则提供m个出度，m个入度，共2m度。,第十四章 图基本概念,12/27,12,第十四章 图基本概念,推论,任何图中，奇度顶点个数一定是偶数。,证实：设G=为任一图，令,V1=v|vV,d(v)为奇数,V2=v|vV,d(v)为偶数,则V1 V2=V,V1V2=,由握手定理知,2m=,=,故,+,必为偶数，又,V,1,为奇度顶点集，故|,V,1,|必为偶数.,13/27,13,经典例题：,例1:,已知无向图G中有10条边，2个2度顶点,2个3度顶点,1 个4度顶点,其余顶点度数都是1,问G中有多少个顶点?,例2:,已知无向图G中有10条边，3度与4度顶点各2个,其余顶点度数均小于3,问G中最少有多少个顶点?,第十四章 图基本概念,解：假设顶点个数为n个，则由握手定理可知,2*2+2*3+1*4+（n-1-2-2）*1=10*2,故 n=11,14/27,14,定义14.5,完全图,设G为一个含有n个结点无向简单图，假如G中任一个结点都与其余n-1个结点相邻接，则称G为,无向完全图,，简称G为,完全图,，记为,K,n,。,设G为一个含有n个结点有向简单图，若对于任意u,v,V(u,v)，现有有向边，又有有向边，则称G为,有向完全图,，在不发生误解情况下，也记为,K,n,。,无向完全图K,n,边数,为=n(n-1)，有向完全图K,n,边数,为=n(n-1)。,第十四章 图基本概念,15/27,15,第十四章 图基本概念,14.2 通路与回路,定义14.11,图,G中结点和边相继交织出现序列T=v,0,e,1,v,1,e,2,v,2,e,k,v,k,，若T中边e,i,两端点是v,i-1,和v,i,（G是有向图时要求v,i-1,与v,i,分别是e,i,始点和终点），则称T为结点v,0,到结点v,k,通路,。,v,0,和v,k,分别称为此通路始点和终点，统称为通路,端点,。,通路中边数目k称为此,通路长度,。,当v,0,v,R,时，此通路称为,回路,。,16/27,16,若通路中全部边e,1,，e,2,，e,k,互不相同，则称此通路为,简单通路,或一条,迹,；若回路中全部边e,1,，e,2,，e,k,互不相同，则称此回路为,简单回路,或一条,闭迹,；,若通路中全部结点v,0,，v,1,，v,k,互不相同，则称此通路为,基本通路,或者,初级通路,、,路径,；若回路中除v,0,v,k,外全部结点v,0,，v,1,，v,k-1,互不相同（从而全部边互不相同），则称此回路为,基本回路,或者,初级回路,、,圈,。,基本通路(或基本回路)一定是简单通路(或简单回路)，但反之则不一定。,第十四章 图基本概念,17/27,17,第十四章 图基本概念,14.3 图连通性,定义14.12,设无向图G=,u,v,V,若u,v之间存在通路，则称u,v是,连通,，记作,uv,.,u,V,要求vv.,由定义不难看出，无向图中顶点之间,连通关系,=,|u,v V且u与v之间有通路,显然是自反，对称，传递，因而,是V上,等价关系,定义14.13,若无向图G是平凡图或G中任何两个顶点都是连通，则称G为,连通图,，不然称G为,非连通图,或,分离图,。,18/27,18,定义14.14,若无向图G=，V关于顶点之间连通关系商集V/=V,1,V,2,V,k,V,i,为等价类，称导出子图GV,i,(I=1,2,k)为G,连通分支,，连通分支数k常记为p(G).,例:以下图连通分支数分别为:,第十四章 图基本概念,v,3,。,。,。,v,1,e,4,v,2,v,4,v,5,e,1,e,3,e,5,e,6,e,7,v,3,。,。,。,v,1,v,2,v,4,v,5,e,1,e,3,v,3,。,。,V,1,v,2,1,3,3,19/27,19,。,。,。,第十四章 图基本概念,定义14.17,设无向图G=,若存在E,E,且E,，使得P(G-E)P(G)，而对于任意E,E，都有P(G-E)=P(G)，则称E是G,边割集,，或简称为,割集,。若E是单元集，即E=e,则称e为,割边,或,桥,.,定义14.16,设无向图G=,若存在V,V,且V,，使得P(G-V)P(G)，而对于任意V,V,，都有P(G-V)=P(G)，则称V是G,点割集,，若V是单元集，即V=v,则称v为,割点,.,v,5,v,1,e,3,v,2,v,3,v,4,e,1,e,5,e,4,e,6,e,2,v,6,20/27,20,第十四章 图基本概念,14.4 图矩阵表示,定义14.24,设无向图G=,V=v,1,v,2,v,n,E=e,1,e,2,e,m,令m,ij,为顶点v,i,与边e,j,关联次数，则称(m,ij,),nm,为G,关联矩阵,，记作M(G)。,以下列图关联矩阵为：,。,。,。,v,3,v,1,e,4,v,2,v,4,v,5,e,1,e,3,e,5,e,6,e,7,v,6,e,2,1 0 0 0 1 0 0,0 0 0 0 0 1,0 0 1 0 0 1 0,0 0 1 1 0 0 1,0 0 0 1 1 0 0,0 2 0 0 0 1 0,关联矩阵性质P,284,.,21/27,21,第十四章 图基本概念,14.4 图矩阵表示,定义14.25,设有向图D=中无环,V=v,1,v,2,v,n,E=e,1,e,2,e,m,令m,ij,为顶点v,i,与边e,j,关联次数，则称(m,ij,),nm,为G,关联矩阵,，记作M(G)。,1,v,i,为e,j,始点,m,ij,=0，v,i,与e,j,是不关联,-1，v,i,为e,j,终点,则称(m,ij,),nm,为D关联矩阵，记作M(D)。,22/27,22,第十四章 图基本概念,关联矩阵性质P,285,.,以下列图关联矩阵为：,-1 -1 1 1 0 0 0,0 1 -1 0 1 0 0,0 0 0 -1 0 1 -1,1 0 0 0 -1-1 -1,e,3,e,1,e,2,e,4,e,5,e,6,e,7,23/27,23,第十四章 图基本概念,定义14.26,设有向图D=中无环,V=v,1,v,2,v,n,E=e,1,e,2,e,m,令a,ij,(1),为顶点v,i,与邻接到顶点v,j,边条数，称(a,ij,(1),),nn,为D,邻接矩阵,，记作A(D)，或简记为A。,邻接矩阵性质P,286,.,以下列图邻接矩阵为：,e,3,e,1,e,2,e,4,e,5,e,6,e,7,0 1 1 0,1 0 0 1,0 0 1 0,1 0 1 0,邻接矩阵展示了两点间长度为1通路数，那么怎样求两点间长度为L通路数呢？,24/27,24,第十四章 图基本概念,定义14.27,设D=为有向图,V=v,1,v,2,v,n,令,可达矩阵实例 P,350,.,1,v,i,可达v,j,p,ij,=,0，v,i,不可达v,j,称(p,ij,),nn,为D,可达矩阵,，记作P(D),简记作P。,25/27,25,第十四章 图基本概念,Warshall算法一个求,可达矩阵,算法：,设M为有向图D长度为1可达矩阵，则,(1)置新矩阵N=M;,(2)置i=1;,(3),对j(1jn),若N第j 行第i 列处为1，则对k=1,2,n 做以下计算：,将N 第j 行k 列处元素与第i 行k 列处元素进行逻辑加，然后将结果放到第j 行k 列处，即,N j,k=N j,k+N i,k;,(4)i=i+1;,(5)若in,go(3),不然停顿。,最终得到矩阵N即为所求。,26/27,26,离散数学 第22讲,本讲小结：,图论中基本概念,握手定理及推论,完全图及其特征,通路及回路,27/27,27,
展开阅读全文
浙ICP备2021020529号-1 | 浙B2-20240490 
