《离散数学》课件第十章

1、图 论（Graph Theory） 直观地表示离散对象之间的相互关系，研究它们的共性和特性解决具体问题ACDB1发展历史18世纪七桥问题(Euler 图)图论之父: 欧拉Euler2请你思考？如何找到物流运输的最优路径？如何找到最优的网络通信线路？如果你想周游全国所有城市，如何设计旅游线路？化学化合物分析：结构是否相同？程序结构度量：程序是否结构相似？如何为考试分配教室，使得资源利用率最优？如何安排工作流程而达到最高效率？如何设计为众多的电视台频道分配最优方案？如何设计通信编码以提高信息传输效率？操作系统中,如何调度进程而使得系统效率最优？3请你思考？如何设计集成电路线路布局而达到最优效率？如

2、何设计计算机鼓轮？七枚同重量硬币与一枚较轻的伪币，使用天平秤多少次就能找出伪币？如何设计下棋程序？n-皇后问题最少用几种颜色就能将世界地图都着色？如何使箱子尽可能装满物体？ 一个船夫要把一只狼，一只羊和一棵白菜运过河。问题是当人不在场时，狼要吃羊，羊要吃白菜，而他的船每趟只能运其中的一个。那么他怎样才能把三者都运过河呢？ 4研究主题旅行商问题：TSP问题中国邮路问题地图着色问题：四色定理最短路径问题网络流匹配组合优化E.W.Dijkstra（1930-2002）5七桥问题ACDBA view of Knigsberg showing the seven bridges over the Riv

3、er Pregel 6学习重点基本术语数学模型理论证明（构造性）了解应用“现在应该使图的概念渗入所有的数学教学，图表示了一个系统可能的状态以及连接这些状态的算子”B.Thwaites7主要内容第1讲 基本概念第2讲 Euler图与Hamilton图 第3讲 树第4讲 平面图与图着色第5讲 二分图与匹配8第1讲 基本概念 1 基本术语 2 几种重要类型的图、图的运算 3 图的基本性质 4 完全图、补图 5 图的同构 6 子图 7 图的连通性 8 图的表示910.2 图与图模型 例2 时间安排问题。某大学计算机学院的某教研组共有10名教师，他们分别参加7个班级的讨论课，每个班级可能同时需要多位教师

4、参加，有的教师可能需要参加多个班级的讨论，每个班级必须单独开展讨论课，则如何安排才使得所有班级在最短时间段内完成讨论课？参加各个班级讨论课的教师情况如下（ci为班级编号，数字1-10为教师编号）： c1=1，2，3，c2=1，3，4，5，c3=2，5，6，7，c4=2，6，7，c5=4，7，8，9，c6=8，9，10，c7=1，3，9，10。 1010.2 图与图模型 这样，一位教师如果给多个班级都授课，则在讨论课时间安排方面则不能冲突，如教师1不能同时参加班级c1与班级c2的讨论课。这种情况可以用下图直观地表示。 在上图中，共用了7个小圆圈来表示班级，圆圈之间的线段表示存在同一个教师参加该二

5、班级的讨论课，这样就不能安排该二班级同时开展讨论课。显然，这就给上述问题构建了一个直观的图的模型。 c6c5c4c2c3c7c111 1 基本术语图的简单表示：图G是一个有序二元组（V，E），其中V=v1，v2，vn是一个有限非空的集合。V中的元素称为G的结点，V称为图G的结点集，常记作V（G）； E是V中不同元素的无序偶(有序偶)的集合，E中的元素称为G的边，E称为图G的边集，常记作E（G）。无向图常简称为图(Graph)，记为G：G = (,) 若|V|=n,|E|=m，可记G为(n,m)图，G为n阶(Order)图。m表示图G的规模（Size）。1210.2 图与图模型 在图G中，若边集

