离散数学 7-4 欧拉图和汉

1、7-4欧拉图和汉密尔顿图,要求：1、理解欧拉图、汉密尔顿图的定义。2、掌握欧拉图的判定方法。3、会判断一些图不是汉密尔顿图。4、熟悉一些欧拉图和汉密尔顿图。,一、欧拉图1、哥尼斯堡七桥问题,近代图论的历史可追溯到18世纪的七桥问题穿过哥尼斯堡城的七座桥，要求每座桥通过一次且仅通过一次。,七桥问题等价于在图中求一条回路，此回路经过每条边一次且仅有一次。欧拉在1736年的论文中提出了一条简单的准则，确定了哥尼斯堡七桥问题是不能解的。,2、欧拉图(Euler),如果无孤立结点图G上有一条经过G的所有边一次且仅一次的路径，则称该路径为图G的欧拉路径（Eulerwalk）。如果图G上有一条经过G边一次且

2、仅一次的的回路，则称该回路为图G的欧拉回路。具有欧拉回路的图称为欧拉图（Eulergraph）。,定理7-4.1无向图G具有一条欧拉路，当且仅当G连通，并且有零个或两个奇数度结点。,证明思路：1)先证必要性:G有欧拉路G连通且（有0个或2个奇数度结点）设G的欧拉路是点边序列v0e1v1e2ekvk，其中结点可能重复，但边不重复。因欧拉路经过（所有边）所有结点，所以图G是连通的。对于任一非端点结点vi，在欧拉路中每当vi出现一次，必关联两条边，故vi虽可重复出现，但是deg(vi)必是偶数。对于端点,若v0=vk，则deg(v0)必是偶数，即G中无奇数度结点。若v0vk，则deg(v0)必是奇数

3、，deg(vk)必是奇数,即G中有两个奇数度结点。必要性证完。,2)再证充分性:(证明过程给出了一种构造方法)G连通且（有0个或2个奇数度结点）G有欧拉路(1)若有2个奇数度结点,则从其中一个结点开始构造一条迹,即从v0出发经关联边e1进入v1,若deg(v1)为偶数,则必可由v1再经关联边e2进入v2,如此下去,每边仅取一次,由于G是连通的,故必可到达另一奇数度结点停下,得到一条迹L1:v0e1v1e2ekvk。若G中没有奇数度结点,则从任一结点v0出发,用上述方法必可回到结点v0,得到一条闭迹。(2)若L1通过了G的所有边,L1就是一条欧拉路。(3)若G中去掉L1后得到子图G,则G中每个结

4、点度数都为偶数,因为原来的图G是连通的,故L1与G至少有一个结点vi重合,在G中由vi出发重复(1)的方法,得到闭迹L2。(4)当L1与L2组合,若恰是G,得欧拉路,否则重复(3),可得闭迹L3,依此类推可得一条欧拉路。充分性证完,由于有了欧拉路和欧拉回路的判别准则，因此哥尼斯堡七桥问题立即有了确切的否定答案，因为从图中可以看到deg(A)5，deg(B)deg(C)deg(D)=3，故欧拉回路必不存在。,定理7-4.1的推论无向图G具有一条欧拉回路，当且仅当G连通且所有结点度数皆为偶数。,4、一笔画问题要判定一个图G是否可一笔画出，有两种情况：一是从图G中某一结点出发，经过图G的每一边一次仅

5、一次到达另一结点。另一种就是从G的某个结点出发，经过G的每一边一次仅一次再回到该结点。,v1,v2,v3,v4,v5,为欧拉路，有从v2到v3的一笔画。为欧拉回路，可以从任一结点出发，一笔画回到原出发点。,5.定义7-4.2：给定有向图G，通过图中每边一次且仅一次的一条单向路（回路），称作单向欧拉路（回路）。,可以将欧拉路和欧拉回路的概念推广到有向图中。,6.定理7-4.2(1)有向图G为具有一条单向欧拉回路，当且仅当G连通，并且每个结点的入度等于出度。(2)有向图G有单向欧拉路，当且仅当G连通，并且恰有两个结点的入度与出度不等，它们中一个的出度比入度多1，另一个入度比出度多1。证明思路与定理

