《欧拉图与汉密尔顿图课件》由会员分享，可在线阅读，更多相关《欧拉图与汉密尔顿图课件（35页珍藏版）》请在金锄头文库上搜索。
1、7-4 欧拉图与哈密尔顿图,1736年瑞士数学家列昂哈德欧拉(leonhard Euler)发表了图论的第一篇论文“哥尼斯堡七桥问题”。这个问题是这样的：哥尼斯堡(Konigsberg)城市有一条横贯全城的普雷格尔(Pregel) 河，城的各部分用七座桥连接，每逢假日，城中的居民进行环城的逛游，这样就产生一个问题，能不能设计一次“逛游”，使得从某地出发对每座跨河桥走一次，而在遍历了七桥之后却又能回到原地。,这个问题可用图7-4.1 表示。,Leonhard Euler,Leonhard Euler(17071783): 人类有史以来最多产的数学家. 1736年,“七桥问题”,图论和拓扑学诞生,
2、图7-4.2为七桥问题的图。,图中的结点A，B，C，D表示四块地，而边表示七座桥。哥尼斯堡七桥问题是在图中找寻经过每一条边且仅一次而回到原地的通路。,欧拉在1736年的一篇论文中提出了一条简单的准则，确定了哥尼斯堡七桥问题是不能解的。下面将讨论这个问题的证明。 定义 欧拉回路 给定无孤立点图G，若存在一条路，经过图中每边一次且仅一次，该条路称为欧拉路；若存在一条回路，经过图中的每边一次且仅一次，该回路称为欧拉回路。具有欧拉回路的图称为欧拉图,定理 无向图G具有一条欧拉路，当且仅当G是连通的，且有零个或两个奇数度结点。 证明 必要性: 设G具有欧拉路，即有点边序列v0e1v1e2v2eiviei
3、+1ekvk，其中结点可能重复出现，但边不重复，因为欧拉路经过图G中每一个结点，故图G必连通的。对任意一个不是端点的结点vi，在一个欧拉路中每当vi出现一次，必关联两条边，故虽然vi可重复出现，但deg(vi)必是偶数。对于端点，若v0=vk，则deg(v0)为偶数，即G中无奇数度结点，若端点v0与vk不同，则deg(v0)为奇数，deg(vk )为奇数，G中就有两个奇数度结点。,充分性: 若图G连通，有零个或两个奇数度结点，我们构造一条欧拉路如下： 若有两个奇数独结点，则从其中的一个结点开始构造一条迹，即从v0出发关联e1“进入”v1，若deg(v1)为偶数，则必由v1再经过e2进入v2，如
4、此进行下去，每次仅取一次。由于G是连通的，故必可到达另一奇数度结点停下，得到一条迹L1：v0e1v1e2v2eiviei+1ekvk。若G中没有奇数度结点，则从任一结点v0出发，用上述的方法必可回到结点v0，得到上述一条闭迹L1。 若L1通过了G的所有边，则L1就是欧拉路。,若G中去掉L1后得到子图G，则G中每一点的度数为偶数，因原图是连通的，故L1与G至少有一个结点vi重合，在G中由vi出发重复的方法，得到闭迹L2。 当L1与L2组合在一起，如果恰是G，则即得欧拉路，否则重复可得到闭迹L3，以此类推直到得到一条经过图G中所有边的欧拉路。,推论 无向图G具有一条欧拉回路，当且仅当G是连通的，并
5、且所有结点度数为偶数。 由于有了欧拉路和欧拉回路的判别准则，因此哥尼斯堡七桥问题立即有了确切的答案，因为有四个结点的度数皆为奇数，故欧拉路必不存在。,与七桥问题类似的还有一笔划的判别问题，要判定一个图G是否可一笔划画出，有两种情况：一是从图G中某一结点出发，经过图G的每一边一次且仅一次到达另一结点。另一种就是从G的某个结点出发，经过G的每一边一次且仅一次回到该结点。上述两种情况可以由欧拉路和欧拉回路的判定条件给予解决。,欧拉路和欧拉回路的概念，很容易推广到有向图上去。 定义7-4.2 给定有向图G，通过每边一次且仅一次的一条单向路(回路)，称作单向欧拉路(回路)。,定理7-4.2有向图G具有一
6、条单向欧拉回路，当且仅当是连通的，且每个结点的入度等于出度。一个有向图G具有单向欧拉路，当且仅当是连通的，而且出两个结点外，每个结点的入度等于出度，但这两个结点中，一个结点的入度比出度大1。另一个结点的入度比出度小1。,这个定理的证明可以看作是无向图的欧拉路的推广，因为对于有向图的任意一个结点来说，如果入度与出度相等，则该结点的总度数为偶数，若入度和出度之差为1时，其总度数为奇数。因此定理的证明与定理7-4.1相似。,例3.1.3 计算机鼓轮设计。设有旋转鼓轮其表面等分成个部分。如图所示。,其中每一部分分别用绝缘体或导体组成。绝缘体部分给出信号为0，导体给出的信号为1，在图3.1.16中所示的
7、阴影部分为导体，空白部分表示绝缘体，根据图中鼓轮的位置，触点将得到信号为1101，如果将鼓轮顺时针方向转一个部分，触点将有信号1010。问鼓轮上的16个绝缘体和导体怎样安排，才能使鼓轮每旋转一个部分，四个触点能得到一组不同的四位二进制码。,设有八个结点的有向图，如图3.1.17所示，,其结点分别记三位二进制码000，001，010，011，100，101，110，111，设，从结点可引出两条有向边0和1。按照上述的方法，对于八个结点的有向图共有16条边，在这种图的任一条路中，其邻接的边必是和的形式，即是第一条边标号的后三位与第二条边标号的头三位相同。因为图中的16条边被记成不同的二进制数，可见
8、前述鼓轮转动所得的16个不同的位置触点的二进制码，即对应着图中的一条欧拉回路。图2.1.17每个结点的入度为2，出度也为2，图中的欧拉回路是0000，0001，0010，0100，1001，0011，0110，1101，1010，0101，1011，0111，1111，1110，1100，1000。根据相邻边的记法16个二进制数可写成对应的0-1码0000100110101111。将它安排成环状，既是所求的鼓轮。,上述的例子可以推广到有n个触点的鼓轮。,汉密尔顿回路,与欧拉回路非常类似的问题是汉密尔顿回路问题。1859年威廉汉密尔顿爵士在给他的朋友的一封信中，首先谈到关于十二面体的一个数学游戏
9、，能不能在下图中找到一条回路，使它含有这个图的结点？他把结点看作是一座城市，联结两个结点的边看成是交通线，于是它的问题是能不能找到旅行路线，沿着交通线经过每一个城市恰好一次，再回到原来的出发地？他把这个问题称为周游世界问题。,定义 汉密尔顿路，汉密尔顿回路 给定图G，若存在一条路经过图中的每一个结点恰好一次，这条路称作汉密尔顿路。若存在一条回路，经过图中的每一个结点恰好一次，这个回路称作汉密尔顿回路。 具有汉密尔顿回路的图称为汉密尔顿图。,定理 无向图具有汉密尔顿回路的必要条件 若图G=V，E具有汉密尔顿回路，则对于结点集V的每一个非空子集S均有W(GS)|S|成立。其中W(GS)是GS中连通
10、分支数。 证明 设C是G的一条汉密尔顿回路，则对于V的任何一个非空子集S在C中删去S中任一结点a1，则Ca1是连通非回路，若删去S中的另一个结点a2，则W(Ca1a2)2，由归纳法得知 W(CS) |S| 同时CS是GS的一个生成子图，因而 W(GS)W(CS) 所以 W(GS) |S|,利用该定理可以证明某些图是非汉密尔顿图。如下图 (a)中取S=v1,v4，则GS中有三个分图，故G不是汉密尔顿图。,这个方并不是总是有效的。例如，著名的彼得森(Pertersen)图，如上图 (b) 所示，在图中删去任一个结点或任意两个结点，不能使它不连通；删去三个结点，最多只能得到有两个连通分支的子图；删去
11、四个结点，最多只能得到有三个连通分支的子图；删去五个或五个以上的结点，余下的结点数都不大于5，故必不能有5个以上的连通分支数。所以该图满足W(CS)|S|，但是可以证明它非汉密尔顿图。,虽然汉密尔顿回路问题和欧拉回路问题在形式上极为相似，但对图G是否存在汉密尔顿回路还无充要的判别准则。下面我们给出一个无向图具有汉密尔顿路的充分条件。,定理 无向图具有汉密尔顿路的充分条件 设G具有n个结点的简单图，如果G中每一对结点的度数之和大于等于n-1，则在G中存在一条汉密尔顿路。 证明 我们首先证明G是连通的。若G有两个或更多互不连通的分图，设一个分图有n1个结点，任取一个结点v1，设另一个分图有n2个结
12、点，任取一个结点v2，因为d(v1)n11，d(v2)n21，故d(v1)+ d(v2) n1+ n22n1，这表明与题设矛盾，故G必连通。 其次，我们从一条边出发构成一条路，证明它是汉密尔顿路。,设在G中有p1条边的路，pn，它的结点序列为v1，v2，vp。如果有v1或vp邻接于不在这条路上的一个结点，我们可立即扩展这条路，使它包含这一个结点，从而得到p条边的路。否则，v1和vp都只能邻接于这条路上的结点，我们证明在这种情况下，存在一条回路包含结点v1，v2，vp。若v1邻接于vp，则v1，v2，vp，v1即为所求的回路。假设与v1邻接的结点集是，这里2l，m，tp-1，如果是邻接于vl-1
13、，vm-1，vj-1，vt-1中之一，譬如说vj-1，如图1.1.20 (a)所示，v1v2v3vj-1vpvp-1vjv1是所求的包含结点的回路v1，v2，vp。,如果vp不邻接于vl-1，vm-1，vj-1，vt-1中任一个，则vp至少邻接于pk1个结点，deG(vp)p-k-1，deG(v1) k，故deG(vp)deG(v1) p-k-1+ k= p- 1n-1，即v1与vp度数之和至多为n-2，得到矛盾。 至此，我们有包含所有结点v1，v2，vp的一条回路，因为G是连通的，所以在G中必有一个不属于该回路的结点vx与v1，v2，vp中的每一个结点vk邻接，如图1.1.20(b)所示，于
14、是就得到一条包括p条边的路(vx，vk，vk+1，vj-1，vp，vp-1，vj，v1，v2，vk-1)。如图3.1.20(c)所示，重复前述的构造方法，直到得到n-1条边的路。,容易看出，定理7-4.4的条件是图中的汉密尔顿路的存在的充分条件，但是并不是必要的条件。设图是n边形，如图所示， 其中n=6虽然任何两个结点度数的和是461，但在G中有一条汉密尔顿路。,例题1： 考虑在七天内安排七们功课的考试，使得同一位教师所任的两们课程考试不安排在接连的两天里，试证如果没有教师担任多于四门课程，则符合上述要求的考试安排总是可能的。,证明 设G为七个结点的图，每一个结点对应一们功课的考试，如果这两个
15、结点对应的课程的考试是由不同教师担任的，那么这两个结点之间有一条边，因为每个教师所任的课程不超过4，故每个结点的度数至少是3，任两个结点度数的和至少是6，故G总包含一条汉密尔顿路，它对应于一个七门考试课目的一个适当安排。,定理 无向图具有汉密尔顿回路的充分条件 设图G是具有n个结点的简单图，如果G中每一对结点的度数大于等于n，则在G中存在一条汉密尔顿回路。 证明 由定理7-4.4可知必有一条汉密尔顿路，设为v1v2vn，如果v1与vn邻接，则定理得证。 如果v1与vn不邻接，假设v1邻接，2ijn-1，可以证明vn必邻接于中之一。如果不邻接于中的任意一点，则vn至多邻接于n-k-1个结点，因而
16、d(vn)nk1，而d(v1)= k，故d(v1)+ d(vn) nk1+ k= n-1，与题设矛盾，所以必有汉密尔顿回路v1v2vj-1vnvn-1vjv1 。,给定图G=V，E有n个结点，若将图G中度数之和至少是n的非邻接结点连接起来得图G，对图G重复上述步骤，直到不再有这样的结点为止，所得的图，称为原图G的闭包，记作C(G)。,如图3.1.23 给出了六个结点的一个图，构造它的闭包过程。在这个例子中C(G)是一个完全图。一般情况下，C(G)也可能不是一个完全图。,定理3.1.19当且仅当一个简单图的闭包是汉密尔顿图时，这个简单图是汉密尔顿图。 证明 略。,作业7-4,P 311 (7) (9),
