第六章第六章 图图 论论 Graphs图/Graph： 可直观地表示离散对象之间的相互关系，研讨它们的共性和特性，以便处理详细问题。6.1 图的概述/Introduction of Graph6.2 图的术语/Graph Terminology6.3 图的表示与同构/ Representing Graph and Graph Isomorphism6.4 连通性/Connectivity6.5 欧拉通路与哈密顿通路 / Euler and Hamilton Paths6.6 最短通路问题/Shortest Path Problem6.7 平面图/Planar Graphs6.8 图的着色/Graph Coloring学习内容6.5 欧拉通路与哈密顿通路欧拉通路与哈密顿通路 Euler and Hamilton PathKonigsberg(哥尼斯堡哥尼斯堡)七桥问题七桥问题问题：能否从河岸或小岛出发，经过每一座桥，而且仅仅经过一次回到原地。 Euler(欧拉)1736年对这个问题，给出了否认的回答。将河岸和小岛作为图的顶点，七座桥为边，构成一个无向多重图，问题化为图论中简单回路的问题：6.5 欧拉通路与哈密顿通路欧拉通路与哈密顿通路 Euler and Hamilton Path定义定义1欧拉通路回路：欧拉通路回路： G=(V,E)，称包含，称包含E中一切边的简单通路为欧拉通中一切边的简单通路为欧拉通路路/Euler Path/E通路。通路。 包含包含E中一切边的简单回路为欧拉回路中一切边的简单回路为欧拉回路/Euler Circuit/E回路。回路。注：包含欧拉回路的图称为欧拉图注：包含欧拉回路的图称为欧拉图/E图图6.5 欧拉通路与哈密顿通路欧拉通路与哈密顿通路 Euler and Hamilton Path例1 图中能否存在欧拉回路？假设无，存在欧拉通路？6.5 欧拉通路与哈密顿通路欧拉通路与哈密顿通路 Euler and Hamilton PathG1存在欧拉回路 eabedceG2不存在欧拉回路和欧拉通路 G3存在欧拉通路 adcabdeb例2 图中能否存在欧拉回路？假设无，存在欧拉通路？6.5 欧拉通路与哈密顿通路欧拉通路与哈密顿通路 Euler and Hamilton PathH1不存在欧拉回路和欧拉通路H2存在欧拉回路 agcbedfaH3不存在欧拉回路,存在欧拉通路 cabcdb定理定理1欧拉定理：欧拉定理： 没没有有度度为为0的的孤孤立立顶顶点点的的无无向向图图存存在在欧欧拉拉通通路路的的充要条件是：充要条件是： (1)图是连通的；图是连通的； (2)图中奇度顶点个数是图中奇度顶点个数是0个或个或2个。个。6.5 欧拉通路与哈密顿通路欧拉通路与哈密顿通路 Euler and Hamilton Path证明： 必要性： 假设存在欧拉通路，且没有0度顶点，那么每个顶点都有边关联，而边又全在欧拉通路上，故一切顶点都连通。 除了起点，终点外，欧拉通路每经过一个顶点，使顶点的度添加2，故只需起点和终点才能够成为奇度顶点，而一个奇度顶点是不能够的，当无奇度顶点时，是欧拉回路。充分性： 假设(1)，(2)成立，构造欧拉通路。6.5 欧拉通路与哈密顿通路欧拉通路与哈密顿通路 Euler and Hamilton Path 假设图G存在奇度顶点，任取一个作为起点，假设不存在，那么任取一个顶点作为起点。 假设此图有n条边，总度为2n。每进入或分开一个顶点，让此顶点的度减1，由于除了两个或没有奇度顶点外，其他顶点度为偶数，只需进得去，一定出得来，直至进入另一个奇度顶点或起点作为终点。这样构造的是简单通路，假设经过一切的边，即得到一条欧拉通路。 不然，记走过的简单通路为p1，p1上顶点集V1，边集E1，G1=(V1, E1)是G的子图。6.5 欧拉通路与哈密顿通路欧拉通路与哈密顿通路 Euler and Hamilton Path 假设G2=(V2,E2)是G1的关于G的补图，E2=E-E1，但V1V2 ，否那么G不连通，设CV1V2，从C出发，用上面方法作G2的简单回路p2 回到C, 这能做到。 由于作好p1后，留下顶点的度都是偶度。假设p1p2经过一切边，那么欧拉通路是p1走到C时，先把p2走完，最后走完p1的余下通路。 假设p1p2仍未经过一切边，将p1p2视为p1反复上述过程，由于E边有限，故存在欧拉通路。6.5 欧拉通路与哈密顿通路欧拉通路与哈密顿通路 Euler and Hamilton Path例1：1) 顶点的度：A(3) , B(2) , C(4) , D(2) , E(6), F(2) , G(6) , H(2) , I(4) , J(3)。其中奇度顶点A，J2) 从A出发，走一条通路P1A,C,E,A,B,C,D,E,F,G,H,I,J6.5 欧拉通路与哈密顿通路欧拉通路与哈密顿通路 Euler and Hamilton Path3) G1=(V1, E1) V1 =A,B,C,D,E,F,G,H,I,J E1 =(A,C),(C,E),(E,A),(A,B),(B,C),(C,D),(D,E),(E,F), (F,G),(G,H),(H,I),(I,J)那么 G2=(V2, E2) E2=(E,G),(E,J),(J,G),(G,I),(I,G) V2=E,G, I, J E(V1 V2)6.5 欧拉通路与哈密顿通路欧拉通路与哈密顿通路 Euler and Hamilton Path4) 在G2中从E出发回到E的回路(E, J, G, E)，参与到P1中 P1=(A,C,E,A,B,C,D,E, J, G, E,F,G,H,I,J)5) 还有未经过的边，反复上述过程 ，从G出发，(G,I,G)，再参与即得欧拉通路。 P1 =(A,C,E,A,B,C,D,E, J, G, E,F,G,I,G,H,I,J)6.5 欧拉通路与哈密顿通路欧拉通路与哈密顿通路 Euler and Hamilton Path推论推论1欧拉定理：欧拉定理： 没没有有度度为为0的的孤孤立立顶顶点点的的无无向向图图存存在在欧欧拉拉回回路路的的充要条件是：充要条件是： (1)图是连通的；图是连通的； (2)图中没有奇度顶点。图中没有奇度顶点。6.5 欧拉通路与哈密顿通路欧拉通路与哈密顿通路 Euler and Hamilton Path定理定理2 有向图的欧拉定理：有向图的欧拉定理： 不含出不含出/入度为入度为0的孤立顶点的有向图具有欧拉通路的孤立顶点的有向图具有欧拉通路的充要条件是：的充要条件是：1弱连通；弱连通；2除了能够有除了能够有2个顶点，一个入度比出度大个顶点，一个入度比出度大1，一个出，一个出度比入度大度比入度大1，其他顶点出度等于入度。，其他顶点出度等于入度。推论推论 不含出不含出/入度为入度为0的孤立顶点的有向图具有欧拉回路的孤立顶点的有向图具有欧拉回路的充要条件是：的充要条件是：1弱连通；弱连通；2一切顶点出度等于入度。一切顶点出度等于入度。6.5 欧拉通路与哈密顿通路欧拉通路与哈密顿通路 Euler and Hamilton Path欧拉通路欧拉通路/回路的运用与推行：回路的运用与推行：1一笔画问题一笔画问题2假设奇度顶点个数为假设奇度顶点个数为2K个，此问题是个，此问题是K笔画问题笔画问题3中国邮递员问题中国邮递员问题4电路布线、网络组播和分子生物学电路布线、网络组播和分子生物学 6.5 欧拉通路与哈密顿通路欧拉通路与哈密顿通路 Euler and Hamilton Path欧拉通路欧拉通路/回路的运用与推行：回路的运用与推行：1一笔画问题一笔画问题2假设奇度顶点个数为假设奇度顶点个数为2K个，此问题是个，此问题是K笔画问题笔画问题3中国邮递员问题中国邮递员问题4电路布线、网络组播和分子生物学电路布线、网络组播和分子生物学 6.5 欧拉通路与哈密顿通路欧拉通路与哈密顿通路 Euler and Hamilton PathHamilton(哈密哈密顿顿)通路通路问题问题： 1857年年发发明的一种游明的一种游戏戏。在在一一个个实实心心的的正正十十二二面面体体，20个个顶顶点点标标上上世世界界著著名名大大城城市市的的名名字字，要要求求游游戏戏者者从从某某一一城城市市出出发发，遍遍历历各城市一次，最后回到原地。各城市一次，最后回到原地。这这就就是是“绕绕行行世世界界问问题题。即即找找一一条条经经过过一一切切顶顶点点 城市城市 的根本回路。的根本回路。6.5 欧拉通路与哈密顿通路欧拉通路与哈密顿通路 Euler and Hamilton Path定义1哈密顿通路/回路： G=(V, E)，G中经过V中一切顶点的根本通路称为哈密顿通路/Hamilton Path，简称H通路。 G=(V, E)，G中经过V中一切顶点的根本回路称为哈密顿回路/Hamilton Circuit，简称H回路。注：存在哈密顿回路的图称为哈密顿图/H图6.5 欧拉通路与哈密顿通路欧拉通路与哈密顿通路 Euler and Hamilton Path图A 每个顶点都是奇度的，不存在E通路，但有H通路。 图B存在E通路，不存在H通路。6.5 欧拉通路与哈密顿通路欧拉通路与哈密顿通路 Euler and Hamilton Path6.5 欧拉通路与哈密顿通路欧拉通路与哈密顿通路 Euler and Hamilton Path有哈密顿回路或通路吗？图G1 有H回路；图G2 有H通路，无H回路；图G3无H通路，也无H回路定理定理3 设设G=(V,E) 是是n个个顶顶点的点的简单图简单图，假，假设设任一任一对对不不相相邻邻的的顶顶点度之和点度之和n-1，那么，那么G中一定有中一定有H通路通路(n2)。证明：1 G一定连通，否那么G分为二个不连通的分图G1，G2，其中G1有n1个顶点，G2有n2个顶点，G1中每个顶点度n1-1，G2中每个顶点度n2-1，从G1中取一个顶点，G2中取一个顶点，这一对顶点度之和n1-1 + n2-1n1 + n2 - 2n-2n-1，与定理的假设矛盾。6.5 欧拉通路与哈密顿通路欧拉通路与哈密顿通路 Euler and Hamilton Path留意:此定理条件显然不是必要条件，如n6的n边形，二个顶点度之和=4，4n-1，而n边形显然有H通路。2 用用归纳归纳法法证证明明G中存在中存在H通路：通路：任取一条任取一条边边(V1,V2)，是含，是含2个个顶顶点的根本通路。点的根本通路。假假设设已有已有p个个顶顶点的根本通路点的根本通路 (V1,V2,Vp)，(pn-1) 必能构造必能构造p+1个个顶顶点的根本通路。点的根本通路。a) 假假设设在在V-V1,V2,Vp中中存存在在与与V1或或Vp相相邻邻的的顶顶点点，那么根本通路自然可以那么根本通路自然可以扩扩展一个展一个顶顶点。点。b) 假假设设V1,Vp仅仅与与V1,V2,Vp中中顶顶点点相相邻邻，那那么么V1,V2,Vp必可适当必可适当陈陈列，构成回路。列，构成回路。6.5 欧拉通路与哈密顿通路欧拉通路与哈密顿通路 Euler and Hamilton Path 假设V1与Vp相邻，显然成了环。不然，由于V1,Vp仅与V1,V2,Vp中顶点相邻， V1,Vp的度p-1。无妨设V1的度为kp-1，分别记相邻顶点为Vi1，Vi2，Vik，它们前面的顶点指在根本通路V1,V2,Vp中的序为 ，Vp必与 中某顶点相邻，否那么Vp的度p-1-k，V1与Vp的度之和k+p-1 k = p-1n-1，与任一对顶点度之和n-1矛盾。 无妨Vp与Vj-1相邻，V1与Vj相邻。将V1与Vj连起来，Vp与Vj-1连起来，并将Vj-1到Vj的边去掉，就构成一个环。6.5 欧拉通路与哈密顿通路欧拉通路与哈密顿通路 Euler and Hamilton Path又由G的连通性，总可在V-V1,V2,Vp中找到一个点Vx，与V1,V2,Vp中某一顶点相邻，无妨与Vk相邻，VkV1，VkVp，连上Vx与Vk的边，去掉Vk-1到Vk的边，可以从Vk-1为起点，不断走到Vk，再到Vx，这是一条p+1个顶点的根本通路。假设p+1n，仍继续扩展根本通路内的顶点，直至到达n。6.5 欧拉通路与哈密顿通路欧拉通路与哈密顿通路 Euler and Hamilton Path推推论论 奥奥尔尔定理：定理： G=(V,E)是是n3的的简简单单图图，假假设设任任何何一一对对不不相相邻邻顶顶点点的度之和的度之和n，那么，那么G必有哈密必有哈密顿顿回路。回路。6.5 欧拉通路与哈密顿通路欧拉通路与哈密顿通路 Euler and Hamilton Path 由于推论条件也必满足定理3条件，存在H通路，可类似于定理1的方法找到一条H回路。定理定理5 无向无向/有向完全有向完全图图一定存在一定存在H通路。通路。6.5 欧拉通路与哈密顿通路欧拉通路与哈密顿通路 Euler and Hamilton Path定理定理4 狄拉克定理狄拉克定理 假假设设G是是带带n个个顶顶点点的的连连通通简简单单图图，n3，且且G中中每每个个顶顶点的度都至少点的度都至少为为n/2，那么，那么G有哈密有哈密顿顿回路。回路。 要判别一个图不存在H通路/H回路，也不是很容易的，只能对无向图给出一些必要条件：1) H通路存在必要条件： 连通 至多只能有二个顶点的度2，其他顶点的度2。bcda6.5 欧拉通路与哈密顿通路欧拉通路与哈密顿通路 Euler and Hamilton Path2) H回路存在必要条件： 对V的任一非空真子集S，G-S的连通分支个数|S|。 6.5 欧拉通路与哈密顿通路欧拉通路与哈密顿通路 Euler and Hamilton Path解：取S=A1, A2G-S存在3个连通分支根据H回路存在的必要条件之二，可知H回路不存在！6.5 欧拉通路与哈密顿通路欧拉通路与哈密顿通路 Euler and Hamilton Path运用运用问题之一：之一： Knights tour运用运用问题之二：之二： Gray Code运用运用问题之三：之三： Tower of Hanoi6.5 欧拉通路与哈密顿通路欧拉通路与哈密顿通路 Euler and Hamilton Path旋转的指针的位置可以表示成数字的方式。一种方式是把圆周等分成2n段弧并且用长度为n的位串给每段弧赋值。格雷码格雷码Gray Code 在指针上用n个接触点来确定指针位置，每个接触点用来读出位置的数字表示中的一位格雷码格雷码Gray Code 当指针接近两段弧的边境时，读出指针的位置能够出错格雷码格雷码Gray Code 3位都错最多1位错可用n立方体Qn来为问题建模弧的满足要求的标志就是求Qn的一个哈密顿回路。格雷码格雷码Gray Code Q3格雷码是上世纪40年代弗兰克格雷为把数字信号传送过程中错误的影响降到最低而发明的。思索题思索题在某次国际会议的预备会议中，共有8人参与，他们来自不同的国家。知他们中任何两个无共同言语的人中的每一个，与其他有共同言语的人数之和大于或等于8，问能否将这8个人排在圆桌旁，使其任何人都能与两边的人交谈。 思索题思索题解：设8个人分别为v1,v2,v8，作无向简单图G=(V,E)，其中V=v1,v2,v8，vi,vjV，且ij，假设vi与vj有共同言语，就在vi,vj之间连无向边(vi,vj)，由此组成边集合E，那么G为8阶无向简单图，viV，d(vi)为与vi有共同言语的人数。由知条件可知，vi,vjV且ij，均有d(vi)+d(vj)8。由定理3可知，G中存在哈密顿回路，设Cvi1vi2vi8为G中一条哈密顿回路，按这条回路的顺序安排座次即可。作作 业业 P274：3、10、17