大一各科课件-离散图论

主讲教 图论主要图论 2图论3图论图论1、计算机科学中许多概念、算法需要图论支持(如二叉树)2、为计算机应用建模提供数学工 提名均涉及图理HonorableMentionwinnerAleksanderMadry,nominatedbytheMassachusettsInstituteofTechnologyforhisdissertation"FromGraphstoMatrices,andBack:NewTechniquesforGraphAlgorithms."HonorableMentionwinnerDavidSteurer,nominatedbyPrincetonUniversityforhisdissertation"OnComplexityofUniqueGamesandGraph总而言之，图论之大矣哉4The7BridgesofKonigsburg(nowcalledKalingrad)isacityontheBalticSeawedgedbetweenPolandandLithuania.AriverrunsthroughthecitywhichcontainsasmallThereare7bridgeswhichconnectthevariouslandmassesofthecity.TheThepeopleofKonigsburgmadeasportduringthe18thcenturyoftryingtocrosseachandeveryoneofthe7bridgesexactlyonce.Thiswastobedoneinsuchawaythatonewouldalwaysendupwhereonebegan.GraphTheory-LeonhardEuler'spaperon“SevenBridgesofKönigsberg”,publishedinEuler(pronouncedEulerwasoneofthegreatestmathematiciansofallHecontributedtovirtuallyeveryfieldofmathematicsthatexistedinhistime.Thepublicationofhiscollectedworks(OperaOmnia)ispresentlyuptovolume73andstillnotEulerandGraphEuler’ssolutiontotheKonigsburgbridgeproblemwasmorethanatrivialmatter.Hedidn’tjustsolvetheproblemasstated;hemadeamajorcontributiontographtheory.Indeed,heessentiallyinventedthesubject.HiscontributionhasmanypracticalFamous“ThetravelingsalesmanAtravelingsalesmanistovisitanumberofcities;howtoplanthetripsoeverycityisvisitedonceandjustonceandthewholetripisasshortaspossible?FamousIn1852FrancisGuthrieposedthe“fourcolorproblem”whichasksifitispossibletocolor,usingonlyfourcolors,anymapofcountriesinsuchawayastopreventtwoborderingcountriesfromhavingthesamecolor.Thisproblem,whichwasonlysolvedacenturylaterin1976byKennethAppelandWolfgangHaken,canbeconsideredthebirthofgraphtheory.FlowofliquidflowingthroughcurrentthroughelectricalinformationthroughcommunicationpartsthroughanassemblyInOperatingsystemstomodelresourcehandling(deadlockIncompilersforparsingandoptimizingtheCostofwiringelectronicShortestroutebetweentwoShortestdistancebetweenallpairsofcitiesinaroadMatching/ResourceTaskVisibility/图论 图论的基本图论图论的基图论难点：度、图同构WhatisaInformallyagraphisasetofnodesjoinedbyasetoflinesorarrows.1245124536124536图论无向图、有向图论AgraphGconsistsofafinitesetVofobjectscalledvertices,afiniteEofobjectscallededges,andafunctionγthatassignstoeachasubset{v1，v2},wherev1andv2VE是有限集合，且V

arevertices(andmaybe Ψ：E｛｛v1，v2｝｜v1∈Ｖ且v2∈V｝，则称G=〈Ｖ，Ｅ，Ψ〉为无向图。如果Ψ：E→V×V，则称G＝〈Ｖ，Ｅ，Ψ〉为有向图。注意： E可为空 一个E中元素可对应二个相同的V中元 (自环图论图论图VG的(顶E的元素称为图G的边，图G的结点数目称为它的阶。Example:LetV={1,2,3},E={e1,e2,e3,e4,e5}.Letγbedefinedbyγ(e1)=γ(e5)={1,2},γ(e2)={4,3},γ(e3)={1,3},γ(e4)={2,4}Then,G=(V,E,γ)isa图论图论图的最本质内容：结点和边的对应关系用几何图形表示图 v小圆圈表示结 无向图Ψ(e)v1，v2}，就用一条连接结点v1和v2有向图Ψ(e)＝〈v1，v2〉，就用一条由v1指向v2的有向线段表示边e图论图论设无向G=〈Ｖ，Ｅ，Ψ〉，e，e1，e2∈E且 =｛v1，v2｝，则称e与v1(或v2)互相关联，e连接v1和v2，v1和v2既是e的起点，也是e的终v1v2邻接如果两条不同边e1和e2与同一个结点关联， e1和e2邻接。图论图论设有向图G=〈Ｖ，Ｅ，Ψ〉，e∈E且v1，v2∈V。若Ψ(e)=〈v1，v2ev1和v2，ev1(或v2)互相关联，分别称v1和v2是e的起点和终点，也称v1和v2邻接。图论自圈、平图论G〈Ｖ，Ｅ，Ψ〉，e1和e2Ge1e1为(selfΨ(e1Ψ(e2)，则称e1e2平行G没有自圈，也没有平行边G为简(simple v我们一般只讨论有限图 图论度图论vGG是无向图，Gv关联的边v关联的自圈的数目之和称为v的度，记为dG(v)。如果G是有向图，G中以v为起点的边的数目称为的出度Gv为终点的边的数目称为v的入度dＧ—v的出度与入度之和v的度dG(v)每增加一条边，都使图中所有结点的度数之和2图论定理7.1.1、定理图论 设无向图G=〈Ｖ，Ｅ，Ψ〉有m条边， v∈VdG(v)=2m证因为每条边为图中提供次数均为定理

设有向图G＝〈Ｖ，Ｅ，ΨdG＋(v) v∈VdG－(v)=m

mv∈VdG(v)=2m奇结点、偶结 图度为偶数的结点称为偶结点图论定理图论任何无向图中都有偶数个奇结点。

undirectedAngraphhasanevennumberofverticesofoddProof:LetV1andV2bethesetofverticesevendegreeandthesetofverticesofdegree,respectively,inanundirectedgraphG(V,E)withmedges.2m=v∈Vdeg(v)=v∈V1deg(v)+v∈V2deg孤立点、端 图度0的结称孤立点度1的结称端点图论零图、平凡图、d度正则图、完全图论结点都是孤立点的图称为零图(Foreachintegern>=1,weletDndenotethegraphwithnverticesandnoedges.WecallDnthediscretegraphonnvertices.)D2：一阶零图称为平凡图所有结点的度均为自然数d的无向图称为d度正则图(Regular)设n∈I+，如果n阶简单无向图G是n-1度正则图，则称G为完全无向图（CompleteGraph)，记为 Kn。Kn的边数m=n(n-1)/2。(Acompletegraphonnvertices,denotedbyKn,isasimplegraphthatcontainsexactlyoneedgebetweeneachpairofdistinct设n∈I+，每个结点的出度和入度均为n-1的n阶简单有向图称为完图论图论注意完全图必是正则图，但正则图不一定是完全Dn图论图论图论定义：设无向图G〈V，E〉和G′〈V′，E〉，如果存在双射函数ƒ:v→v′,并且当且仅当e=（ui，uj）E,有e′=(ƒ(ui，ƒ(ujE，则称GG′同构，记做GＧ。(有向图的同构单射：指将不同的变量映射到不同的值的函数满射：指陪域等于值域的函数。即：对陪域中任意元素，都存在至少一个定义域中与之对应图论Ingraphtheory,thesimplegraphsG1=(V1,E1)andG2=(V2,E2)areisomorphicifthereexistsaone-to-oneandontofunctionffromV1toV2withthepropertythataandbareadjacentingraphG1ifandonlyiff(a)andf(b)areadjacentinG2,forallaandbinV1.Thiskindofbijectioniscommonl