6、E(G)=,则称G为零图（Null Graph），此时，又若G为n阶图，则称G为n阶零图，记作Nn，特别地，称N1为平凡图（Trivial graph）。在图的定义中规定结点集V为非空集，但在图的运算中可能产生结点集为空集的运算结果，为此规定结点集为空集的图为空图（Empty Graph），并将空图记为。阶为有限的图称为有限图(Finite Graph)，否则称为无限图(Infinite Graph)。结点没有标号的图称为非标号图（Unlabeled Graph），否则为标号图（Labeled Graph）。 1310.2 图与图模型 如果图中存在某两条边的端点都相同，则称该图为多重图(Mul

7、tigraph)，该两条边称为平行边。如果一条边关联的两个结点是相同的结点，则称该边为圈或自环(Loop)。不存在平行边与圈的图即称为简单图(Simple Graph)。 1410.2 图与图模型 定义10.2 如果uv是图G的边，记为e，即uvE(G),则称结点u和v邻接(Adjacent),否则称结点u与v非邻接。这里，也称结点u或v与边e是关联（Incident）关系。与同一个结点关联的两条边称为邻接边。与结点v关联的边数称为结点v的度，记作deg(v)。与结点v关联的环对v的度数的贡献要计算两次。如果结点v的度为0，则称之为孤立点(Isolated Vertex)。一度的结点称为悬挂点

8、（Pendant Vertex）。图G的所有结点度数的最小度数称为G的最小度，记作(G)，而所有结点度数的最大者称为G的最大度，记作(G)。各结点的度均相同的图称为正则图（Regular Graph）。各结点度均为k的正则图称为k-正则图。 1510.2 图与图模型 定义10.3 如果图的每条边是二结点构成的有序对，则该图称为有向图(Directed Graph)，上文所定义的图都是无向图(Undirected Graph)。有向图中边uv与vu是两条不同的边，对于边uv，称u为始点，v为终点。 有向图中，结点v的度分为入度，即与该结点相关联并以该结点为终点的边的数目，以及出度,即与该结点相关

9、联并以该结点为始点的边的数目,分别记作deg+(v)，deg-(v)。 1610.2 图与图模型v1v2e1e2v1v2e1e2无向图有向图17 1 基本术语环loop- (伪图)非简单图simple graph边e2(directed edge有向图)关联incident结点v1、v2，邻接adjacent结点vertex/vertices(结点)平行边/重边multiedge多重图multigraph多重图且伪图拟图(pseudograph)孤立点(isolated vertex)悬挂边(pendant edge)悬挂点(pendant vertex)分离边v3结点度degree为3,与3

10、个结点邻接，1出度2入度v3v1v2e1e218 2 几种重要类型的图图的类型：（1）有向图/无向图；简单图/多重图/伪图；零图，平凡图，空图；有限图/无限图；带权图、标记图；（2）特殊图：环图(Cn)、轮图(Wn)、立方图(Qn)、网格、正则图(r-图)；偶图(G(V1,V2), 二分图/二部图, Bipartite graph) 、完全偶图(Km,n)；（3）特殊图：子图、完全图、补图（4）特殊图：Euler图、Hamilton图、树图、平面图19 3 图基本性质定理10.1（欧拉定理） （1）图论第一定理（握手定理）：设 图G =为无向图或有向图，V=v1, v2, ,vn, |E|=m

11、(m为边数)则 d(vi) = 2m.推论:任何图(无向的或有向的)中,度为奇数的结点个为偶数.20示例 1 已知图G中有10条边,4个3度结点,其余结点的度数均小于等于2,问G中至少有多少个结点? 21 3 图基本性质（2）设有向图D =,V =v1, v2, ,vn, |E| = m, 则有 d (vi) = d (vi) = m. 22 4 完全图、补图完全图（Complete graph）、补图n阶无向完全图：设G =是n阶无向简单图,若G中任何结点都与其余的n1个结点相邻。记作Kn.n阶有向完全图：设D =为n阶有向简单图,若对于任意的结点 , u,vV (u v) ,既有有向边,又

12、有 示例 223 4 完全图、补图讨论：完全图性质设无向完全图G有n个结点，则G有n(n-1)/2条边。24 4 完全图、补图绝对补图，记为示例 325 5 子图子图(Subgraph)设G =,G =是两个图.若（1）V V,（2）E E,则称 G 是G的子图,G是 G 的超图（母图）,记作 G G.若G G且 G G(即 V V或 E E),则称 G 是G的真子图.若G G且 V V,则称 G 是G的生成子图.26 5 子图导出子图（Induced Subgraph） 设 V1V,且 V1 ,以 V1为结点集,以两端点均在V1中的全体边为边集的G的子图,称为结点集V1导出的导出子图.设 E

