您好,欢迎访问三七文档
当前位置:首页 > 商业/管理/HR > 薪酬管理 > 北大离散数学chap7
图论简介图论是一个古老的数学分支,它起源于游戏难题的研究。图论的内容十分丰富,应用得相当广泛,许多学科,诸如运筹学、信息论、控制论、网络理论、博弈论、化学、生物学、物理学、社会科学、语言学、计算机科学等,都以图作为工具来解决实际问题和理论问题。随着计算机科学的发展,图论在以上各学科中的作用越来越大,同时图论本身也得到了充分的发展。本课程在第七,八,九各章中介绍与计算机科学关系密切的图论的内容。第七章图的基本概念第一节无向图及有向图内容:有向图,无向图的基本概念。重点:1、有向图,无向图的定义,2、图中顶点,边,关联与相邻,顶点度数等基本概念,3、各顶点度数与边数的关系1()2niidvm及推论,内容:有向图,无向图的基本概念。5、图的同构的定义。重点:4、简单图,完全图,子图,补图的概念,一、图的概念。1、定义。无序积&(,)ABabaAbB无向图,GVE&EVV中元素为无向边,简称边。,E有向图,DVEEVV中元素为有向边,简称边。,E一、图的概念。1、定义。无序积&(,)ABabaAbB,(),(),(),()GVEVVGEEGDVEVVDEED无向图记为记为图有向图记为记为2、图的表示法。有向图,无向图的顶点都用小圆圈表示。无向边(,)ab——连接顶点,ab的线段。有向边,ab——以a为始点,以b为终点的有向线段。例1、(1)无向图,GVE12345,,,,Vvvvvv,122223131314(,),(,),(,),(,),(,),(,)Evvvvvvvvvvvv图形表示如右:6e5e4e3e2e1e5v4v3v2v1v图形表示如右:例1、(2)有向图,DVE12345,,,,Vvvvvv,12323234,,,,,,,,Evvvvvvvv24455455,,,,,,,vvvvvvvv3、相关概念。(1)有限图——都是有限集的图。,VE阶图——n的图。Vn零图——的图。特别,若又有E1V,称平凡图。(2)关联(边与点关系)——设边(,)kijevv(或,ijvv),则称与(或)关联。keivjv3、相关概念。01122ikikikkvevevee与不关联无向图关联的次数与关联次与关联次(为环)(2)101ikikikveveve为的始点与不关联为的终点有向图关联的次数(无环)3、相关概念。(2)点的相邻——两点间有边,称此两点相邻边的相邻——两边有公共端点,称此两边相邻相邻孤立点——无边关联的点。环——一条边关联的两个顶点重合,称此边为环(即两顶点重合的边)。3、相关概念。(2)悬挂点——只有一条边与其关联的点,所对应的边叫悬挂边。(3)平行边——关联于同一对顶点的若干条边称为平行边。平行边的条数称为重数。多重图——含有平行边的图。简单图——不含平行边和环的图。如例1的(1)中,6e5e4e3e2e1e5v4v3v2v1v与关联的次数均为1,1e12,vv与关联的次数为2,2e2v边1456,,,eeee都是相邻的,为孤立点,5v为悬挂点,4v6e为悬挂边,2e为环,45,ee为平行边,重数2,为多重图。G4、完全图设为阶无向简单图,若,GVEn中每个G顶点都与其余个顶点相邻,则称1n为Gn阶无向完全图,记作nK。若有向图的任一对顶点D,()uvuv,既有有向边,uv又有有向边,vu,则称为有向完全图。D例如:4K5K二、顶点的度数,握手定理。1、顶点的度数(简称度)。无向图的度数记,指与,GVEiv,()idviv相关联的边的条数。有向图的度数,GVEiv,()()()iiidvdvdv二、顶点的度数,握手定理。1、顶点的度数(简称度)。最大度()max()GdvvV最小度()min()GdvvV对有向图相应地还有()D()D()G()G,,,。如例1的(2)中,222()()()dvdvdv134111()()()dvdvdv101555()()()224dvdvdv()4D,()1D。设为图的顶点集,称11,,,nVvvvG12(),(),,()ndvdvdv为的度数序列。G2、握手定理。定理1:设图为无向图或有向图,,GVE11,,,nVvvvEm为边数),m,(则1()2niidvm定理2:设为有向图,,DVE11,,,nVvvvEm,则,11()()nniiiidvdvm。2、握手定理推论:任何图中,度为奇数的顶点个数为偶数。1()2niidvm例2、(1)(3,3,2,3)(5,2,3,1,4)能成为图的度数,序列吗?为什么?(2)已知图中有10条边,4个3度顶点,其余顶G点的度数均小于3,问中至少有多少个顶点?为什么?G三、子图,补图。1、子图定义:设是两个图,若,GVE'','GVE,'VV,且'EE,则称'G是的子图,GG是的母图,记作'GG'G。真子图——且(即或'GG'GG'VV'EE)。生成子图——且'GG'VV。三、子图,补图。导出子图——非空,以为顶点集,'VV'V以两端均在中的边的全体为边集的'VG的子图,称的导出子图。'V——非空'EE,以'E为边集,以中边关联的顶点的全体为顶点集的'EG的子图,称的导出子图。'E例3、(1)(2)(3)(4)(5)(6)上图中,(1)-(6)都是(1)的子图,其中(2)-(6)为真子图,(1)-(5)为生成子图。2、补图定义。设为无向完全图,11,GVE,GVE,22,GVE为无向简单图,其中12EE,12EEE,则称1G2G,相对于G互为补图,记12GG21GG,。(1)(2)(3)(4)(5)(6)如例3中,四、图的同构。定义:设两个无向图111,GVE,222,GVE,若存在双射函数12:VV,使得对于任意的1(,)ijevvE,当且仅当2'(),()ijevvE并且与重数相同,则称e'e与同构,1G2G记作12GG≌。例4、(1)(2)(3)(4)(5)(6)(7)1v2v3v4v5v5v1v2v3v4v6vecacaefbddb例5、(1)画出4个顶点,3条边的所有非同构的无向简单图。解:只有如下3个图:(1.1)(1.2)(1.3)例5、(2)画出3个顶点,2条边的所有非同构的有向简单图。解:只有如下4个图:第二节通路,回路,图的连通性内容:图的通路,回路,连通性。重点:1、通路,回路,简单通路,回路,初级通路,回路的定义,2、图的连通性的概念,3、短程线,距离的概念。一、通路,回路。1、通路(回路)中顶点和边的交替序列——G0112llveveev,其中1(,)iiievv(无向图),或1,iiievv(有向图),——始点,0v——终点,称为到lv0vlv的通路。当0lvv时,为回路。一、通路,回路。2、简单通路,简单回路。简单通路(迹)简单回路(闭迹)复杂通路(回路)一、通路,回路。3、初级通路,初级回路。初级通路(路径)初级回路(圈)初级通路(回路)简单通路(回路),但反之不真。4、通路,回路的长度——中边的数目。例1、(1)图(1)中,从的通路有:到1v6v11125576vevevev21122334425576vevevevevevev31125564425576vevevevevevev…………长度3长度6长度6例1、(1)图(1)中,从的通路有:到1v6v11125576vevevev21122334425576vevevevevevev31125564425576vevevevevevev…………初级通路简单通路复杂通路例1、(2)12443322vevevev2255643322vevevevev3244332255643322vevevevevevevev…………长度3长度4长度7图(2)中过)有:的回路(从2v2v到2v例1、(2)12443322vevevev2255643322vevevevev3244332255643322vevevevevevevev…………初级回路(圈)初级回路(圈)复杂回路图(2)中过)有:的回路(从2v2v到2v5、图中最短的回路。如图:6、性质。定理:阶图中,若从顶点nivjv到存在通路()ijvv,则从ivjv到存在长度小于等于在一个的通路。1n推论:阶图中,若从顶点nivjv到存在通路()ijvv,则从ivjv到存在长度小于等于在一个的初级通路。1n6、性质。定理:阶图中,若niv到自身存在回路,则从到自身存在长度小于等于ivn的回路。在一个推论:阶图中,若niv到自身存在一个简单回路,则从到自身存在长度小于等于ivn的初级回路。在一个6、性质。由以上定理可知,在阶图中,n任何一条初级通路的长度任何一条初级回路的长度1nn二、图的连通性。1、连通,可达。无向图中,从到存在通路,称ivjv到ivjv是连通的(双向)。有向图中,从到存在通路,称ivjv可达ivjv(注意方向)。2、短程线,距离。短程线——连通或可达的两点间长度最短的通路。距离——短程线的长度,记,ijdVV(,)ijdVV无向图有向图2、短程线,距离。若之间无通路(或不可达),规定,ijvv(,),ijijdvvdvv距离满足:,ijdvv(1),时,等号成立。,0ijdvvijvv(2),,,ijjkikdvvdvvdvv若是无向图,还具有对称性,(,)(,)ijjidvvdvv。3、无向图的连通。为连通图——是平凡图,或都是连通的。GGG中任两点为非连通图——G中至少有两点不连通。G3、无向图的连通。设是一个无向图,是GRG中顶点之间的连通关系,则是等价关系。R设将划分成个等价类:R()VG(1)kk12,,,kVVV,由它们导出的子图12,,GVGV,kGV称为的连通分支,其个数记为G()pG4、有向图的连通。——中任一对顶点都互相可达D(双向)——中任一对顶点至少一向可达D——略去中有向边的方向后得到的无向图连通D连通强连通单向连通弱连通强连通单向连通弱连通例2、强连通单向连通例2、单向连通弱连通非连通图第三节图的矩阵表示内容:关联矩阵,邻接矩阵,可达矩阵。重点:1、有向图,无向图的关联矩阵,2、有向图的邻接矩阵。了解:有向图的可达矩阵。一、无向图的关联矩阵。1、设无向图,GVE12,,,nVvvv,,12,,,mEeee,的关联矩阵G()()ijnmMGm,01122()ijijijijjivemveveev与不关联其中与关联次与关联次即是以为端点的环例1、无向图(下图所示),求G()MG。1v2v3v4v1e2e3e4e5e1110001110()1001200000MG解:2、性质。12nijim(1)1()mijijmdv(2)(3)111112()mnnmnijijijiijimmmdv握手定理(4)10mijjm,当且仅当为孤立点。iv2、性质。(5)若第列与第列相同,则说明jk与jeke为平行边。二、有向图的关联矩阵。1、设无环有向图,DVE12,,,nVvvv,,12,,,mEeee,的关联矩阵D()()ijnmMDm,101ijijijijvemveve为的始点与不关联为的终点其中例2、有向图(下图所示),求D()MD。1100010111()0000101110MD解:2、性质。(1)10nijim(2)1()mijijmdv(3)110mnijjim三、有向图的邻接矩阵。1、设有向图,DVE12,,,nVvvv
本文标题:北大离散数学chap7
链接地址:https://www.777doc.com/doc-5196718 .html