离散数学课件第5章

《离散数学课件第5章》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、1离散数学DiscreteMathematics汪荣贵教授合肥工业大学软件学院专用课件2011.06Chapter5graphtheory3CHAPTER5Graphs5.1IntroductiontoGraphs图的概述5.2GraphTerminology图的术语5.3RepresentingGraphsandGraphIsomorphism图的表示和图的同构5.4Connectivity连通性5.5EulerandHamiltonPaths欧拉通路和哈密顿通路5.6PlanarGraphsandGraphColo

2、ring平面图与着色5.7Trees树42021/10/8一、EulerPathsKonigsbergSevenBridgeProblem哥尼斯堡七桥问题CABD52021/10/8Terminologies:EulerCircuit图G里的欧拉回路是包含着G的每一条边的简单回路.EulerPath图G里的欧拉通路是包含着G的每一条边的简单通路EulerGraphAgraphcontainsanEulercircuit.判别定理：无向图G是欧拉图当且仅当G是连通图，且G中没有奇度顶点。(充要条件)证明（反证法）：设C=

3、(e1=(v0,v1),e2=(v1,v2),…,em=(vm-1,v0))是图中最大的回路。假设C不是Euler回路。则图G如下图所示：CC或∵图是连通的，则顶点不可能出现下面的情况：C∵图中任意结点的度均为偶数，∴有如下所示：C与假设矛盾，∴C是Euler回路。C82021/10/8NecessaryandsufficientconditionforEulercircuitandpaths欧拉回路和欧拉通路的充要条件【Theorem1】连通多重图具有欧拉回路当且仅当它的每个顶点都有偶数度Proof:Necessar

4、ycondition必要条件GhasanEulercircuitEveryvertexinVhasevendegreeConsidertheEulercircuit.thevertexawhichtheEulercircuitbeginswiththeothervertex92021/10/8(2)sufficientconditionWewillformasimplecircuitthatbeginsatanarbitraryvertexaofG.Buildasimplepathx0=a,x1,x2,…,xn=a.

5、AnEulercircuithasbeenconstructedifalltheedgeshavebeenused.otherwise,ConsiderthesubgraphHobtainedfromG.LetwbeavertexwhichisthecommonvertexofthecircuitandH.Beginningatw,constructasimplepathinH.102021/10/8【Theorem2】连通多重图具有欧拉通路而无欧拉回路，当且仅当它恰有两个奇数度顶点〖Example1〗Konigsbe

6、rgSevenBridgeProblem哥尼斯堡七桥问题CABDSolution:Thegraphhasfourverticesofodddegree.Therefore,itdoesnothaveanEulercircuit.欧拉回路112021/10/8〖Example2〗DeterminewhetherthefollowinggraphhasanEulerpath.Constructsuchapathifitexists.判断下图是否具有欧拉通路，如果存在构建一条通路BCDEFGHIJASolution:Theg

7、raphhas2verticesofodddegree,andallofotherverticeshaveevendegree.Therefore,thisgraphhasanEulerpath.122021/10/8〖Example2〗DeterminewhetherthefollowinggraphhasanEulerpath.Constructsuchapathifitexists.BCDEFGHIJASolution:Thegraphhas2verticesofodddegree,andallofotherve

8、rticeshaveevendegree.Therefore,thisgraphhasanEulerpath.TheEulerpath:A,C,E,F,G,I,J,E,A,B,C,D,E,G,H,I,G,J欧拉回路求解方法（Fleury‘salgorithm）：(1)可从任一点出发去掉连接此点的一边。(2)依序去掉相连的边但必须注