13、1 E,且 E1 ,以E1为边集,以E1中边关联的结点的全体为结点集G的子图,称为边集E1导出的导出子图.27 5 子图示例 8v1v2v1v4v1v2v2v4v3v1v2v3v2v1v3v3v2e4e5e4e5e1e3e2e4e1e3e1e3e1e3e2e1e4(1)(2)(3)(4)(5)(6)28 6 子图示例 9 画出完全图K5的含4条边的所有非同构的生成子图29 5 子图示例 10 画出有向完全图K4的含2条边的所有非同构的生成子图.30问题探讨请你思考一个州的立法机关由许多委员会组成某些资深的立法委员身兼数职，因而各委员会的委员互相交迭。说明怎样用图来描述这种委员会委员的互相交迭如

14、果委员会A有委员（编号）1，3，5，6；B有2，4，8，10；C有1，7，9；D有2，5，8；E有2，4，10；F有 11，12，13试绘出描述委员会委员互相交叠的图。田径赛的时间安排：假设某校的田径选拔赛共设六个项目的比赛，即跳高、跳远、标枪、铅球、100米和200米短跑，规定每个选手至多参加三个项目的比赛现有七名选手报名。如果已知选手报名情况，请设计一个比赛日程安排表，使得在尽可能短的时间内完成比赛31问题探讨假定有一个矩形国际象棋盘（代替标准的棋盘是否存在一连串符合规定的着法，使马可以从某个指定的方格走到另一个指定的方格 在一个足球赛季中，某足球联合会内每两队间比赛一次，假定每次比赛结束

15、后总有一方获胜（即无平局），如何用图来表示该比赛的结局，即确定比赛名次。 3210.3 路径与图连通性 图论中的许多概念和应用都与对图的遍历有关，即是从一个结点u出发，到达与之相邻接的结点，在从该邻接结点出发到达其邻接的结点，依次类推，最后可以到达图中的某结点v，从而就得到一条从u到v的通路。3310.3 路径与图连通性 如果通路上首尾结点相同，则称该通路是闭的(Closed)，否则称该通路是开的(Opened)。如果通路上没有相同的边，则称该通路为迹(Trail)，如果迹上的开始结点与结束结点相同，则称之为回路(Circuit)，如果回路上除了开始结点与结束结点没有相同的结点，则称之为环(C

16、ycle)。如果通路上没有相同的结点，则称该通路为路或路径(Path)，有n个结点的路常记作Pn。 3410.3 路径与图连通性 通路遍历过的边的数目为通路的长度，如果通路长度为0，则称之为平凡通路（Trivial Walk）。两结点u，v间的路可能不只一条，将其中的最短的路称为u，v间的距离。3510.3 路径与图连通性 定理10.2 如果图G上存在一条u-v通路，则必然存在一条u-v路；如果G上存在一条闭通路，则必然存在一条回路(环)。 这是因为，如果通路上存在相同的结点vi,vj，则可将vi,vj之间的一段通路删除，并合并vi，vj为一个结点，从而得到一条更短的u-v通路。如果所得到的u

17、-v通路上还存在相同的结点，则可以依此继续执行删除操作，最终一定可以得到一条没有相同结点的u-v通路，也就是一条u-v路。类似地，如果G上存在一条闭通路，则必然存在一条回路（环）。 3610.3 路径与图连通性例10.11 在右图中，1) 找出一条包含图所有结点的通道；2) 找出一条包含图所有结点的迹； 3) 找出所有a-d路，并求出其长度；4) 找出图中所有的环。解 1) 包含图所有结点的不是迹的通道：aebcaebd。2) 包含所有结点的迹：beacbd。3) a-d路：aebd,acbd,长度均为3。4) 环：acbea，长度为4。abedc3710.3 路径与图连通性 例10.12 每

18、个结点的度数至少为2的图必包含一个回路。 证明 设P是图G中最长路经中的一条，并设其长度为m, P的一个端点为u。考察G中与u关联的边，由于G中每个结点的度至少为2，故u必关联一条不在P上的边e，从而e的另一个端点v必然在P上，否则，将这个结点加入P上，则可以得到更长的路。于是，P上u到v的的路与边e构成回路。 uvP3810.3 路径与图连通性 练习4 已知关于a,b,c,d,e,f,g的下述事实： a说英语； b说英语和西班牙语； c说英语、意大利语和俄语； d说日语和西班牙语； e说德语和意大利语； f说法语、日语和俄语； g说法语和德语； 试问：上述7人中是否任意两人都能交谈（如果必要