6、7-4.1类似,例1有向欧拉图应用示例：计算机鼓轮的设计。鼓轮表面分成24=16等份，其中每一部分分别用绝缘体或导体组成，绝缘体部分给出信号0，导体部分给出信号1，在下图中阴影部分表示导体，空白体部分表示绝缘体，根据鼓轮的位置，触点将得到信息4个触点a,b,c,d读出1101(状态图中的边e13),转一角度后将读出1010(边e10)。问鼓轮上16个部分怎样安排导体及绝缘体才能使鼓轮每旋转一个部分，四个触点能得到一组不同的四位二进制数信息。,0,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,1,1,1,0,a,b,c,d,设有一个八个结点的有向图，如下图所示。其结点分别记为三位二

7、进制数000，001，111，设ai0,1，从结点a1a2a3可引出两条有向边，其终点分别是a2a30以及a2a31。该两条边分别记为a1a2a30和a1a2a31。按照上述方法，对于八个结点的有向图共有16条边，在这种图的任一条路中，其邻接的边必是a1a2a3a4和a2a3a4a5的形式，即是第一条边标号的后三位数与第二条边的头三位数相同。由于图中16条边被记为不同的二进制数，可见前述鼓轮转动所得到16个不同位置触点上的二进制信息，即对应于图中的一条欧拉回路。,010,101,110,100,011,001,111,000,e10=1010,e13=1101,e5=0101,e3=0011,

8、e11=1011,e6=0110,e7=0111,e14=1110,e15=1111,e12=1100,e2=0010,e4=0100,e1=0001,e8=1000,e9=1001,e0=0000,a1a2a3(=000)0,a1a2a3(=000)1,a1a2a3(=001)1,a1a2a3(=100)0,a1a2a3(=111)0,a1a2a3(=111)1,a1a2a3(=110)0,a1a2a3(=011)1,所求的欧拉回路为：e0e1e2e4e9e3e6e13e10e5e11e7e16e14e12e8(e0)（从图示位置开始）e13e10e5e11e7e16e14e12e8e0e1

9、e2e4e9e3e6(e13)所求的二进制序列为：0000100110101111(0)1101011110000100(1)（从图示位置开始）,上述结论可推广到鼓轮具有n个触点的情况。构造2n-1个结点的有向图，每个结点标记为n-1位二进制数,从结点a1a2a3.an-1出发,有一条终点为a2a3.an-10的边,该边记为a1a2a3.an-10；还有一条终点标记为a2a3.an-11的边,该边记为a1a2a3.an-11。邻接边的标记规则为：“第一条边后n-1位与第二条边前n-1位二进制数相同”。哈密尔顿回路问题见图7-4.6。,二、汉密尔顿图,与欧拉回路类似的是汉密尔顿回路。它是1859

10、年汉密尔顿首先提出的一个关于12面体的数学游戏：能否在图7-4.6中找到一个回路，使它含有图中所有结点一次且仅一次？若把每个结点看成一座城市，连接两个结点的边看成是交通线，那么这个问题就变成能否找到一条旅行路线，使得沿着该旅行路线经过每座城市恰好一次，再回到原来的出发地？他把这个问题称为周游世界问题。,定义7-4.3：给定图G，若存在一条路经过图中的每个结点恰好一次，这条路称作汉密尔顿路。若存在一条回路，经过图中的每个结点恰好一次，这条回路称作汉密尔顿回路。具有汉密尔顿回路的图称作汉密尔顿图。,二、汉密尔顿图,图7-4.6存在一条汉密尔顿回路，它是汉密尔顿图,2、定理7-4.3若图G具有汉密尔

11、顿回路，则对于结点集V的每个非空子集S均有W(G-S)|S|，其中W(G-S)是G-S的连通分支数。,证明设C是G的一条汉密尔顿回路，对于V的任何一个非空子集S，在C中删去S中任一结点a1，则C-a1是连通的非回路，W(C-a1)=1，|S|1，这时W(C-S)|S|。若再删去S中另一结点a2，则W(C-a1-a2)2，而|S|2，这时W(C-S)|S|。由归纳法可得：W(C-S)|S|。同时C-S是G-S的一个生成子图，因而W(G-S)W(C-S)，所以W(G-S)|S|。,C经过图G的每个结点恰好一次，C与G的结点集合是同一个，因此C-S与G-S的结点集合是同一个，,定理7-4.3是必要条

