离散数学课件-第5章-5、6.ppt

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

1、1离散数学DiscreteMathematics汪荣贵教授合肥工业大学软件学院专用课件2011.06Chapter5graphtheory3CHAPTER5Graphs5.1IntroductiontoGraphs图的概述5.2GraphTerminology图的术语5.3RepresentingGraphsandGraphIsomorphism图的表示和图的同构5.4Connectivity连通性5.5EulerandHamiltonPaths欧拉通路和哈密顿通路5.6PlanarGraphsandGraphColoring平面图与着色5.7Trees树42021/9/15一、E

2、ulerPathsKonigsbergSevenBridgeProblem哥尼斯堡七桥问题CABD52021/9/15Terminologies:EulerCircuit图G里的欧拉回路是包含着G的每一条边的简单回路.EulerPath图G里的欧拉通路是包含着G的每一条边的简单通路EulerGraphAgraphcontainsanEulercircuit.判别定理：无向图G是欧拉图当且仅当G是连通图，且G中没有奇度顶点。(充要条件)证明（反证法）：设C=(e1=(v0,v1),e2=(v1,v2),…,em=(vm-1,v0))是图中最大的回路。假设C不是Euler回路。则图G如

3、下图所示：CC或∵图是连通的，则顶点不可能出现下面的情况：C∵图中任意结点的度均为偶数，∴有如下所示：C与假设矛盾，∴C是Euler回路。C82021/9/15NecessaryandsufficientconditionforEulercircuitandpaths欧拉回路和欧拉通路的充要条件【Theorem1】连通多重图具有欧拉回路当且仅当它的每个顶点都有偶数度Proof:Necessarycondition必要条件GhasanEulercircuitEveryvertexinVhasevendegreeConsidertheEulercircuit.thevertexawh

4、ichtheEulercircuitbeginswiththeothervertex92021/9/15(2)sufficientconditionWewillformasimplecircuitthatbeginsatanarbitraryvertexaofG.Buildasimplepathx0=a,x1,x2,…,xn=a.AnEulercircuithasbeenconstructedifalltheedgeshavebeenused.otherwise,ConsiderthesubgraphHobtainedfromG.Letwbeavertexwhichisthecom

5、monvertexofthecircuitandH.Beginningatw,constructasimplepathinH.102021/9/15【Theorem2】连通多重图具有欧拉通路而无欧拉回路，当且仅当它恰有两个奇数度顶点〖Example1〗KonigsbergSevenBridgeProblem哥尼斯堡七桥问题CABDSolution:Thegraphhasfourverticesofodddegree.Therefore,itdoesnothaveanEulercircuit.欧拉回路112021/9/15〖Example2〗Determinewhetherthefo

6、llowinggraphhasanEulerpath.Constructsuchapathifitexists.判断下图是否具有欧拉通路，如果存在构建一条通路BCDEFGHIJASolution:Thegraphhas2verticesofodddegree,andallofotherverticeshaveevendegree.Therefore,thisgraphhasanEulerpath.122021/9/15〖Example2〗DeterminewhetherthefollowinggraphhasanEulerpath.Constructsuchapathifitexi

7、sts.BCDEFGHIJASolution:Thegraphhas2verticesofodddegree,andallofotherverticeshaveevendegree.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)依序去掉相连的边但必须注