19、，可由其余5人中所组成的译员链帮忙？）39407 图的连通性讨论1 Dijkstra算法输入：一个带权图G，G的任意两个结点间有路径存在，G中任意边(v,x)的权值w(v,x)0；结点a与z输出：L(z)，从结点a到z的最短路径长度1 Procedure Dijkstra(G)2 For 所有结点xa 3 L(x)=; 4End for;5 L(a)=0;6 T=V(G);7S=;8 While(zT)9 从T中找出具有最小L(v)的结点v;10 For 所有与v相邻的结点uT11 L(u)=minL(u),L(v)+w(v,u)12 End For13 T=T-v;14 S=Sv;15 En

20、d While16 End Procedure41 ()()()()()(0) v1 v2 v3 v4az42(4)(2)()()()(0) v1 v2 v3 v4az43(3)(2)(10)(12)()(0) v1 v2 v3 v4az44(3)(2)(8)(12)()(0) v1 v2 v3 v4az45(3)(2)(8)(10)(14)(0) v1 v2 v3 v4az46(3)(2)(8)(10)(13)(0) v1 v2 v3 v4az47(3)(2)(8)(10)(13)(0) v1 v2 v3 v4az48 10.3 路径与图连通性 定义10.5 如果图G中结点u到v有一条路径，

21、则称结点u到v是可达的（Accesible）或连通的（Connected）。结点u到其自身也定义为连通的。 定义10.6 如果图G的任何两个结点都是相互可达的，称G是连通的（Connected）,并称G为连通图(Connected Graph)。有向连通图 弱连通、单向连通、强连通图4910.3 路径与图连通性 容易判断，强连通图必定是单向连通图，单向连通图必定是弱连通图。 例10.14 下图中，(a)为连通图，(b)为由两个连通分支的非连通图，c为强连通图，d为单向连通图，e为弱连通图。 a b c d e5010.3 路径与图连通性 若将图中两个结点间的连通性看作图的结点间的一种关系，容易

22、判定图中两个结点间的连通性是一个等价关系，因为结点u到u是连通的满足自反性；若u到v是连通的，则v到u也是连通的，满足对称性；若u到v连通，v到w连通，则u到w存在一条通路，从而存在一条u到w的路径，故u到w是连通的，满足传递性。但对于有向图，结点间的连通性不满足对称性，是偏序关系。 5110.3 路径与图连通性 现在可以利用结点的连通性对图G的结点集进行划分，于是利用这个划分可以得到G的多个连通子图，如 Gv=(Vv,Ev), 称Gv为G的连通分支或连通分图（Connected Component）,也称为极大连通子图。 52 10.3 路径与图连通性讨论：连通图有关性质1 （定理10.3）

23、设G是一(n，m)图，G有个分图，则 n-m(n-)(n-+1)/22 二分图G中无长度为奇数的环。3 有向图D强连通 D中有闭通路过每个结点至少一次.4 有向图D单向连通 D中有通路过每个结点至少一次.53 7 图的连通性3 证明: () 显然 () 设V(D)=v1,v2,vn, 设i,j是从vi到vj的有向路径, 则1,2+2,3+n-1,n+n,1是过每个结点至少一次的闭通路. 思考：进一步地，一定存在满足条件的环？请举例。5410.3 路径与图连通性 练习5在任何n (n2)个顶点的简单图G中，至少有两个顶点具有相同的度。 证明 如果G有两个或更多孤立顶点，那么它们便是具有相同的度的

24、两个顶点。 如果G恰有一个孤立顶点，那么我们可对有n1 个顶点但没有孤立顶点的G（它由G删除孤立顶点后得到）作讨论；如果G有分图，则也可以直接对分图进行讨论。因此，不妨设G没有孤立顶点，那么G 的n个顶点的度数应是：1，2，3，n1 这n1种可能之一，显然，必定有两个顶点具有相同的度。5510.3 路径与图连通性 练习6给定简单图G=，且|V|=n，|E|(n-1)(n-2)/2，试证G是连通图。试给出|V|=n，|E|=(n-1)(n-2)/2的简单无向图G=是不连通的例子。 5610.3 路径与图连通性 定义10.9 设S为图G的结点集V的子集，称S为G的点割集（Cut Set of Ve