12、件，可以用来证明一个图不是汉密尔顿图。,如右图，取S=v1,v4，则G-S有3个连通分支，,不满足W(G-S)|S|，故该图不是汉密尔顿图。,所以用此定理来证明某一特定图不是汉密尔顿图并不是总是有效的。例如，著名的彼得森(Petersen)图，在图中删去任一个结点或任意两个结点，不能使它不连通；删去3个结点，最多只能得到有两个连通分支的子图；删去4个结点，只能得到最多三个连通分支的子图；删去5个或5个以上的结点，余下子图的结点数都不大于6，故必不能有5个以上的连通分支数。所以该图满足W(G-S)|S|，但是可以证明它不是汉密尔顿图。,说明：此定理是必要条件而不是充分条件。有的图满足此必要条件，

13、但也不是汉密尔顿图。,3.定理7-4.4设图G具有n个结点的简单图,如果G中每一对结点度数之和大于等于n-1,则G中存在一条汉密尔顿路。,证明思路：1)先证G连通:若G有两个或多个互不连通的分支,设一个分图有n1个结点,任取一个结点v1,另一分图有n2个结点,任取一个结点v2,因为deg(v1)n1-1,deg(v2)n2-1,deg(v1)+deg(v2)n1+n2-2n-1,与假设矛盾,G是连通的。,2)先证(构造)要求的汉密尔顿路存在:不要求掌握！,2)先证(构造)要求的汉密尔顿路存在:设G中有p-1条边的路,pn,它的结点序列为v1,v2,vp。如果有v1或vp邻接于不在这条路上的一个

14、结点,立刻扩展该路,使它包含这个结点,从而得到p条边的路。否则v1和vp都只邻接于这条路上的结点,我们证明在这种情况下,存在一条回路包含结点v1,v2,vp。,若v1邻接于vp,则v1,v2,vp即为所求。若v1邻接于结点集vl,vm,vj,vt中之一,这里2l,m,.,j,.,tp-1,如果vp是邻接于vl-1,vm-1,vj-1,vt-1中之一,譬如是vj-1,则v1v2vj-1vpvp-1.vjv1是所求回路（如图7-4.9(a)所示）。如果vp不邻接于vl-1,vm-1,vj-1,vt-1中任一个,则vp最多邻接于p-k-1个结点,deg(vp)p-k-1,deg(v1)=k,故deg

15、(vp)+deg(v1)p-k-1+kn-1,即v1与vp度数之和最多为n-2，得到矛盾。,至此，已经构造出一条包含结点v1,v2,vp的回路,因为G是连通的,所以在G中必有一个不属于该回路的结点vx与回路中某一结点vk邻接,如图7-4.9(b)所示,于是就得到一条包含p条边的回路(vx,vk,vk+1,vj-1,vp,vp-1,vj,v1,v2,vk-1),如图7-4.9(c)所示,重复前述构造方法，直到得到n-1条边的路。,说明：该定理的条件是充分条件但不是必要条件。例：见308页图7-4.10。n=6，每一对结点度数之和等于4，小于n-1，但在G中存在一条汉密尔顿路。,3.定理7-4.4

16、设图G具有n个结点的简单图,如果G中每一对结点度数之和大于等于n-1,则G中存在一条汉密尔顿路。,例某地有5个风景点，若每个景点均有两条道路与其他景点相通，问是否可经过每个景点一次而游完这5处。,解将景点作为结点，道路作为边，则得到一个有5个结点的无向图。由题意，对每个结点vi(i=1,2,3,4,5)有deg(vi)=2。则对任两点和均有deg(vi)+deg(vj)=2+2=4=51所以此图有一条汉密尔顿回路。即经过每个景点一次而游完这5个景点。,例：在七天内安排七门课程的考试，使得同一位教师所任的两门课程不排在接连的两天中，试证明如果没有教师担任多于四门课程，则符合上述要求的考试安排总是

17、可能的。,证明：设G为具有七个结点的图，每个结点对应于一门课程考试，如果这两个结点对应的课程考试是由不同教师担任的，那么这两个结点之间有一条边，因为每个教师所任课程数不超过4，故每个结点的度数至少是3，任两个结点的度数之和至少是6，故G总是包含一条汉密尔顿路，它对应于一个七门考试课程的一个适当的安排。,4.定理7-4.5设图G具有n个结点的简单图,如果G中每一对结点度数之和大于等于n,则G中存在一条汉密尔顿回路。证明：略,5、图的闭包定义7-4.4：给定图G=有n个结点，若将图G中度数之和至少是n(n)的非邻接结点连接起来得图G，对图G重复上述步骤，直到不再有这样的结点对存在为止，所得到的图，

