图论课件图论-1

离散数学图论,主讲教师：李欢lihuan,2,图论,主要内容,1.图论的基本概念2.通路问题3.图的矩阵表示4.欧拉图和哈密顿图5.二分图与图匹配6.树、有向树和有序树,第九章图的基本概念,3,图论,4,图论,图论已有二百多年历史(以Euler研究歌尼斯堡七桥问题为发端)。近四十年来发展十分迅速，成为一个新兴的数学分支。1、计算机科学中许多概念、算法需要图论支持(如二叉树)。2、为计算机应用建模提供数学工具3.2012年ACM两个最佳博士论文提名均涉及图理论HonorableMentionwinnerAleksanderMadry,nominatedbytheMassachusettsInstituteofTechnologyforhisdissertationFromGraphstoMatrices,andBack:NewTechniquesforGraphAlgorithms.HonorableMentionwinnerDavidSteurer,nominatedbyPrincetonUniversityforhisdissertationOntheComplexityofUniqueGamesandGraphExpansion.总而言之，“图论之为用大矣哉！”,The7BridgesofKonigsburg,Konigsburg(nowcalledKalingrad)isacityontheBalticSeawedgedbetweenPolandandLithuania.Ariverrunsthroughthecitywhichcontainsasmallisland.Thereare7bridgeswhichconnectthevariouslandmassesofthecity.,TheProblem,ThepeopleofKonigsburgmadeasportduringthe18thcenturyoftryingtocrosseachandeveryoneofthe7bridgesexactlyonce.Thiswastobedoneinsuchawaythatonewouldalwaysendupwhereonebegan.,GraphTheory-History,LeonhardEulerspaperon“SevenBridgesofKnigsberg”,publishedin1736.,Euler(pronounced“oiler”),Eulerwasoneofthegreatestmathematiciansofalltime.Hecontributedtovirtuallyeveryfieldofmathematicsthatexistedinhistime.Thepublicationofhiscollectedworks(OperaOmnia)ispresentlyuptovolume73andstillnotcomplete.,EulerandGraphTheory,EulerssolutiontotheKonigsburgbridgeproblemwasmorethanatrivialmatter.Hedidntjustsolvetheproblemasstated;hemadeamajorcontributiontographtheory.Indeed,heessentiallyinventedthesubject.Hiscontributionhasmanypracticalapplications.,Famousproblems,“Thetravelingsalesmanproblem”Atravelingsalesmanistovisitanumberofcities;howtoplanthetripsoeverycityisvisitedonceandjustonceandthewholetripisasshortaspossible?,Famousproblems,In1852FrancisGuthrieposedthe“fourcolorproblem”whichasksifitispossibletocolor,usingonlyfourcolors,anymapofcountriesinsuchawayastopreventtwoborderingcountriesfromhavingthesamecolor.Thisproblem,whichwasonlysolvedacenturylaterin1976byKennethAppelandWolfgangHaken,canbeconsideredthebirthofgraphtheory.,Examples,FlowofmaterialliquidflowingthroughpipescurrentthroughelectricalnetworksinformationthroughcommunicationnetworkspartsthroughanassemblylineInOperatingsystemstomodelresourcehandling(deadlockproblems)Incompilersforparsingandoptimizingthecode.,Examples,CostofwiringelectroniccomponentsShortestroutebetweentwocities.Shortestdistancebetweenallpairsofcitiesinaroadatlas.Matching/ResourceAllocationTaskschedulingVisibility/Coverage,14,图论,7.1图论的基本概念,15,图论,图论的基本概念,目的：了解图论的基本概念；重点：图论的基本概念；难点：度、图同构。,WhatisaGraph?,Informallyagraphisasetofnodesjoinedbyasetoflinesorarrows.,1,1,2,3,4,4,5,5,6,6,2,3,17,图论,无向图、有向图,AgraphGconsistsofafinitesetVofobjectscalledvertices,afinitesetEofobjectscallededges,andafunctionthatassignstoeachedgeasubsetv1，v2,wherev1andv2arevertices(andmaybethesame).设V和E是有限集合，且V如果：Ev1，v2v1且v2V，则称G=，为无向图。如果：EVV，则称G，为有向图。注意：E可为空零图一个E中元素可对应二个相同的V中元素自圈(自环）多个E中的元素可对应V中相同的二元素平行边,18,图论,无向图和有向图统称为图，其中V的元素称为图G的结点(顶点)，E的元素称为图G的边，图G的结点数目称为它的阶。Example:LetV=1,2,3,E=e1,e2,e3,e4,e5.Letbedefinedby(e1)=(e5)=1,2,(e2)=4,3,(e3)=1,3,(e4)=2,4Then,G=(V,E,)isagraph.,V:=1,2,3,4,5,6E:=1,2,1,5,2,3,2,5,3,4,4,5,4,6,20,图论,图的最本质内容：结点和边的对应关系。用几何图形表示图：小圆圈表示结点无向图：若(e)=v1，v2，就用一条连接结点v1和v2的无向线段表示边e有向图：若(e)v1，v2，就用一条由v1指向v2的有向线段表示边e,21,图论,关联、邻接结点和边的关系,设无向图G=，e，e1，e2E且v1，v2V如果(e)=v1，v2，则称e与v1(或v2)互相关联，e连接v1和v2，v1和v2既是e的起点，也是e的终点，也称v1和v2邻接。如果两条不同边e1和e2与同一个结点关联，则称e1和e2邻接。,22,图论,关联、邻接结点和边的关系,设有向图G=，eE且v1，v2V。若(e)=v1，v2，则称e连接v1和v2，e与v1(或v2)互相关联，分别称v1和v2是e的起点和终点，也称v1和v2邻接。,23,图论,自圈、平行边、简单图,设图G=，e1和e2是G的两条不同边。如果与e1关联的两个结点相同，则称e1为自圈(selfloop)；ii)如果(e1)=(e2)，则称e1与e2平行；如果图G没有自圈，也没有平行边，则称G为简单图(simplegraph)我们一般只讨论有限图。,24,图论,度,设v是图G的结点。如果G是无向图，G中与v关联的边和与v关联的自圈的数目之和称为v的度，记为dG(v)。如果G是有向图，G中以v为起点的边的数目称为v的出度，记为d(v)；G中以v为终点的边的数目称为v的入度,记为d(v)；v的出度与入度之和称为v的度，记为dG(v)。注意：在计算无向图中结点的度时，自圈要考虑两遍，因为自圈也是边。（例）每增加一条边，都使图中所有结点的度数之和增加2。,25,图论,定理7.1.1、定理7.1.2,定理7.1.1设无向图G=，有m条边，则vVdG(v)=2m证:因为每条边为图中提供次数均为2定理7.1.2设有向图G，有m条边，则vVdG(v)=vVdG(v)=m，且vVdG(v)=2m。,26,图论,奇结点、偶结点,度为奇数的结点称为奇结点；度为偶数的结点称为偶结点。,27,图论,任何无向图中都有偶数个奇结点。（Anundirectedgraphhasanevennumberofverticesofodddegrees.)Proof:LetV1andV2bethesetofverticesofevendegreeandthesetofverticesofodddegree,respectively,inanundirectedgraphG=(V,E)withmedges.Then2m=vVdeg(v)=vV1deg(v)+vV2deg(v),定理7.1.3,28,图论,孤立点、端点,度为0的结点称为孤立点；度为1的结点称为端点。,29,图论,定义以下特殊图：结点都是孤立点的图称为零图(Foreachintegern=1,weletDndenotethegraphwithnverticesandnoedges.WecallDnthediscretegraphonnvertices.)。D2：一阶零图称为平凡图。所有结点的度均为自然数d的无向图称为d度正则图(Regular)。设nI+，如果n阶简单无向图G是n-1度正则图，则称G为完全无向图（CompleteGraph)，记为Kn。Kn的边数m=n(n-1)/2。(Acompletegraphonnvertices,denotedbyKn,isasimplegraphthatcontainsexactlyoneedgebetweeneachpairofdistinctvertices.)设nI+，每个结点的出度和入度均为n-1的n阶简单有向图称为完全有向图。,零图、平凡图、d度正则图、完全图,30,图论,注意：1.完全图必是正则图，但正则图不一定是完全图。2.Dn零图也是正则图,31,图论,图的最本质内容：结点和边的关联关系。,32,图论,定义：设无向图G=V，E和G=V，E，如果存在双射函数:vv,并且当且仅当e=（ui，uj）E,有e=(ui)，(uj)E，则称G和G同构，记做G。(有向图的同构定义类似，只是边改为弧即可。）,同构,单射：指将不同的变量映射到不同的值的函数。满射：指陪域等于值域的函数。即：对陪域中任意元素，都存在至少一个定义域中的元素与之对应。双射（也称一一对应）：既是单射又是满射的函数。直观地说，一个双射函数形成一个对应，并且每一个输入值都有正好一个输出值以及每一个输出值都有正好一个输入值,33,图论,Ingraphtheory,thesimplegraphsG1=(V1,E1)andG2=(V2,E2)areisomorphicifthereexistsaone-to-oneandontofunctionffromV1toV2withthepropertythataandbareadjacentingraphG1ifandonlyiff(a)andf(b)areadjacentinG2,forallaandbinV1.Thiskindofbijectioniscommonlycalled“edge-preservin