25、rtex）,如果从G中删除S中的所有结点后G的连通分支数增加，但S的任何真子集均无这一特性。当点割集为单元素集合v时，v称为割点（Cut Vertex）。 设S为连通图G边集E的子集，称S为G的边割集（Cut set of Edge），如果从G中删除S的所有边后G的连通分支数增加，但S的任何真子集均无这一特性。当割集为单元素集e时，称e为桥(Bridge)或割边（Cut Edge）。 5710.3 路径与图连通性 例10.17 下图中的图有点割集1，5，2，3是割点，而4，7不是点割集。e1,e3,e4,e5,e6,e8等均是边割集，e9是割边。126735e1e3e2e4e7e8 e64e9

26、e55810.3 路径与图连通性 例10.18 试证明：图G的任一边，若其不是割边，则必出现于G的某一环里。 证明 设图G的边e=(vi，vj)不是分割边，去掉e后，与vi相连接的接点集为V1，与vj相连接的结点集为V2，由割边定义知，V1V2。因而存在一结点vV1V2，使得在去掉e后，vi与v有路相连，v与vj有路相连。于是vi与vj有路相连接，因而必存在一条连接vi与vj的路P=vi，v1，v2，v，vj，从而P与边(vi，vj)组成一个环。 5910.3 路径与图连通性 定义10.10 图G的点连通度（Vertex Connectivity）是指把G变成非连通图或平凡图至少要删除的结点数

27、，记作(G) (读作卡帕)。定义中的平凡图主要针对G为完全图时而言的，因为完全图无论删除多少结点都不会变得不连通。根据定义，(G)可以具体定义如下：(G)= 6010.3 路径与图连通性 类似地，有边连通度的定义。G的边连通度（Edge Connectivity）是指把G变成非连通图或平凡图至少要删除的边数，记作(G)。根据定义，当G为非连通图或为K1时(G)=0。 例10.17中图的点连通度为1，边连通度为1。 显然，点（边）连通度越小，图的连通性越脆弱。 6110.3 路径与图连通性 令(G)表示图G中结点度数的最小值（常称图G的最小度），那么我们有以下定理。 定理10.4 对于图G，有下

28、面不等式成立： (G)(G)(G) 从直观上看，图的连通度应当与图中任两点之间的路的条数有关。连通度越高，连接两点的路应当越多。 6210.3 路径与图连通性 定义10.11 设G=(V，E)是连通图，SV，u，vV。若在G-S中u，v不可达，则称S分离u，v。设FE，若在G-F中u，v不可达，则称F分离u，v。 定理10.5 在一个连通(p，q)图中，分离两个不相邻接的点u，v的点集中，点的最少数目等于连接u，v的不相交的路的最多数。 6310.3 路径与图连通性 证明 设G=(p，q)，u，v是G中任二不相邻的结点，且分离u，v的点集至少有k个点，连接u，v的不相交的路(点不相重)共有m条

29、。 1) 因为连接u，v的不相交的路共有m条，这m条路除端点外无公共点，所以要分离u，v，至少要从每一条路上去掉一个点，即mk。 2) 若分离u，v的点集中至少要k个点，而连接u，v的路共有m条，则只要在这m条互不相交的路上各取一点，即可组成一个由m个点组成的点集S，S分离u，v。所以km。 由(1)、(2)结论可得k=m。证毕。 6410.3 路径与图连通性 定理10.6 若u，v是图G中两个不同的点，G中连接u，v的边不相交的路的最多数目，等于分离u，v的边集中边的最少数目。 以上两个定理属于Menger定理的图论形式。Menger定理具有普遍意义，它的图论形式还有多种。并且，在其它领域中