18、称为是原图G的闭包，记作C(G)。,在这个例子中C(G)是完全图，一般情况下，C(G)也可能不是完全图。,6、定理7-4.6：当且仅当一个简单图的闭包是汉密尔顿图时，这个简单图是汉密尔顿图。7、推论：n3的有向(无向)完全图Kn为汉密尔顿图。,判别汉密尔顿路不存在的标号法,关于图中没有汉密尔顿路的判别尚没有确定的方法。介绍一个判别汉密尔顿路不存在的标号法。,例证明下图没有汉密尔顿路。,任取一结点如v1,用A标记，所有与它邻接的结点标B。,继续不断地用A标记所有与B邻接的结点，用B标记所有与A邻接的结点，直到图中的所有结点全部标记完毕。,作业,P311：（2）（6）（9）,7-5平面图,一、平面

19、图1、定义7-5.1如果无向图G=的所有结点和边可以在一个平面上图示出来，而使各边仅在顶点处相交。无向图G称为平面图（planargraph），否则称G为非平面图。,有些图形从表面看有几条边是相交的，但是不能就此肯定它不是平面图。例如，下面左图表面看有几条边相交，但如把它画成右图，则可看出它是一个平面图。,有些图形不论怎样改画，除去结点外，总有边相交，故它是非平面图。,定义7-5.2设图G=是一连通平面图，由图中各边所界定的区域称为平面图的面(regions)。有界的区域称为有界面，无界的区域称为无界面。界定各面的闭的拟路径称为面的边界(boundary).面r的边界长度称为面r的度（degr

20、ee）记为deg(r)，又称为面r的次数。,2、面、边界,例如图7-5.3,deg(r1)=3deg(r2)=3deg(r3)=5deg(r4)=4deg(r5)=3,deg(r1)+deg(r2)+deg(r3)+deg(r4)+deg(r5)=18,如边是两个面的分界线，该边在两个面的度数中各记1次。如边不是两个面的分界线(称为割边)则该边在该面的度数中重复记了两次，故定理结论成立。,3.定理7-5.1设G为一有限平面图，面的次数之和等于其边数的两倍。,证明思路：任一条边或者是两个面的共同边界（贡献2次），或者是一个面的重复边（贡献2次）,4、欧拉定理定理7-5.2（欧拉定理）设G为一平面

21、连通图，v为其顶点数，e为其边数，r为其面数，那么欧拉公式成立ve+r=2,证明（1）若G为一个孤立结点，则v=1，e=0，r=1，故v-e+r=2成立。,（2）若G为一个边，即v=2，e=1，r=1，则v-e+r=2成立。,（3）设G为k条边时，欧拉公式成立，即vk-ek+rk=2。考察的情况。,因为在k条边的连通图上增加一条边，使它仍为连通图，只有下述两种情况：,加上一个新结点b，b与图上的一点a相连，此时vk和ek两者都增加1，而面数rk没变，故（vk+1）-（ek+1）+rk=vk-ek+rk=2。,用一条边连接图上的已知两点，此时ek和rk都增加1，结点数vk没变，故vk-（ek+1

22、）+（rk+1）=vk-ek+rk=2。,例：已知一个平面图中结点数v=10，每个面均由4条边围成，求该平面图的边数和面数。,解：因每个面的次数均为4，则2e=4r，即e=2r，又v=10，代入欧拉公式v-e+r=2有10-2r+r=2解得r=8，则e=2r=16。,5.定理7-5.3设G为一简单连通平面图，其顶点数v3，其边数为e，那么e3v6,证明思路：设G的面数为r,当v=3,e=2时上式成立,若e=3,则每一面的次数不小于3,各面次数之和不小于2e,因此2e3r,r2e/3代入欧拉公式:2=v-e+rv-e+2e/3整理后得:e3v6说明：这是简单图是平面图的必要条件。本定理的用途:判

23、定某图是非平面图。,例如：K5中e=10，v=5，3v-6=9，从而e3v-6，所以K5不是平面图。,定理7-5.3的条件不是充分的。如K3,3图满足定理7-5.3的条件（v=6，e=9，3v-6=12，e3v-6成立），但K3,3不是平面图。,315页例2证明K3,3图不是平面图。,在K3,3中有6个结点9条边，2v-4=26-4=89,与2v-4e矛盾，故K3,3不是平面图。,证明假设K3,3图是平面图。,在K3,3中任取三个结点，其中必有两个结点不邻接，故每个面的次数都不小于4，由4r2e，re/2，即v-e+e/2v-e+r=2，v-e/22，2v-e4，2v-4e。,6、定义7-5.

