8.3-8.4-欧拉图-哈密顿图.ppt

第第4篇篇图论基础图论基础离散数学离散数学欧拉图与哈密顿图欧拉图与哈密顿图oo8.38.3欧拉图欧拉图欧拉图欧拉图oo8.48.4哈密顿图哈密顿图哈密顿图哈密顿图8.3欧拉图欧拉图一、哥尼斯堡七桥问题：一、哥尼斯堡七桥问题：一、哥尼斯堡七桥问题：一、哥尼斯堡七桥问题：在当时的哥尼斯堡城有一条普莱格尔（在当时的哥尼斯堡城有一条普莱格尔（Pregel）河，）河，河中有两个小岛，并有七座桥将河中的两个小岛和河的河中有两个小岛，并有七座桥将河中的两个小岛和河的两岸连接起来。当时那里的居民热衷于一个问题：两岸连接起来。当时那里的居民热衷于一个问题：一个一个散步者从任何一处陆地出发，怎样才能走遍每座桥一次散步者从任何一处陆地出发，怎样才能走遍每座桥一次且仅一次，最后又回到原出发地且仅一次，最后又回到原出发地？这就是七桥问题，一个这就是七桥问题，一个这就是七桥问题，一个这就是七桥问题，一个著名的图论问题。著名的图论问题。著名的图论问题。著名的图论问题。oo于是于是于是于是“七桥问题七桥问题七桥问题七桥问题”就等价于图中所画图形的一笔画问题了。就等价于图中所画图形的一笔画问题了。就等价于图中所画图形的一笔画问题了。就等价于图中所画图形的一笔画问题了。oo欧拉欧拉欧拉欧拉注意注意注意注意到，每个点如果有进去的边就必须有出来的边，从而到，每个点如果有进去的边就必须有出来的边，从而到，每个点如果有进去的边就必须有出来的边，从而到，每个点如果有进去的边就必须有出来的边，从而每个点连接的边数必须有偶数个才能完成一笔画。上图的每个每个点连接的边数必须有偶数个才能完成一笔画。上图的每个每个点连接的边数必须有偶数个才能完成一笔画。上图的每个每个点连接的边数必须有偶数个才能完成一笔画。上图的每个点都连接着奇数条边，因此不可能一笔画出，这就说明不存在点都连接着奇数条边，因此不可能一笔画出，这就说明不存在点都连接着奇数条边，因此不可能一笔画出，这就说明不存在点都连接着奇数条边，因此不可能一笔画出，这就说明不存在一次走遍一次走遍一次走遍一次走遍7 7 7 7座桥，而每座桥只许通过一次的走法。座桥，而每座桥只许通过一次的走法。座桥，而每座桥只许通过一次的走法。座桥，而每座桥只许通过一次的走法。陆地是桥梁的连接地点，不妨把图中被河隔开的陆地看成陆地是桥梁的连接地点，不妨把图中被河隔开的陆地看成A、B、C、D，4个点，个点，7座桥表示成座桥表示成7条连接这条连接这4个点的线，如图所示。个点的线，如图所示。二、欧拉通路、欧拉回路、欧拉图、半欧拉图二、欧拉通路、欧拉回路、欧拉图、半欧拉图设设设设G=G=为连通图为连通图为连通图为连通图(无向的或有向的无向的或有向的无向的或有向的无向的或有向的)oo将将将将GG中中中中经过每条边一次且仅一次经过每条边一次且仅一次经过每条边一次且仅一次经过每条边一次且仅一次的的的的通路通路通路通路称作称作称作称作欧拉通路欧拉通路欧拉通路欧拉通路；oo将将将将GG中中中中经过每条边一次且仅一次经过每条边一次且仅一次经过每条边一次且仅一次经过每条边一次且仅一次的的的的回路回路回路回路称作称作称作称作欧拉回路欧拉回路欧拉回路欧拉回路；oo将将将将具有欧拉回路具有欧拉回路具有欧拉回路具有欧拉回路的图称为的图称为的图称为的图称为欧拉图欧拉图欧拉图欧拉图；oo将将将将具有欧拉通路具有欧拉通路具有欧拉通路具有欧拉通路但但但但不具有欧拉回路不具有欧拉回路不具有欧拉回路不具有欧拉回路的图称为的图称为的图称为的图称为半欧拉图半欧拉图半欧拉图半欧拉图。三、对欧拉图的判定三、对欧拉图的判定(无向图无向图)定理定理定理定理8.68.6对于任一无向图对于任一无向图对于任一无向图对于任一无向图GG，ooGG具有欧拉通路具有欧拉通路具有欧拉通路具有欧拉通路当且仅当当且仅当当且仅当当且仅当GG是是是是连通的连通的连通的连通的，且，且，且，且有零个或两个奇度有零个或两个奇度有零个或两个奇度有零个或两个奇度数结点数结点数结点数结点。n n若若若若无奇度结点无奇度结点无奇度结点无奇度结点，则欧拉通路为，则欧拉通路为，则欧拉通路为，则欧拉通路为欧拉回路欧拉回路欧拉回路欧拉回路；n n若若若若有两个奇度顶点有两个奇度顶点有两个奇度顶点有两个奇度顶点，则它们，则它们，则它们，则它们是每条欧拉通路的端点是每条欧拉通路的端点是每条欧拉通路的端点是每条欧拉通路的端点。证明：采用构造证明法。证明：采用构造证明法。证明：采用构造证明法。证明：采用构造证明法。三、对欧拉图的判定三、对欧拉图的判定(无向图无向图)()(续续)o证明证明：对于图对于图G=，设，设V=v1,v2,vn，E=e1,e2,em。o（必要性必要性）设图）设图G中存在中存在欧拉欧拉通通路路L=v1e1v2e2v3e3vmemvm+1，由，由于于L中含有中含有G的所有边，所以的所有边，所以G的的n个结点均在通路个结点均在通路L中出现，从中出现，从而，任何两个结点都可以通过该欧拉通路连通，即，图而，任何两个结点都可以通过该欧拉通路连通，即，图G是连通是连通的。的。o对于欧拉通路中的任意结点对于欧拉通路中的任意结点vk（1 k m+1），该结点关联边），该结点关联边ek 1和边和边ek，因而使得结点，因而使得结点vk获得度数获得度数2。如果。如果vk在通路中重复出在通路中重复出现现s次，则次，则deg(vk)=2s。o对于欧拉通路中的起始结点对于欧拉通路中的起始结点v1和终止结点和终止结点vm+1，如果两者不重合，如果两者不重合，则各自获得度数则各自获得度数1，如果还在通路中分别重复，如果还在通路中分别重复s1次和次和s2次，则各次，则各自的度数分变为自的度数分变为deg(v1)=2s1+1，deg(vm+1)=2s2+1。从而，。从而，G中中有两个奇度数结点。有两个奇度数结点。o综上知，图综上知，图G是连通图且有零个或两个奇度数结点。是连通图且有零个或两个奇度数结点。三、对欧拉图的判定三、对欧拉图的判定(无向图无向图)()(续续)o（充分性）如果图（充分性）如果图G是连通图且有零个或两个奇度数结点，则通过如下步骤是连通图且有零个或两个奇度数结点，则通过如下步骤构造一条欧拉通路：构造一条欧拉通路：o如果有两个奇度数结点如果有两个奇度数结点v0和和vt，则从其中一个结点（如，则从其中一个结点（如v0）开始构造一条简）开始构造一条简单通路，即，从单通路，即，从v0出发经过关联边出发经过关联边e1到结点到结点v1，由于，由于deg(v1)是偶数，必可由结是偶数，必可由结点点v1经过关联边经过关联边e2到结点到结点v2，如此下去，每条边经过一次。由于图，如此下去，每条边经过一次。由于图G是连通的，是连通的，必可达到另一个奇度数结点必可达到另一个奇度数结点vt，从而得到一条结点，从而得到一条结点v0到结点到结点vt的简单通路的简单通路L1；如果没有奇度数结点如果没有奇度数结点，则从任意一个结点（如则从任意一个结点（如v0）出发，利用上述方法可以）出发，利用上述方法可以回到结点回到结点v0，从而得到一条简单回路，从而得到一条简单回路L1。o如果如果L1含有所有边，则它即为欧拉通路或欧拉回路；否则，删除图含有所有边，则它即为欧拉通路或欧拉回路；否则，删除图G中的中的L1上的所有边，得到子图上的所有边，得到子图G，则图，则图G 中的任何结点的度数都是偶数。由于中的任何结点的度数都是偶数。由于图图G是连通的，所以图是连通的，所以图G 中至少存在一个中至少存在一个L1上的结点上的结点vk。在图。在图G 中，以该中，以该结点结点vk为起始结点，重复为起始结点，重复的方法，得到一个简单回路的方法，得到一个简单回路L2。o对于所得到的对于所得到的L1=和和 L2=，如果，如果L1 L2=G，则得到欧拉通路或欧拉回路，则得到欧拉通路或欧拉回路L1 L2；否则，重复；否则，重复的方法，删的方法，删除图除图G 中的中的L2上的所有边，得到子图上的所有边，得到子图G，从而得到一条简单回路，从而得到一条简单回路L3，继，继续下去，直到得到欧拉通路或欧拉回路续下去，直到得到欧拉通路或欧拉回路L1 L2 L3。由此，图。由此，图G=含有欧拉通路。含有欧拉通路。o证毕。证毕。三、对欧拉图的判定三、对欧拉图的判定(无向图无向图)()(续续)推论推论推论推论 无向图无向图无向图无向图G=G=含有含有含有含有欧拉回路欧拉回路欧拉回路欧拉回路当且仅当当且仅当当且仅当当且仅当GG是是是是连通图连通图连通图连通图且且且且所有结点的度数都是偶数所有结点的度数都是偶数所有结点的度数都是偶数所有结点的度数都是偶数。练习练习判断下列图是否为欧拉图或者半欧拉图。判断下列图是否为欧拉图或者半欧拉图。判断下列图是否为欧拉图或者半欧拉图。判断下列图是否为欧拉图或者半欧拉图。四、一笔画问题四、一笔画问题oo与七桥问题类似的还有与七桥问题类似的还有与七桥问题类似的还有与七桥问题类似的还有一笔画一笔画一笔画一笔画的判别问题，要判定一个的判别问题，要判定一个的判别问题，要判定一个的判别问题，要判定一个图是否可一笔画出，有两种情况：图是否可一笔画出，有两种情况：图是否可一笔画出，有两种情况：图是否可一笔画出，有两种情况：n n一是从图一是从图一是从图一是从图GG中某一结点出发，经过图中的每一边一次中某一结点出发，经过图中的每一边一次中某一结点出发，经过图中的每一边一次中某一结点出发，经过图中的每一边一次且仅一次到达另一结点；且仅一次到达另一结点；且仅一次到达另一结点；且仅一次到达另一结点；n n另一种情况是从另一种情况是从另一种情况是从另一种情况是从GG的某个结点出发，经过的某个结点出发，经过的某个结点出发，经过的某个结点出发，经过GG的每一边的每一边的每一边的每一边一次且仅一次再回到该结点。一次且仅一次再回到该结点。一次且仅一次再回到该结点。一次且仅一次再回到该结点。上述两种情况分别可由欧拉通路和欧拉回路的判定条上述两种情况分别可由欧拉通路和欧拉回路的判定条上述两种情况分别可由欧拉通路和欧拉回路的判定条上述两种情况分别可由欧拉通路和欧拉回路的判定条件予以解决。件予以解决。件予以解决。件予以解决。例如：判断下列两图可否一笔画出？例如：判断下列两图可否一笔画出？例如：判断下列两图可否一笔画出？例如：判断下列两图可否一笔画出？五、对欧拉图的判定五、对欧拉图的判定(有向图有向图)定理定理定理定理8.78.7有向图有向图有向图有向图G=G=，ooGG含有欧拉通路含有欧拉通路含有欧拉通路含有欧拉通路当且仅当当且仅当当且仅当当且仅当GG是是是是连通的连通的连通的连通的，且，且，且，且n n所有结点的入度等于出度所有结点的入度等于出度所有结点的入度等于出度所有结点的入度等于出度，或者，或者，或者，或者n n除两个结点外其余结点的入度等于出度除两个结点外其余结点的入度等于出度除两个结点外其余结点的入度等于出度除两个结点外其余结点的入度等于出度，而在这两个，而在这两个，而在这两个，而在这两个结点中，结点中，结点中，结点中，一个结点的入度比出度大一个结点的入度比出度大一个结点的入度比出度大一个结点的入度比出度大1 1，另一个结点的入另一个结点的入另一个结点的入另一个结点的入度比出度小度比出度小度比出度小度比出度小1 1。推论推论推论推论oo有向图有向图有向图有向图G=G=含有含有含有含有欧拉回路，欧拉回路，欧拉回路，欧拉回路，当且仅当图当且仅当图当且仅当图当且仅当图GG是是是是连通的连通的连通的连通的，并且并且并且并且所有结点的入度等于出度所有结点的入度等于出度所有结点的入度等于出度所有结点的入度等于出度。oo如果有向图如果有向图如果有向图如果有向图G=G=是半欧拉图，则是半欧拉图，则是半欧拉图，则是半欧拉图，则入度比出度小入度比出度小入度比出度小入度比出度小1 1的的的的结点结点结点结点是欧拉通路的是欧拉通路的是欧拉通路的是欧拉通路的起点起点起点起点，入度比出度大入度比出度大入度比出度大入度比出度大1 1的结点的结点的结点的结点是欧拉通路是欧拉通路是欧拉通路是欧拉通路的的的的终点终点终点终点。练习练习判断下列图是否为欧拉图或者半欧拉图。判断下列图是否为欧拉图或者半欧拉图。判断下列图是否为欧拉图或者半欧拉图。判断下列图是否为欧拉图或者半欧拉图。练习练习判断下列说法是否正确：判断下列说法是否正确：判断下列说法是否正确：判断下列说法是否正确：oo平凡图是欧拉图；平凡图是欧拉图；平凡图是欧拉图；平凡图是欧拉图；oo奇数个顶点的完全图是欧拉图；奇数个顶点的完全图是欧拉图；奇数个顶点的完全图是欧拉图；奇数个顶点的完全图是欧拉图；oo欧拉通路欧拉通路欧拉通路欧拉通路(欧拉回路欧拉回路欧拉回路欧拉回路)经过了图中的所有顶点；经过了图中的所有顶点；经过了图中的所有顶点；经过了图中的所有顶点；oo完全图完全图完全图完全图KKn n(n(n 3 3)都是欧拉图；都是欧拉图；都是欧拉图；都是欧拉图；oon(nn(n 3 3)阶有向完全图都是欧拉图；阶有向完全图都是欧拉图；阶有向完全图都是欧拉图；阶有向完全图都是欧拉图；六、六、Fleury算法算法oo对于欧拉图对于欧拉图对于欧拉图对于欧拉图G G=oo 任选任选任选任选V V中任一个结点中任一个结点中任一个结点中任一个结点v v0 0为起始结点，并令为起始结点，并令为起始结点，并令为起始结点，并令L L0 0=v v0 0；oo 设已选好的简单通路为设已选好的简单通路为设已选好的简单通路为设已选好的简单通路为L Li i=v v0 0e e1 1v v1 1e e2 2v v2 2e e3 3e ei iv vi i，按下述方法从，按下述方法从，按下述方法从，按下述方法从E E e e1 1,e e2 2,e e3 3,e ei i 中选取边中选取边中选取边中选取边e ei i+1+1：（：（：（：（G G 为从为从为从为从G G中删除边集中删除边集中删除边集中删除边集 e e1 1,e e2 2,e e3 3,e ei i 得到的图）得到的图）得到的图）得到的图）oo（i i）结点）结点）结点）结点v vi i是边是边是边是边e ei i+1+1的端点；的端点；的端点；的端点；oo（ii ii）除非无其它边可选取，否则删除边）除非无其它边可选取，否则删除边）除非无其它边可选取，否则删除边）除非无其它边可选取，否则删除边e ei i+1+1不应该改变图不应该改变图不应该改变图不应该改变图G G 的连通性。的连通性。的连通性。的连通性。oo 第第第第步无法进行时（所有的边已选择），算法终止。步无法进行时（所有的边已选择），算法终止。步无法进行时（所有的边已选择），算法终止。步无法进行时（所有的边已选择），算法终止。练习练习求如左图求如左图求如左图求如左图G G1 1中的一条欧拉回路。中的一条欧拉回路。中的一条欧拉回路。中的一条欧拉回路。解解解解 在图在图在图在图G G1 1中，令中，令中，令中，令e e1 1=(=(v v1 1,v v2 2)，e e2 2=(=(v v1 1,v v3 3)，e e3 3=(=(v v1 1,v v4 4)，e e4 4=(=(v v1 1,v v5 5)，e e5 5=(=(v v2 2,v v3 3)，e e6 6=(=(v v2 2,v v4 4)，e e7 7=(=(v v2 2,v v5 5)，e e8 8=(=(v v3 3,v v4 4)，e e9 9=(=(v v3 3,v v5 5)，e e1010=(=(v v4 4,v v5 5)。oo根据根据根据根据FleuryFleury算法，将结点算法，将结点算法，将结点算法，将结点v v1 1作为起始结点，那么，作为起始结点，那么，作为起始结点，那么，作为起始结点，那么，L L00=v v1 1；oo在边集在边集在边集在边集E E=e e1 1,e e2 2,e e3 3,e e4 4,e e5 5,e e6 6,e e7 7,e e8 8,e e9 9,e e1010 中，边中，边中，边中，边e e1 1与结点与结点与结点与结点v v1 1关联，且删除关联，且删除关联，且删除关联，且删除该边不改变图该边不改变图该边不改变图该边不改变图G G1 1的连通性，所以，选取边的连通性，所以，选取边的连通性，所以，选取边的连通性，所以，选取边e e1 1，得到，得到，得到，得到L L1 1=v v1 1e e1 1v v2 2；oo在边集在边集在边集在边集E E=e e1 1,e e2 2,e e3 3,e e4 4,e e5 5,e e6 6,e e7 7,e e8 8,e e9 9,e e1010 e e1 1=e e2 2,e e3 3,e e4 4,e e5 5,e e6 6,e e7 7,e e8 8,e e9 9,e e1010 中，边中，边中，边中，边e e5 5与结点与结点与结点与结点v v2 2关联，且删除该边不改变图关联，且删除该边不改变图关联，且删除该边不改变图关联，且删除该边不改变图G G 的连通性，所以，选的连通性，所以，选的连通性，所以，选的连通性，所以，选取边取边取边取边e e5 5，得到，得到，得到，得到L L2 2=v v1 1e e1 1v v2 2e e5 5v v3 3；oo在边集在边集在边集在边集E E=e e1 1,e e2 2,e e3 3,e e4 4,e e5 5,e e6 6,e e7 7,e e8 8,e e9 9,e e1010 e e1 1,e e5 5=e e2 2,e e3 3,e e4 4,e e6 6,e e7 7,e e8 8,e e9 9,e e1010 中，边中，边中，边中，边e e8 8与结点与结点与结点与结点v v3 3关联，且删除该边不改变图关联，且删除该边不改变图关联，且删除该边不改变图关联，且删除该边不改变图G G 的连通性，所以，选的连通性，所以，选的连通性，所以，选的连通性，所以，选取边取边取边取边e e8 8，得到，得到，得到，得到L L3 3=v v1 1e e1 1v v2 2e e5 5v v3 3e e8 8v v4 4；oo重复上述步骤，可以得出图重复上述步骤，可以得出图重复上述步骤，可以得出图重复上述步骤，可以得出图G G1 1的一条欧拉回路为的一条欧拉回路为的一条欧拉回路为的一条欧拉回路为ooL L1010=v v1 1e e1 1v v2 2e e5 5v v3 3e e8 8v v4 4e e1010v v5 5e e4 4v v1 1e e2 2v v3 3e e9 9v v5 5e e7 7v v2 2e e6 6v v4 4e e3 3v v1 1练习练习从下图中找出一条欧拉通路。从下图中找出一条欧拉通路。从下图中找出一条欧拉通路。从下图中找出一条欧拉通路。奇数度顶点是奇数度顶点是:v1和和v9。L=v1v2v3v4v5v2v4v6v7v8v9v10v6v8v10v7v9是一条欧拉通路。是一条欧拉通路。8.4哈密顿图哈密顿图一、哈密顿周游世界问题一、哈密顿周游世界问题一、哈密顿周游世界问题一、哈密顿周游世界问题 1859 1859 1859 1859年年年年,爱尔兰数学家哈密顿爱尔兰数学家哈密顿爱尔兰数学家哈密顿爱尔兰数学家哈密顿(Halmiton)Halmiton)Halmiton)Halmiton)提出一个提出一个提出一个提出一个“周游世界周游世界周游世界周游世界”的游戏的游戏的游戏的游戏,它把图它把图它把图它把图(a)a)a)a)所示的正十二面体的二十所示的正十二面体的二十所示的正十二面体的二十所示的正十二面体的二十个顶点当作是地球上的二十个城市个顶点当作是地球上的二十个城市个顶点当作是地球上的二十个城市个顶点当作是地球上的二十个城市,要求旅游者从某个城要求旅游者从某个城要求旅游者从某个城要求旅游者从某个城市出发市出发市出发市出发,沿棱沿棱沿棱沿棱走过每个城市一次且仅一次走过每个城市一次且仅一次走过每个城市一次且仅一次走过每个城市一次且仅一次,最后回到出发最后回到出发最后回到出发最后回到出发点点点点。(b)b)b)b)图中粗线所构成的回路就是问题的答案。图中粗线所构成的回路就是问题的答案。图中粗线所构成的回路就是问题的答案。图中粗线所构成的回路就是问题的答案。18ab二、哈密顿通路二、哈密顿通路/回路、回路、(半半)哈密顿图哈密顿图设设设设G=G=G=G=为连通图为连通图为连通图为连通图(无向的或有向的无向的或有向的无向的或有向的无向的或有向的)oo将将将将G G G G中中中中经过每一个结点一次且仅一次经过每一个结点一次且仅一次经过每一个结点一次且仅一次经过每一个结点一次且仅一次的的的的通路通路通路通路称作称作称作称作哈密顿通哈密顿通哈密顿通哈密顿通路路路路；oo将将将将G G G G中中中中经过每一个结点一次且仅一次经过每一个结点一次且仅一次经过每一个结点一次且仅一次经过每一个结点一次且仅一次的的的的回路回路回路回路称作称作称作称作哈密顿回哈密顿回哈密顿回哈密顿回路路路路；oo将将将将具有哈密顿回路具有哈密顿回路具有哈密顿回路具有哈密顿回路的图称为的图称为的图称为的图称为哈密顿图哈密顿图哈密顿图哈密顿图；oo将将将将具有哈密顿通路具有哈密顿通路具有哈密顿通路具有哈密顿通路但但但但不具有哈密顿回路不具有哈密顿回路不具有哈密顿回路不具有哈密顿回路的图称为的图称为的图称为的图称为半哈密顿半哈密顿半哈密顿半哈密顿图图图图。欧拉图欧拉图 vs.vs.哈密顿图哈密顿图(1)(1)(1)(1)欧拉图欧拉图欧拉图欧拉图遍历边遍历边遍历边遍历边，而，而，而，而哈密顿哈密顿哈密顿哈密顿图图图图遍历顶点遍历顶点遍历顶点遍历顶点。(2)(2)(2)(2)欧拉回路是简单回路欧拉回路是简单回路欧拉回路是简单回路欧拉回路是简单回路，而，而，而，而哈密顿回路是初级回路哈密顿回路是初级回路哈密顿回路是初级回路哈密顿回路是初级回路。oo 简单回路：简单回路：简单回路：简单回路：边全不相同的回路。边全不相同的回路。边全不相同的回路。边全不相同的回路。oo 初级回路：初级回路：初级回路：初级回路：除终点与始点外，各结点全不相同的回路。除终点与始点外，各结点全不相同的回路。除终点与始点外，各结点全不相同的回路。除终点与始点外，各结点全不相同的回路。(3)(3)(3)(3)欧拉图欧拉图欧拉图欧拉图已已已已“彻底和漂亮彻底和漂亮彻底和漂亮彻底和漂亮”地解决了地解决了地解决了地解决了，对，对，对，对哈密顿图至今还哈密顿图至今还哈密顿图至今还哈密顿图至今还没有找到简单的充要条件没有找到简单的充要条件没有找到简单的充要条件没有找到简单的充要条件。三、哈密顿图的判定三、哈密顿图的判定(必要条件必要条件)定理定理定理定理8.98.9对于任一无向图对于任一无向图对于任一无向图对于任一无向图GG，oo设无向图设无向图设无向图设无向图G=G=是是是是哈密顿图哈密顿图哈密顿图哈密顿图，则对结点集，则对结点集，则对结点集，则对结点集V V的的的的任意非空子任意非空子任意非空子任意非空子集集集集V1V1都有都有都有都有p(G-Vp(G-V1 1)|V)|V1 1|其中其中其中其中p(G-Vp(G-V1 1)表示从表示从表示从表示从GG中删除中删除中删除中删除V V1 1后所得图的连通分支数。后所得图的连通分支数。后所得图的连通分支数。后所得图的连通分支数。推论推论推论推论oo设无向图设无向图设无向图设无向图G=G=中含有中含有中含有中含有哈密顿通路哈密顿通路哈密顿通路哈密顿通路，则对于，则对于，则对于，则对于V V的任一非空的任一非空的任一非空的任一非空子集子集子集子集V V1 1都有都有都有都有 p(G-Vp(G-V1 1)|V1|+1|V1|+1v1v2v7v3v5v8v4v6取取V1=v1,v4v2v7v3v5v8v6练习练习判断下图是否存在哈密顿回路和哈密顿通路。判断下图是否存在哈密顿回路和哈密顿通路。判断下图是否存在哈密顿回路和哈密顿通路。判断下图是否存在哈密顿回路和哈密顿通路。V1=a,f时：时：p(G-V1)=4|V1|=2练习练习判断下图是否存在哈密尔顿回路。判断下图是否存在哈密尔顿回路。判断下图是否存在哈密尔顿回路。判断下图是否存在哈密尔顿回路。oo删去任一个结点或任意两个结点后，仍然是连通的；删去任一个结点或任意两个结点后，仍然是连通的；删去任一个结点或任意两个结点后，仍然是连通的；删去任一个结点或任意两个结点后，仍然是连通的；oo删去删去删去删去3 3个结点，最多只能得到个结点，最多只能得到个结点，最多只能得到个结点，最多只能得到2 2个连通分支；个连通分支；个连通分支；个连通分支；oo删去删去删去删去4 4个结点，最多只能得到个结点，最多只能得到个结点，最多只能得到个结点，最多只能得到3 3个连通分支；个连通分支；个连通分支；个连通分支；oo删去删去删去删去5 5个或个或个或个或5 5个以上的结点，余下子图的结点数都不大于个以上的结点，余下子图的结点数都不大于个以上的结点，余下子图的结点数都不大于个以上的结点，余下子图的结点数都不大于5 5，故必不能有故必不能有故必不能有故必不能有5 5个以上的连通分支数。个以上的连通分支数。个以上的连通分支数。个以上的连通分支数。定理定理8.9是是必要条件必要条件，只能判断，只能判断不是不是哈密顿图的情况。哈密顿图的情况。彼得森彼得森(Petersen)图图But，不存在哈密尔顿回路！，不存在哈密尔顿回路！四、哈密顿图的判定四、哈密顿图的判定(充分条件充分条件)定理定理定理定理8.108.10设设设设G=G=是是是是n(n(n3n3)阶无向简单图，阶无向简单图，阶无向简单图，阶无向简单图，o如果如果如果如果GG中中中中任意两个不相邻结点的度数之和都大于等于任意两个不相邻结点的度数之和都大于等于任意两个不相邻结点的度数之和都大于等于任意两个不相邻结点的度数之和都大于等于n-n-1 1，则，则，则，则GG中存在中存在中存在中存在哈密顿通路哈密顿通路哈密顿通路哈密顿通路；推论推论推论推论11设设设设G=G=是是是是n(n(n3n3)阶无向简单图，阶无向简单图，阶无向简单图，阶无向简单图，o如果如果如果如果GG中中中中任意两个不相邻结点的度数之和都大于等于任意两个不相邻结点的度数之和都大于等于任意两个不相邻结点的度数之和都大于等于任意两个不相邻结点的度数之和都大于等于n n，则，则，则，则GG中存在中存在中存在中存在哈密顿回路，哈密顿回路，哈密顿回路，哈密顿回路，即即即即GG为哈密顿图为哈密顿图为哈密顿图为哈密顿图。推论推论推论推论22设设设设G=G=是是是是n(n(n3n3)阶无向简单图，阶无向简单图，阶无向简单图，阶无向简单图，o如果如果如果如果GG中中中中任意结点任意结点任意结点任意结点v v，都有，都有，都有，都有deg(v)deg(v)n/2n/2，则，则，则，则GG中存在中存在中存在中存在哈哈哈哈密顿回路，密顿回路，密顿回路，密顿回路，即即即即GG为哈密顿图为哈密顿图为哈密顿图为哈密顿图。练习练习解解图图G1的阶数为的阶数为5，由于，由于deg(v1)=deg(v2)=deg(v3)=deg(v4)=deg(v5)=4 5/2，所以，图，所以，图G1是哈密顿图；是哈密顿图；图图G2的阶数为的阶数为5，虽然，虽然deg(v1)=deg(v2)=deg(v3)=deg(v4)=deg(v5)=2 5/2，但是，但是，v1v2v3v4v5v1是图是图G2中的一条哈密顿回路，所以，图中的一条哈密顿回路，所以，图G2是哈密顿图；是哈密顿图；在图在图G3中，取中，取V1=v1,v6，p(G3 V1)=4|V1|=2，所以，图，所以，图G3不是哈密顿不是哈密顿图，也不是半哈密顿图；图，也不是半哈密顿图；在图在图G4中，取中，取V1=v1,v4,v6,v8,v10，p(G4 V1)=6|V1|=5，所以，图，所以，图G4不是哈密顿图，但是，基本通路不是哈密顿图，但是，基本通路v5v1v2v6v11v10v7v4v3v8v9是图是图G4中的一条哈中的一条哈密顿通路，所以，图密顿通路，所以，图G4是半哈密顿图。是半哈密顿图。判断下列各图哪些是哈密顿图或半哈密顿图。判断下列各图哪些是哈密顿图或半哈密顿图。判断下列各图哪些是哈密顿图或半哈密顿图。判断下列各图哪些是哈密顿图或半哈密顿图。练习练习试分别画出满足如下条件的无向图试分别画出满足如下条件的无向图试分别画出满足如下条件的无向图试分别画出满足如下条件的无向图:(1)(1)具有欧拉回路和哈密尔顿回路；具有欧拉回路和哈密尔顿回路；具有欧拉回路和哈密尔顿回路；具有欧拉回路和哈密尔顿回路；(2)(2)具有欧拉回路而没有哈密尔顿回路；具有欧拉回路而没有哈密尔顿回路；具有欧拉回路而没有哈密尔顿回路；具有欧拉回路而没有哈密尔顿回路；(3)(3)具有哈密尔顿回路而没有欧拉回路；具有哈密尔顿回路而没有欧拉回路；具有哈密尔顿回路而没有欧拉回路；具有哈密尔顿回路而没有欧拉回路；(4)(4)既没有欧拉回路，也没有哈密尔顿回路。既没有欧拉回路，也没有哈密尔顿回路。既没有欧拉回路，也没有哈密尔顿回路。既没有欧拉回路，也没有哈密尔顿回路。练习练习例例例例 考虑在考虑在考虑在考虑在6 6天内安排天内安排天内安排天内安排6 6门课程的考试，要求同一位教师所任的门课程的考试，要求同一位教师所任的门课程的考试，要求同一位教师所任的门课程的考试，要求同一位教师所任的任何两门课程的考试不能安排在连续两天里考。证明：如任何两门课程的考试不能安排在连续两天里考。证明：如任何两门课程的考试不能安排在连续两天里考。证明：如任何两门课程的考试不能安排在连续两天里考。证明：如果没有教师担任多于果没有教师担任多于果没有教师担任多于果没有教师担任多于3 3门课程，则总存在符合上述要求的考门课程，则总存在符合上述要求的考门课程，则总存在符合上述要求的考门课程，则总存在符合上述要求的考试安排。试安排。试安排。试安排。证明证明证明证明设设设设GG为具有为具有为具有为具有6 6个结点的图，每个结点对应于一门课程考个结点的图，每个结点对应于一门课程考个结点的图，每个结点对应于一门课程考个结点的图，每个结点对应于一门课程考试，如果这两个结点对应的课程考试是由不同教师担任的，试，如果这两个结点对应的课程考试是由不同教师担任的，试，如果这两个结点对应的课程考试是由不同教师担任的，试，如果这两个结点对应的课程考试是由不同教师担任的，那么这两个结点之间有一条边。那么这两个结点之间有一条边。那么这两个结点之间有一条边。那么这两个结点之间有一条边。因为每个教师所任课程数不超过因为每个教师所任课程数不超过因为每个教师所任课程数不超过因为每个教师所任课程数不超过3 3，故每个结点的度数，故每个结点的度数，故每个结点的度数，故每个结点的度数至少是至少是至少是至少是3 3，任两个结点的度数之和至少是，任两个结点的度数之和至少是，任两个结点的度数之和至少是，任两个结点的度数之和至少是6 6，故，故，故，故GG总是包含总是包含总是包含总是包含一条一条一条一条哈密顿通路哈密顿通路哈密顿通路哈密顿通路，它对应于考试课目的一个适当安排。，它对应于考试课目的一个适当安排。，它对应于考试课目的一个适当安排。，它对应于考试课目的一个适当安排。练习练习oo考虑在考虑在考虑在考虑在7 7天内安排天内安排天内安排天内安排7 7门课程的考试，使得同一位教师所任门课程的考试，使得同一位教师所任门课程的考试，使得同一位教师所任门课程的考试，使得同一位教师所任的两门课程考试不排在接连的两天中。的两门课程考试不排在接连的两天中。的两门课程考试不排在接连的两天中。的两门课程考试不排在接连的两天中。求证：如果没有教师担任多于求证：如果没有教师担任多于求证：如果没有教师担任多于求证：如果没有教师担任多于4 4门课程，则符合上述要求门课程，则符合上述要求门课程，则符合上述要求门课程，则符合上述要求的考试安排总是可能的。的考试安排总是可能的。的考试安排总是可能的。的考试安排总是可能的。证明证明证明证明.设设设设GG为具有为具有为具有为具有7 7个结点的图，每个结点对应于一门课程个结点的图，每个结点对应于一门课程个结点的图，每个结点对应于一门课程个结点的图，每个结点对应于一门课程考试，如果这两个结点对应的课程考试是由不同教师担考试，如果这两个结点对应的课程考试是由不同教师担考试，如果这两个结点对应的课程考试是由不同教师担考试，如果这两个结点对应的课程考试是由不同教师担任的，那么这两个结点之间有一条边。因为每个教师所任的，那么这两个结点之间有一条边。因为每个教师所任的，那么这两个结点之间有一条边。因为每个教师所任的，那么这两个结点之间有一条边。因为每个教师所任课程数不超过任课程数不超过任课程数不超过任课程数不超过4 4，故每个结点的度数至少是，故每个结点的度数至少是，故每个结点的度数至少是，故每个结点的度数至少是3 3，任两个，任两个，任两个，任两个结点的度数之和至少是结点的度数之和至少是结点的度数之和至少是结点的度数之和至少是6 6，故，故，故，故GG总是包含一条哈密顿路，总是包含一条哈密顿路，总是包含一条哈密顿路，总是包含一条哈密顿路，它对应于七门考试课目的一个适当的安排。它对应于七门考试课目的一个适当的安排。它对应于七门考试课目的一个适当的安排。它对应于七门考试课目的一个适当的安排。作业作业oP336第第30大题大题第第36大题大题