30、，类似的定理也被一再发现。例如，网络最优化理论中有名的最大流最小割定理、集族理论中的霍尔定理、格论中关于有限格中不可比元素的数目等于包含所有元素的链集中链的最少数的定理，等等。这些定理从不同领域中发现，相互之间有着内在联系，它们都是Menger定理的变形。 65 10.5 图的同构图的同构定义10.12 设(有向)图G1=, G2=, 若存在双射 f:V1V2, 满足 uV1,vV1, (u,v)E1 (f(u),f(v)E2(E1 E2)则称G1与G2同构, 记作G1G266 10.5 图的同构示例 5(1)(2)(3)(4)(5)(6)abcdev1v2v3v4v567 10.5 图的同构

31、示例 6G1G2G3G1G3, G1G268 10.5 图的同构示例 7G1G2G3G1G2G369 10.5 图的同构示例 7G1G2G3G1G2, G2G370 10.5 图的同构示例 9 画出完全图K5的含4条边的所有非同构的生成子图71 10.5 图的同构思考：（1）画出4个结点3条边的所有可能非同构无向简单图；（2）画出3个结点2条边的所有可能非同构的有向简单图;（3）如何判定两个图不同构？72 10.5 图的表示图的矩阵表示图的表示的三种方法：（1）集合表示（2）邻接表（adjacency list）表示（3）矩阵（ matrix）表示 1、邻接矩阵（adjacency matri

32、x）表示 2、关联矩阵（incidence matrix）表示7310.5 图的表示示例 邻接矩阵及其应用aedcbA(G)= ca b c d eA(G)2=7410.5 图的表示定理10.7 如果A是一个图G的邻接矩阵，那么An（n=1，2，3，）中元素(ij)等于从结点i到结点j的长度为n的通路的数目。7510.6 欧拉图 Euler Graph定义：欧拉图:图中存在一条经过每条边一 次且仅一次的回路。欧拉路：经过图中每边一次且仅一次的通路。7610.6 欧拉图 Euler Graph哥尼斯堡七桥问题7710.6 欧拉图 Euler Graph781 欧拉图哥尼斯堡七桥问题 寻找走遍哥尼

33、斯堡（Knigsberg）城的七座桥一次且仅一次最后又回到原出发点的路是否存在.研究方法抽象 将哥尼斯堡七桥问题抽象为一个数学问题.791 欧拉图A view of Knigsberg showing the seven bridges over the River Pregel CADB？ABCD802 欧拉图的判定欧拉图判定定理 图G具有一条欧拉回路（即G为欧拉图），当且仅当G是连通的，并且所有结点度数均为偶数。812 欧拉图的判定A view of Knigsberg showing the seven bridges over the River Pregel CADB822 欧拉图的

34、判定示例 请判断下列各图中，哪些是欧拉图？832 欧拉图的判定欧拉图判定定理的证明v0构造法842 欧拉路的判定 图G具有一条欧拉路，当且仅当G是连通的，且有零个或两个奇数度结点。两个奇数度结点是欧拉路的两个端点。853 欧拉图的应用 1 一笔画问题 示例2 试问下列各图能否一笔画出？ 请你思考：完全图Kn可以几笔画出？863 欧拉图的应用2 “街道清扫车”小区大门873 欧拉图的应用2 “街道清扫车”小区大门21883 欧拉图的应用推广之：中国邮路问题 一个邮递员从邮局出发，到所管辖的街道投递邮件，最后返回邮局，若必须走遍所辖各街道中每一条至少一次，则怎样选择投递路线使所走的路程最短？ 89

35、3 欧拉图的应用我国的数学家管梅谷教授，于1962年写出了论文解决了这一问题，被国际数学界称之为中国邮路问题。它的解题思路大体包括三个方面：第一 若G没有奇数度结点，则G是欧拉图，于是欧拉回路C是唯一的最小长度。第二 若G恰有两个奇数度结点vi和vj，则G具有欧拉路，且邮局位于结点vi，则邮递员走遍所有的街道一次到达结点vj；从vj返回vi可选择其间的一条最短路径。这样，最短邮路问题转化为求vi到vj的欧拉路和vj到vi的最短路径问题。第三 若G中奇数度结点数多于2，则回路中必须增加更多的重复边(路径）。这时，怎样使重复边的总长度最小？有定理给出了判断条件。 904 有向欧拉图有向欧拉回路（迹

36、）: 给定有向图G，通过图中每边一次且仅一次的一条有向回路(迹)。存在有向欧拉回路（迹）的图即有向欧拉图（有向半欧拉图）。判定？有向图G为有向欧拉图，当且仅当G是连通的，且每个结点入度等于出度。一个有向图G为有向半欧拉图，当且仅当它是连通的，而且除两个结点，每个结点入度等于出度，但这两个结点中，一个结点的入度比出度大1，另一个结点的入度比出度小1。914 有向欧拉图计算机鼓轮的设计 设有旋转鼓轮其表面被等分成24个部分。 其中每一部分分别用绝缘体或导体组成，绝缘体部分给出信号0，导体部分给出信号1，图中阴影部分表示导体，空白部分表示绝缘体，根据鼓轮的位置，触点将得到信息1101，如果鼓轮沿顺时

37、针方向旋转一个部分，触点将有信息1010。 问鼓轮上16个部分怎样安排导体和绝缘体，才能使鼓轮每旋转一个部分，四个触点能得到一组不同的四位二进制数信息。924 有向欧拉图的应用每个结点的入度等于2，出度等于2，故在图中必可找到一条欧拉回路如e0e1e2e4e9e3e6e13e10e5e11e7e15e14e12e8根据邻接边的标号记法，这16个二进制数可写成对应的二进制数序列 0000100110101111把这个序列排成环状，即与所求的鼓轮相对应. 0100101101010193小结与作业小结1 欧拉图2 欧拉图的判定3 应用作业 习题 26、27 构造法94哈密尔顿图Hamilton G

38、raph95主要内容 1 哈密尔顿图2 哈密尔顿图判定定理3 建模：哈密尔顿图应用重点难点：哈密尔顿图判定定理961 哈密尔顿图几个问题在一个大城市，有很多取款机，那么，如何制定出一个最优的路线，使运钞车过每个提款机一次就能运送完钱钞？ 货郎担问题旅行商人问题 (Traveling Salesman Problem ,TSP) 优化算法近似解演化算法运筹学、计算机科学和编码理论中的很多问题都可以转化为哈密尔顿图问题 971 哈密尔顿图几个问题在一个大城市，有很多取款机，那么，如何制定出一个最优的路线，使运钞车过每个提款机一次就能运送完钱钞？ 货郎担问题旅行商人问题(TSP)考虑在七天内安排七门

39、课程的考试，要求同一位教师所任教的两门课程考试不安排在接连的两天里，如果教师所担任的课程都不多于四门，则是否存在满足上述要求的考试安排方案？ 时间表问题国际象棋的跳马是否可以遍历其棋盘，即从任一格出发跳到每一格仅一次并最后回到出发的棋盘格子？在一个至少有5人出席的圆桌会议上（会议需要举行多次），为达到充分交流的目的，会议主持者希望每次会议每人两侧的人均与前次不同，这是否可行？请应用图论知识进行论证。 周游世界问题981 哈密尔顿图问题 1859年爱尔兰数学家威廉哈密尔顿（Sir William Hamilton）发明了一个小游戏玩具：一个木刻的正十二面体，每面系正五角形，三面交于一角，共有20

40、个角，每角标有世界上一个重要城市。哈密尔顿提出一个问题：要求沿正十二面体的边寻找一条路通过20个城市，而每个城市只通过一次，最后返回原地。哈密尔顿将此问题称为周游世界问题。游戏) 求解 抽象为图论问题 哈密尔顿给出了肯定回答，该问题的解是存在的哈密尔顿回路(圈)哈密尔顿图991 哈密尔顿图2002年“离散数学与计算机科学研究中心”在福州大学成立范更华教授获2005年度国家自然科学奖二等奖 研究主题：哈密尔顿圈及圈覆盖理论 “范定理” ( “范条件”、“范类型”)1001 哈密尔顿图范更华：歪打正著学了图论 灵光一闪发现定理科学中国人（2005）年度人物哈密尔顿圈问题是图论最古老的研究课题之一，

41、是至今未解决的世界难题，在许多领域有着重要应用。经过多年艰苦攻克，范更华的这一项目在这一问题的研究上开辟 了一条新的途径，证明若图中每对距离为2的点中有一点的度数至少是图的点数的一半，则该图存在哈密尔顿圈。了此成果引发了大量后续工作，以“范定理”、“范 条件”、“范类型”被广泛引用而出现于多种国际权威学术刊物，并作为定理出现在国外的教科书中。 新华网 2006.1.101011 哈密尔顿图哈密尔顿回路(H-回路): 一条经过图G中的每一个结点恰好一次的回路(环)哈密尔顿图(Hamilton Graph, H-图): 具有哈密尔顿回路的图哈密尔顿路(H-路): 一条经过图G中的每一个结点恰好一次

42、的路(通路)半哈密尔顿图1021 哈密尔顿图示例 请判断下列各图中，哪些是哈密尔顿图？（a） (b) (c) abcde1031 哈密尔顿图哈密尔顿图性质若图G=(V，E) 具有哈密尔顿回路，则对于结点集V的每一个非空子集S均有(GS)|S|成立。其中(GS)是GS中连通分支数。哈密尔顿图的必要条件也是判定非哈密尔顿图的充分条件1041 哈密尔顿图88马图(能否遍历是否是H图?)跳马的步数1-64，构成一个幻 方 1051 哈密尔顿图 44马图 55马图1062 哈密尔顿图判定定理(充分条件)定理10.10 设图G为具有n(n3)个结点的简单无向图，1 如果G的每一对结点的度数之和都不小于n1

43、，那么G中有一条哈密尔顿通路； 2 如果G的每一对不相邻结点的度数之和不小于n，那么G为一哈密尔顿图。 “范定理”:若图中每对距离为2的结点中有一结点的度数至少是图的结点数的二分之一，则该图存在哈密尔顿回路(环/圈)。1072 哈密尔顿图判定定理判定定理1的证明首先，G是连通的? 若G有两个或更多互不连通的分图，设一个分图有n1个结点，任取一个结点v1，设另一个分图有n2个结点，任取一个结点v2，由 d(v1)n11，d(v2)n21，有 d(v1)+ d(v2) n1+ n22n1，这表明与题设矛盾，故G必连通。108其次，G有哈密尔顿通路？ 只要在G中构造出一条长为n1的H-通路即可得证。

44、 为此，不妨令P为G中任意一条长为p1(pn)的H-通路，设其结点序列为v1，v2，vp。反复应用下面方法来扩充这一通路，直到P长度为n-1： 1）如果有v v1，v2，vp，它与v1或vp有边相关联，那么可立即扩充P为长度为p的通路。 2）如果v1，vp均只与原通路P上的结点相邻，则首先证明：G中有一条包含v1，v2，vp，长度为p的回路。 2.1) 如果v1与vp相邻，则回路已找到。否则2 哈密尔顿图判定定理1092 哈密尔顿图判定定理 2.2) 如果v1与vi1 ,vi2 , ,vir相邻，1i1，i2, , irp, 考虑vp： 若vp不与vi1-1 ,vi2-1 , , vir-1中

