《图论GraphicTheory.ppt》由会员分享，可在线阅读，更多相关《图论GraphicTheory.ppt（29页珍藏版）》请在三一办公上搜索。
1、图论Graphic Theory,阙夏制作,内容回顾,图论中著名的问题：环球旅行问题到货郎问题；四色猜想问题；Ramsey问题：Ramsey问题的描述；Ramsey问题的证明；妖怪图(snark graph),内容回顾1,图的基本概念有向图/无向图子图；邻接度；路径/简单路径/回路/简单回路；连通/连通图/连通分量/连通有向图/强连通图；两个结论：握手定理；握手定理的推论。,第一章 图的基本概念,1 引论2 图的概念3 道路和回路4 图的矩阵表示法5 中国邮路问题6 平面图,思考：,(1)若有n个顶点的有向图G是强连通图，G中最少有几条弧才能保证其强连通性？(2)若有n个顶点的无向图G是连通图
2、，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如下图所示：,二、欧
3、拉（Euler）回路2,图是连通的，则顶点不可能出现下面的情况：,图中任意结点的度均为偶数，有如下所示：,与假设矛盾，C是Euler回路。,二、欧拉（Euler）回路3,推论：如果连通图G只有两个度为奇数的顶点，则存在以这两个顶点为两端点，且包含G所有边的Euler道路。补充：连通有向图存在Euler回路的充要条件是：每个顶点的入度出度。,欧拉回路求解方法,（Fleurys algorithm）：(1)可从任一点出发去掉连接此点的一边。(2)依序去掉相连的边但必须注意下列两条件：a、如果某边去掉后会导致某点无连通的边，则此顶点亦可去也。b、去某边后不能造成图形的不连通。,例子11,例1-1：如
4、果可能求出下图的一条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,
5、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、如果某边去掉后会导致某点无
6、连通的边，则此顶点亦可去也。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、去某边后不能造成图形的不
7、连通。,这时，如果去掉(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
8、图。在图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是简单图
9、，所以：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.试证明10人中必有3个人相互认识或4个人相互不认识，两者必居其一。,思考题1答案,(1)若有n个顶点的有向图G是强连通图，G中最少有几条边才能保证其强连通性？答：n条边，一个环。(2)若有n个顶点的无向图G是连通图，G中最少有几条边才能保证其极大连通性？答：n-1条边，即为一棵树的时候边数最少。,
