图论GraphicTheory1.ppt

图论 Graphic Theory,阙夏制作,内容回顾,图论中著名的问题： 环球旅行问题到货郎问题； 四色猜想问题； Ramsey问题： Ramsey问题的描述； Ramsey问题的证明； 妖怪图(snark graph),内容回顾1,图的基本概念 有向图/无向图子图； 邻接度； 路径/简单路径/回路/简单回路； 连通/连通图/连通分量/连通有向图/强连通图； 两个结论： 握手定理； 握手定理的推论。,第一章 图的基本概念,1 引论 2 图的概念 3 道路和回路 4 图的矩阵表示法 5 中国邮路问题 6 平面图,思考：,(1)若有n个顶点的有向图G是强连通图，G中最少有几条弧才能保证其强连通性？ (2)若有n个顶点的无向图G是连通图，G中最少有几条边才能保证其极大连通性？ ,3 道路和回路,二、欧拉（Euler）回路,定义：对于连通的无向图G，若存在一简单回路，它通过G的所有边，则这回路称为G的Euler回路； 若图G中存在Euler回路，则称G为Euler图； 在图G中，若存在包含所有边的简单路径，则称这条路径为Euler道路(Euler tour)。,二、欧拉（Euler）回路1,定理：若连通无向图G所有顶点的度都是偶数，则存在一条图G的Euler回路(充要条件) 证明（反证法）： 设C=(e1=(v0,v1),e2=(v1,v2),em=(vm-1 ,v0)是图中最大的回路。 假设C不是Euler回路。则图G如下图所示：,二、欧拉（Euler）回路2, 图是连通的，则顶点不可能出现下面的情况：,图中任意结点的度均为偶数，有如下所示：,与假设矛盾， C是Euler回路。,二、欧拉（Euler）回路3,推论：如果连通图G只有两个度为奇数的顶点，则存在以这两个顶点为两端点，且包含G所有边的Euler道路。 补充：连通有向图存在Euler回路的充要条件是：每个顶点的入度出度。,欧拉回路求解方法,（Fleurys algorithm ）： (1)可从任一点出发去掉连接此点的一边。 (2)依序去掉相连的边但必须注意下列两条件： a、如果某边去掉后会导致某点无连通的边，则此顶点亦可去也。 b、去某边后不能造成图形的不连通。,例子11,例1-1：如果可能求出下图的一条Euler回路。,v1,v2,v5,v3,v4,v6,v7,v8,v9,例子11解答1,解：首先看图中是否有Euler回路，即看每个顶点的度是否都是偶数。 d(V1)=2， d(V2)=4， d(V3)=2， d(V4)=4， d(V5)=4， d(V6)=4， d(V7)=2， d(V8)=2， d(V9)=4。 所以存在Euler回路。 可以任意一个顶点为起点，这里以v2为起点:,v1,v2,v5,v3,v4,v6,v7,v8,v9,例子11解答2,依序去掉相连的边但必须注意下列两条件： a、如果某边去掉后会导致某点无连通的边，则此顶点亦可去也。 b、去某边后不能造成图形的不连通。,v1,v2,v5,v3,v4,v6,v7,v8,v9,例子11解答3,依序去掉相连的边但必须注意下列两条件： a、如果某边去掉后会导致某点无连通的边，则此顶点亦可去也。 b、去某边后不能造成图形的不连通。,v1,v2,v5,v3,v4,v6,v7,v8,v9,(1)先去掉(v2,v4),1,例子11解答4,依序去掉相连的边但必须注意下列两条件： a、如果某边去掉后会导致某点无连通的边，则此顶点亦可去也。 b、去某边后不能造成图形的不连通。,v1,v2,v5,v3,v4,v6,v7,v8,v9,1,2,(2)接着去掉(v4,v3),例子11解答5,依序去掉相连的边但必须注意下列两条件： a、如果某边去掉后会导致某点无连通的边，则此顶点亦可去也。 b、去某边后不能造成图形的不连通。,v1,v2,v5,v3,v4,v6,v7,v8,v9,1,2,(3)接着去掉(v3,v2),3,例子11解答6,依序去掉相连的边但必须注意下列两条件： a、如果某边去掉后会导致某点无连通的边，则此顶点亦可去也。 b、去某边后不能造成图形的不连通。,v1,v2,v5,v3,v4,v6,v7,v8,v9,1,2,3,例子11解答7,v1,v2,v5,v3,v4,v6,v7,v8,v9,1,2,3,4,5,6,7,8,依序去掉相连的边但必须注意下列两条件： a、如果某边去掉后会导致某点无连通的边，则此顶点亦可去也。 b、去某边后不能造成图形的不连通。,这时，如果去掉(v6,v5)将导致图不连通,例子11解答8,v1,v2,v5,v3,v4,v6,v7,v8,v9,1,2,3,4,5,6,7,8,9,10,11,12,13,14,V2-v4-v3-v2-v1-v4-v5-v9-v6-v8-v9-v7-v6-v5-v2,Euler回路：,从上例可知， Euler回路不唯一。,课堂练习,（1）下图所示能否产生Euler回路？如果可以找出一条Euler回路。,三、Hamilton回路,定义：若图G存在一条回路P，它通过G的每个顶点各一次又回到起点，则这回路称为G的Hamilton回路。 若图G中存在Hamilton回路，则称G为Hamilton图。 在图G中，若存在通过每个顶点各一次的道路，则称这条道路为Hamilton道路。,Hamilton定理,定理(充分条件) ：设简单图G的顶点数为n(n3)，若G中任意一对顶点vi、vj，恒有d(vi)+d(vj)n-1，则图G中至少有一条Hamilton道路。 推论(充分条件) ：若任意一对顶点vi、vj，恒有d(vi)+d(vj)n，则图G中至少有一条Hamilton回路。,Hamilton定理证明,下面证明Hamilton道路的存在。 证明：(1)先证明G是连通的。 假设G不连通，则G至少有两个连通分量。设其中一部分有n1个顶点，另一部分有n2个顶点。分别在两部分各选一个顶点v1、v2， G是简单图，所以： d(v1) n11 ，d(v2) n21， d(v1)+d(v2) n1 n2 2n1。 与假设d(vi)+d(vj)n-1矛盾，所以G连通。,Hamilton定理证明1,(2)再证明存在Hamilton道路： 假设G中有一条从v1到vL道路 T=(v1,v2,vL)是图中的最长道路，即起点v1和终点vL不和T之外的顶点相邻。 (a)如果Ln，即T是包含所有顶点的道路，即T是Hamilton道路，得证。 (b)若Ln且v1和vL相邻，则存在包含T的回路；,Hamilton定理证明2,若Ln且v1和vL不相邻，则根据条件d(vi)+d(vj)n-1，有如下图示：,所以存在包含T的回路。,Hamilton定理证明3,(c)证明存在比T更长的道路：,与假设矛盾，所以存在包含所有顶点的Hamilon道路。,则根据条件d(vi)+d(vj)n-1，有如下图示：,课后作业,1.试证明1