45、任何一个相邻，则deg(vp)p-r-l， 因而 deg(v1)+deg(vp)r+prl=p1n1，与题设矛盾， 因此 vp与vi1-1 ,vi2-1 , , vir-1之一, 例如vi1-1相邻， 于是,可得到包含v1，v2，vp 的回路：（v1，v2，vi1-1 ,vp , vp -1 , ，vi1 , v1）如图所示。v1vpv2vi-1vi1102 哈密尔顿图判定定理考虑G中这条包含v1，v2，vp长度为p的回路。 由于pn，故必有回路外结点v与回路上结点(例如vk)相邻，如图所示，可以得到一条长度为p的、包含v1，v2，vp的通路：(v, vk ,vk-1, v1,vi1 ,vi1

46、+1, vp ,vi1-1 , vk+1)。v1vpv2vkvk+1vvi-1vi1112 哈密尔顿图判定定理请你思考 如何证明判定定理2？1 按照上述证明方法？2 其它方法，如教材方法？构造法反证法1122 哈密尔顿图判定定理练习 1 结点数目不少于3的完全图都是哈密尔顿图？ 2 哈密尔顿图中的哈密尔顿回路未必是唯一的吗？ 3 每个结点度数均不小于n/2的图是哈密尔顿图（n为图的结点数）？ 4 前述判定定理给出的条件只是充分条件，不是必要条件。请举例说明之。 5 设G为（n，m）图。请证明：如果 ，那么G为哈密尔顿图。 1133 哈密尔顿图应用举例 问题 考虑在七天内安排七门课程的考试，要求

47、同一位教师所任教的两门课程考试不安排在接连的两天里，请应用有关图论性质证明：如果教师所担任的课程都不多于四门，则存在满足上述要求的考试安排方案.分析设G为七个结点的图，每一个结点对应一门功课的考试，如果这两个结点对应的考试课程是由不同教师担任的，那么这两个结点之间有一条边，因为每个教师所任的课程不超过4，故每个结点的度数至少是3，任两个结点度数的和至少是6，故根据定理，G总包含一条哈密尔顿路，它对应于一个七门考试课目的一个适当安排。114小结与作业小结1 哈密尔顿图2 哈密尔顿图的判定作业 习题 28、29 反证法构造法115补充例题1 右图是一个迷宫,其中数字表示通道、和死胡同(包括目标) 。请用一个图来表示这个迷宫(用结点表示通道、和死胡同(包括目标),用边表示