24、3：给两图G1和G2，或者它们是同构的，或者反复地插入或去掉二度结点后，使G1和G2同构，则称G1和G2是在2度结点内同构的，也称G1和G2是同胚的。,在给定图G的边上，插入一个新的度数为2的结点，使一条边分成两条边，或者对于关于度数为2的结点的两条边，去掉这个结点，使两条边化成一条边，这些都不会影响图的平面性。,7、库拉托夫斯基定理(Kuratowski定理)定理7-5.4：一个图是平面图的充要条件是它不含与K5或K3，3在二度结点内同构的子图。,欧拉公式有时可以用来判定某个图是非平面图。下面的库拉托夫斯基定理给出了判定一个图是平面图的充要条件.,K3，3,K5,K5和K3，3常称作库拉托夫

25、斯基图。,作业,P317：（1）（2）,7-6对偶图与着色,掌握对偶图的定义，会画图G的对偶图G*掌握自对偶图的定义及必要条件。,与平面图有密切关系的一个图论的应用是图形的着色问题，这个问题最早起源于地图的着色，一个地图中相邻国家着以不同颜色，那么最少需用多少种颜色？一百多年前，英国格色里(Guthrie)提出了用四种颜色即可对地图着色的猜想，1879年肯普(Kempe)给出了这个猜想的第一个证明，但到1890年希伍德(Hewood)发现肯普证明是错误的，但他指出肯普的方法虽不能证明地图着色用四种颜色就够了，但可证明用五种颜色就够了，即五色定理成立。,此后四色猜想一直成为数学家感兴趣而未能解决

26、的难题。直到1976年美国数学家阿佩尔和黑肯宣布：他们用电子计算机证明了四色猜想是成立的。所以从1976年以后就把四色猜想这个名词改成“四色定理”了。为了叙述图形着色的有关定理，下面先介绍对偶图的概念。,一、对偶图1、对偶图定义7-6.1对具有面F1,F2,.,Fn的连通平面图G=实施下列步骤所得到的图G*称为图G的对偶图（dualofgraph）：,如果存在一个图G*=满足下述条件：,（a）在G的每一个面Fi的内部作一个G*的顶点vi*。即对图G的任一个面Fi内部有且仅有一个结点vi*V*。,(b)若G的面Fi，Fj有公共边ek，则作ek*=(vi*，vj*)，且ek*与ek相交。即若G中面

27、Fi与Fj有公共边界ek，那么过边界的每一边ek作关联vi*与vj*的一条边ek*=(vi*,vj*)。ek*与G*的其它边不相交。,(c)当且仅当ek只是一个面Fi的边界时(割边)，vi*存在一个环e*k与ek相交。即当ek为单一面Fi的边界而不是与其它面的公共边界时，作vi*的一条环与ek相交（且仅交于一处）。所作的环不与G*的边相交。,则称图G*为G的对偶图。,实线边图为平面图，虚线边图为其对偶图。,v*=r，e*=e，r*=v,2、自对偶图定义7-6.2如果图G的对偶图G*同构于G,则称G是自对偶图。,二、图的着色1、问题的提出该问题起源于地图的着色问题。图着色的三种情况:对点着色是对

28、图G的每个结点指定一种颜色，使得相邻结点的颜色不同;对边着色给每条边指定一种颜色使得相邻的边的颜色不同，给面着色给每个面指定一种颜色使得有公共边的两个面有不同的颜色。对边着色和对面着色均可转化为对结点着色问题。,从对偶图的概念，可以看到，对于地图的着色问题，可以归纳为对于平面图的结点的着色问题，因此四色问题可以归结为要证明对于任何一个平面图，一定可以用四种颜色，对它的结点进行着色，使得邻接的结点都有不同的颜色。,2、图的正常着色：图G的正常着色(或简称着色)是指对它的每一个结点指定一种颜色，使得没有两个邻接的结点有同一种颜色。如果图在着色时用了n种颜色，我们称G为n-色的图。3、色数：对于图G着色时，需要的最少颜色数称为G的色数，记作x(G)。,证明一个图的色数为n，首先必须证明用n种颜色可以着色该图，其次证明用少于n种颜