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

1、7-4 欧拉图和汉密尔顿图欧拉图和汉密尔顿图要求：要求：1、理解欧拉图、汉密尔顿图的定义。、理解欧拉图、汉密尔顿图的定义。2、掌握欧拉图的判定方法。、掌握欧拉图的判定方法。3、会判断一些图不是汉密尔顿图。、会判断一些图不是汉密尔顿图。4、熟悉一些欧拉图和汉密尔顿图。、熟悉一些欧拉图和汉密尔顿图。一、欧拉图一、欧拉图1、哥尼斯堡七桥问题、哥尼斯堡七桥问题ABCDn近代图论的历史可追溯到近代图论的历史可追溯到18世纪的世纪的七桥问题七桥问题穿过穿过哥尼斯堡哥尼斯堡城的七座桥，城的七座桥，要求每座桥通过一次要求每座桥通过一次且仅通过一次。且仅通过一次。七桥问题等价于在图中求一条回路，此回路经过七桥问

2、题等价于在图中求一条回路，此回路经过每条边一次且仅有一次。欧拉在每条边一次且仅有一次。欧拉在1736年的论文中年的论文中提出了一条简单的准则，确定了哥尼斯堡七桥问提出了一条简单的准则，确定了哥尼斯堡七桥问题是不能解的。题是不能解的。2、欧拉图、欧拉图(Euler) 如果无孤立结点图如果无孤立结点图G上有一条经过上有一条经过G的的所有边一所有边一次且仅一次的路径，则称该路径为图次且仅一次的路径，则称该路径为图G的的（Euler walk）。）。如果图如果图G上有一条经过上有一条经过G边一次且仅一次的的回路，边一次且仅一次的的回路，则称该回路为图则称该回路为图G的的（Euler graph）。）。

3、定理定理7-47-4.1 无向图无向图G具有一条具有一条欧拉路欧拉路，当且仅当，当且仅当G连通，并且有零个或两个奇数度结点。连通，并且有零个或两个奇数度结点。 证明思路：证明思路：1 1) ) 先证必要性先证必要性: : G有欧拉路有欧拉路 GG的欧拉路是点边序列的欧拉路是点边序列v0e1v1e2 ekvk，其中结点可能重复，其中结点可能重复，但边不重复。因欧拉路经过（所有边但边不重复。因欧拉路经过（所有边）所有结点，所以图）所有结点，所以图G是连通的。是连通的。viviviviv0=vkv0Gv0vkv0vkG必要性证完。必要性证完。 2)2)再证充分性再证充分性:(:(证明过程给出了一种构

4、造方法证明过程给出了一种构造方法) ) G G有欧拉路有欧拉路 v0e1v1v1v1e2v2Gv0e1v1e2 ekvkGv0v0GGGGGGviGviG充分性证完充分性证完 由于有了欧拉路和欧拉回路的判别准则，因此哥由于有了欧拉路和欧拉回路的判别准则，因此哥尼斯堡七桥问题立即有了确切的否定答案，因为从图尼斯堡七桥问题立即有了确切的否定答案，因为从图中可以看到中可以看到deg(A)5，deg(B)deg(C)deg(D)=3，故欧拉回路必不存在。故欧拉回路必不存在。定理定理7-47-4.1的推论的推论 无向图无向图G具有一条具有一条欧拉回路欧拉回路，当且，当且仅当仅当G连通且所有结点度数皆为偶

5、数。连通且所有结点度数皆为偶数。4、一笔画问题、一笔画问题要判定一个图要判定一个图G是否可一笔画出，有两种情况：是否可一笔画出，有两种情况：n一是从图一是从图G中某一结点出发，经过图中某一结点出发，经过图G的每一边一的每一边一次仅一次到达另一结点。次仅一次到达另一结点。n另一种就是从另一种就是从G的某个结点出发，经过的某个结点出发，经过G的每一边的每一边一次仅一次再回到该结点。一次仅一次再回到该结点。v1v2v3v4v5为欧拉路，有从为欧拉路，有从v2到到v3的一笔画。的一笔画。为欧拉回路，可以从任一结点出发，一笔画回到原为欧拉回路，可以从任一结点出发，一笔画回到原出发点。出发点。 5.定义定

6、义7-4.2：给定有向图：给定有向图G，通过图中每边一次，通过图中每边一次且仅一次的一条单向路（回路），称作单向欧拉路且仅一次的一条单向路（回路），称作单向欧拉路（回路）。（回路）。可以将可以将欧拉路和欧拉回路的概念推广到有向图中。欧拉路和欧拉回路的概念推广到有向图中。 6. 6.定理定理7-47-4.2 (1)有向图有向图G为具有一条为具有一条单向欧拉单向欧拉回路回路，当且仅当，当且仅当G连通连通，并且每个结点的，并且每个结点的入度等于出入度等于出度度。(2)有向图有向图G有有单向欧拉路单向欧拉路，当且仅当，当且仅当G连通连通，并，并且恰有两个结点的入度与出度不等，且恰有两个结点的入度与出度

7、不等，它们中一个的它们中一个的出度比入度多出度比入度多1 1，另一个入度比出度多，另一个入度比出度多1 1。 证明思路与证明思路与定理定理7-47-4.1类似类似 例例1 1有向欧拉图应用示例：有向欧拉图应用示例：计算机鼓轮的设计计算机鼓轮的设计。 鼓轮表面分成鼓轮表面分成24=16等份，其中每一部分分别用绝等份，其中每一部分分别用绝缘体或导体组成，绝缘体部分给出信号缘体或导体组成，绝缘体部分给出信号0，导体部分给，导体部分给出信号出信号1，在下图中阴影部分表示导体，空白体部分表，在下图中阴影部分表示导体，空白体部分表示绝缘体，根据鼓轮的位置，触点将得到信息示绝缘体，根据鼓轮的位置，触点将得到

8、信息4个触点个触点a,b,c,d读出读出1101(状态图中的边状态图中的边e13),转一角度后将读出转一角度后将读出1010 (边边e10)。 问鼓轮上问鼓轮上16个部分怎样安排导体及绝缘体才能使鼓个部分怎样安排导体及绝缘体才能使鼓轮每旋转一个部分，四个触点能得到一组不同的四位二轮每旋转一个部分，四个触点能得到一组不同的四位二进制数信息。进制数信息。01111111100000001110abcd 设有一个八个结点的有向图，如下图所示。其结点分别记为设有一个八个结点的有向图，如下图所示。其结点分别记为三位二进制数三位二进制数000，001，111，设设ai 0,1，从结点，从结点a1 a2 a

9、3可引出两条有向边，其终点分别是可引出两条有向边，其终点分别是a2 a30以及以及a2 a31。该两条边分别记为。该两条边分别记为a1 a2 a30和和a1 a2 a31。按照上述方法，对于八个结点的有向图共有按照上述方法，对于八个结点的有向图共有16条边，在这种图的条边，在这种图的任一条路中，其邻接的边必是任一条路中，其邻接的边必是a1 a2 a3a4和和a2 a3a4a5的形式，即是第的形式，即是第一条边标号的后三位数与第二条边的头三位数相同。一条边标号的后三位数与第二条边的头三位数相同。 由于图中由于图中16条边被记为不同的二进制数，可见前述鼓轮转动所条边被记为不同的二进制数，可见前述鼓

10、轮转动所得到得到16个不同位置触点上的二进制信息，即对应于图中的一条欧个不同位置触点上的二进制信息，即对应于图中的一条欧拉回路。拉回路。010101110100011001111000e10=1010e13=1101e5=0101e3=0011e11=1011e6=0110e7=0111e14=1110e15=1111e12=1100e2=0010e4=0100e1=0001e8=1000e9=1001e0=0000a1 a2 a3 (=000) 0a1 a2 a3 (=000) 1a1 a2 a3 (=001) 1a1 a2 a3 (=100) 0a1 a2 a3 (=111) 0a1 a2

11、 a3 (=111) 1a1 a2 a3 (=110) 0a1 a2 a3 (=011) 1 所求的欧拉回路为：所求的欧拉回路为： e0e1e2e4e9e3e6e13e10e5e11e7e16e14e12e8(e0) （从图示位置开始）（从图示位置开始） e13e10e5e11e7e16e14e12e8e0e1e2e4e9e3e6 (e13) 所求的二进制序列为：所求的二进制序列为： 0000100110101111 (0) 1101011110000100 (1) （从图示位置开始）（从图示位置开始） 上述结论可推广到鼓轮具有上述结论可推广到鼓轮具有n n个触点的情况。构造个触点的情况。构造

12、2 2n-1n-1 个结点的有向图，每个结点标记为个结点的有向图，每个结点标记为n-1n-1位二进制数位二进制数, ,从结点从结点a1a2a3.an-1出发出发, ,有一条终点为有一条终点为a2a3.an-10的边的边, ,该边记为该边记为a1a2a3.an-10；还有一条终点标记为；还有一条终点标记为a2a3.an-11的边的边, ,该边记该边记为为a1a2a3.an-11 。邻接边的标记规则为：。邻接边的标记规则为：“第一条边后第一条边后n-n-1 1位与第二条边前位与第二条边前n-1n-1位二进制数相同位二进制数相同”。 哈密尔顿回路问题见图哈密尔顿回路问题见图7-4.67-4.6。二、

13、汉密尔顿图二、汉密尔顿图与欧拉回路类似的是与欧拉回路类似的是汉密尔顿回路。汉密尔顿回路。它是它是1859年汉密尔顿首先提出的一个关于年汉密尔顿首先提出的一个关于12面体面体的数学游戏：能否在图的数学游戏：能否在图7-4.6中找到一个回路，使它中找到一个回路，使它含有图中所有结点一次且仅一次？含有图中所有结点一次且仅一次？若把每个结点看成一座城市，连接两个结点的边看若把每个结点看成一座城市，连接两个结点的边看成是交通线，那么这个问题就变成能否找到一条旅成是交通线，那么这个问题就变成能否找到一条旅行路线，使得沿着该旅行路线经过每座城市恰好一行路线，使得沿着该旅行路线经过每座城市恰好一次，再回到原来

14、的出发地？他把这个问题称为周游次，再回到原来的出发地？他把这个问题称为周游世界问题。世界问题。定义定义7-4.3：给定图：给定图G，n若存在一条路经过图中的每个结点恰好一次，若存在一条路经过图中的每个结点恰好一次，这条路称作这条路称作汉密尔顿路汉密尔顿路。n若存在一条回路，经过图中的每个结点恰好若存在一条回路，经过图中的每个结点恰好一次，这条回路称作一次，这条回路称作汉密尔顿回路汉密尔顿回路。n具有汉密尔顿回路的图称作具有汉密尔顿回路的图称作汉密尔顿图汉密尔顿图。二、汉密尔顿图二、汉密尔顿图图图7-4.6存在一条汉密尔顿回路，它是汉密尔顿图存在一条汉密尔顿回路，它是汉密尔顿图2、定理、定理7-

15、4.3 若图若图G具有汉密尔顿回路，则对具有汉密尔顿回路，则对于结点集于结点集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|。由

16、归纳法可得：由归纳法可得：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是必要条件，可以用来证明一个图不是汉是必要条件，可以用来证明一个图不是汉密尔顿图。密尔顿图。如右图，取如右图，取S=v1,v4，则则G-S有有3个连通分支，个连通分支，不满足不满足W(G-S)|S|，故故该该图不是汉密尔顿图。图不是汉密尔顿图。 所以所以用此定理来证明某一特定图不是汉密尔顿图并不是用此定理来证明某一

17、特定图不是汉密尔顿图并不是总是有效的。例如，著名的彼得森总是有效的。例如，著名的彼得森(Petersen)图，在图中删图，在图中删去任一个结点或任意两个结点，不能使它不连通；删去去任一个结点或任意两个结点，不能使它不连通；删去3个结个结点，最多只能得到有两个连通分支的子图；删去点，最多只能得到有两个连通分支的子图；删去4个结点，只个结点，只能得到最多三个连通分支的子图；删去能得到最多三个连通分支的子图；删去5个或个或5个以上的结点，个以上的结点，余下子图的结点数都不大于余下子图的结点数都不大于6，故必不能有，故必不能有5个以上的连通分个以上的连通分支数。所以该图满足支数。所以该图满足W(G-S

18、)|S|，但是可以证明它不是汉密，但是可以证明它不是汉密尔顿图。尔顿图。说明：此定理是必要条件而不是充分条件。有的图满足此必说明：此定理是必要条件而不是充分条件。有的图满足此必要条件，但也不是要条件，但也不是汉密尔顿图。汉密尔顿图。3.定理定理7-47-4.4 设图设图G具有具有n个结点的简单图个结点的简单图,如果如果G中每一对结点度数之和大于等于中每一对结点度数之和大于等于n-1,则则G中存在中存在一条汉密尔顿路。一条汉密尔顿路。 证明思路：证明思路：1 1) ) 先证先证G: :G有两个或多个互不连通的分支有两个或多个互不连通的分支,设一个分图设一个分图有有n1个结点个结点,任取一个结点任

19、取一个结点v1,另一分图有另一分图有n2个结点个结点,任取一个结点任取一个结点v2,因为因为v1n1-1-1, v2n2-1-1, v1+ + v2n1+ +n2-2n-1-2n-1 ,与假设矛盾与假设矛盾, G是连是连通的。通的。 2 2) ) 先证先证( (构造构造) )要求的汉密尔顿路存在要求的汉密尔顿路存在: : 不要求掌握！不要求掌握！ 2 2) ) 先证先证( (构造构造) )要求的汉密尔顿路存在要求的汉密尔顿路存在: : 设设G中有中有p-1条边的路条边的路,pn,它的结点序列为它的结点序列为v1, v2, vp。如。如果有果有v1或或vp邻接于不在这条路上的一个结点邻接于不在这

20、条路上的一个结点,立刻扩展该路立刻扩展该路,使它使它包含这个结点包含这个结点,从而得到从而得到p条边的路。否则条边的路。否则v1和和vp都只邻接于这都只邻接于这条路上的结点条路上的结点,我们证明在这种情况下我们证明在这种情况下,存在一条回路包含结点存在一条回路包含结点v1, v2, vp。v1vpv1v2 vpv1vlvm vj vtp-1p-1vpvl-1vm-1 vj-1 vt-1vj-1v1v2vj-1vpvp-1vjv1 vpvl-1vm-1 vj-1 vt-1vpvpp-k-1p-k-1v1=k=kvp+ +v1p-k-1+kn-1p-k-1+kn-1v1vp n-2n-2v1v2

21、vpG是连通的是连通的Gvxvkvxvkvk+1 vj-1vpvp-1 vjv1v2 vk-1 n说明：该定理的条件是充分条件但不是必要条说明：该定理的条件是充分条件但不是必要条件。件。n例：见例：见308页图页图7-4.10。nn=6，每一对结点度数之和等于每一对结点度数之和等于4，小于，小于n-1，但在但在G中存在一条汉密尔顿路。中存在一条汉密尔顿路。3.定理定理7-47-4.4 设图设图G具有具有n个结点的简单图个结点的简单图,如果如果G中每一对结点度数之和大于等于中每一对结点度数之和大于等于n-1,则则G中存在中存在一条汉密尔顿路。一条汉密尔顿路。例例 某地有某地有5个风景点，若每个景

22、点均有两条道路与个风景点，若每个景点均有两条道路与其他景点相通，问是否可经过每个景点一次而游完其他景点相通，问是否可经过每个景点一次而游完这这5处。处。解解 将景点作为结点，道路作为边，则得到一个有将景点作为结点，道路作为边，则得到一个有5个结点的无向图。个结点的无向图。 由题意，对每个结点由题意，对每个结点vi(i=1,2,3,4,5)有有 deg(vi)=2。 则对任两点和均有则对任两点和均有 deg(vi) + deg(vj)=2 + 2 =4 = 5 1 所以此图有一条汉密尔顿回路。即经过每个景所以此图有一条汉密尔顿回路。即经过每个景点一次而游完这点一次而游完这5个景点。个景点。例：在

23、七天内安排七门课程的考试，使得同一位教师例：在七天内安排七门课程的考试，使得同一位教师所任的两门课程不排在接连的两天中，试证明如果没所任的两门课程不排在接连的两天中，试证明如果没有教师担任多于四门课程，则符合上述要求的考试安有教师担任多于四门课程，则符合上述要求的考试安排总是可能的。排总是可能的。证明：设证明：设G为具有七个结点的图，每个结点对应于一为具有七个结点的图，每个结点对应于一门课程考试，如果这两个结点对应的课程考试是由不门课程考试，如果这两个结点对应的课程考试是由不同教师担任的，那么这两个结点之间有一条边，因为同教师担任的，那么这两个结点之间有一条边，因为每个教师所任课程数不超过每个

24、教师所任课程数不超过4，故每个结点的度数至，故每个结点的度数至少是少是3，任两个结点的度数之和至少是，任两个结点的度数之和至少是6，故，故G总是包总是包含一条汉密尔顿路，它对应于一个七门考试课程的一含一条汉密尔顿路，它对应于一个七门考试课程的一个适当的安排。个适当的安排。 4. 4.定理定理7-47-4.5 设图设图G具有具有n个结点的简单图个结点的简单图,如果如果G中每一对结点度数之和大于等于中每一对结点度数之和大于等于n,则则G中存在一条汉密中存在一条汉密尔顿回路。尔顿回路。证明：略证明：略5、图的闭包、图的闭包 定义定义7-4.4：给定图：给定图G=有有n个结点，个结点，若将图若将图G中

25、度数之和至少是中度数之和至少是n (n) 的非邻接结点的非邻接结点连接起来得图连接起来得图G，对图，对图G重复上述步骤，直到不重复上述步骤，直到不再有这样的结点对存在为止，所得到的图，称为再有这样的结点对存在为止，所得到的图，称为是原图是原图G的闭包，记作的闭包，记作C(G)。 在这个例子中C(G)是完全图，一般情况下， C(G)也可能不是完全图。6、定理、定理7-4.6：当且仅当一个简单图的闭包是汉：当且仅当一个简单图的闭包是汉密尔顿图时，这个简单图是汉密尔顿图。密尔顿图时，这个简单图是汉密尔顿图。7、推论：、推论：n 3的有向的有向(无向无向)完全图完全图Kn为汉密尔顿为汉密尔顿图。图。判

26、别汉密尔顿路不存在的标号法判别汉密尔顿路不存在的标号法n关于图中没有汉密尔顿路的判别尚没有确定的方法。n介绍一个判别汉密尔顿路不存在的标号法。例 证明下图没有汉密尔顿路。任取一结点如v1,用A标记，所有与它邻接的结点标B。继续不断地用A标记所有与B邻接的结点，用B标记所有与A邻接的结点，直到图中的所有结点全部标记完毕。作业nP311： （2）（6）（9）7-5 平面图平面图一、平面图一、平面图1、如果无向图如果无向图G=的所有结点和的所有结点和边可以在一个平面上图示出来，而使各边仅在顶点边可以在一个平面上图示出来，而使各边仅在顶点处相交。无向图处相交。无向图G称为称为（planar graph

27、），），否则称否则称G为为。n有些图形从表面看有几条边是相交的，但是不能有些图形从表面看有几条边是相交的，但是不能就此肯定它不是平面图。就此肯定它不是平面图。n例如，下面左图表面看有几条边相交，但如把它例如，下面左图表面看有几条边相交，但如把它画成右图，则可看出它是一个平面图。画成右图，则可看出它是一个平面图。有些图形不论怎样改画，除去结点外，总有些图形不论怎样改画，除去结点外，总有边相交，故它是非平面图。有边相交，故它是非平面图。设图设图G=是一连通平面图，由图是一连通平面图，由图中各边所界定的区域称为平面图的中各边所界定的区域称为平面图的(regions)。有界的区域称为有界的区域称为，无

28、界的区域称为，无界的区域称为无界面无界面。界定各面的界定各面的闭的拟路径闭的拟路径称为面的称为面的(boundary).面面r的边界长度称为的边界长度称为面面r的度的度（degree）记为）记为deg (r) ，又称为面又称为面r的的次数次数 。2、面、边界、面、边界例如图例如图7-5.3deg(r1)=3deg(r2)=3deg(r3)=5deg(r4)=4deg(r5)=3 deg(r1)+deg(r2)+deg(r3)+deg(r4)+deg(r5)=18 如边是两个面的分界线，该边在两个面的度数中如边是两个面的分界线，该边在两个面的度数中各记各记1次。如边不是两个面的分界线次。如边不是

29、两个面的分界线(称为割边称为割边)则该边则该边在该面的度数中重复记了两次，故定理结论成立。在该面的度数中重复记了两次，故定理结论成立。 设设G为一有限平面图，面的次数之为一有限平面图，面的次数之和等于其边数的两倍。和等于其边数的两倍。 证明思路：任一条边或者是两个面的共同边界证明思路：任一条边或者是两个面的共同边界（贡献（贡献2次），或者是一个面的重复边（贡献次），或者是一个面的重复边（贡献2次）次） 4、欧拉定理、欧拉定理 设设G为一平面连通图，为一平面连通图，v为其顶点数，为其顶点数，e为其边数，为其边数，r 为其面数，那么欧拉公为其面数，那么欧拉公式成立式成立 v e + r = 2证明

30、证明 （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没

31、变，故没变，故（ vk +1）-（ ek +1）+ rk = vk-ek+rk=2。用一条边连接图上的已知两点，此时用一条边连接图上的已知两点，此时ek和和rk都增加都增加1，结点数，结点数vk没变，故没变，故 vk -（ek +1）+（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

32、，则，则e=2r=16。 设设G为一简单连通平面图，其顶点数为一简单连通平面图，其顶点数v3，其边数为，其边数为e，那么，那么 e3v 6 证明思路：设证明思路：设G的面数为的面数为r,当当v=3,e=2时上式成立时上式成立,若若e=3,则每一面的次数不小于则每一面的次数不小于3,各面次数之和不小于各面次数之和不小于2e,因此因此 2e3r, r2e/3 代入欧拉公式代入欧拉公式: 2=v-e+rv-e+ 2e/3 整理后得整理后得: e3v 6 说明：这是简单图是平面图的必要条件。说明：这是简单图是平面图的必要条件。本定理的用途本定理的用途:判定某图是非平面图。判定某图是非平面图。例如：例如

33、：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中任取三个结点，其中必

34、有两个结点不中任取三个结点，其中必有两个结点不邻接，故每个面的次数都不小于邻接，故每个面的次数都不小于4，由，由4r2e，re/2，即即v-e+e/2v-e+r=2，v-e/22，2v- e 4，2v-4e。6、定义、定义7-5.3：给两图：给两图G1和和G2，或者它们是同构的，或者它们是同构的，或者反复地插入或去掉二度结点后，或者反复地插入或去掉二度结点后， 使使G1和和G2同同构，则称构，则称G1和和G2是在是在2度结点内同构的，也称度结点内同构的，也称G1和和G2是同胚的。是同胚的。在给定图在给定图G的边上，插入一个新的度数为的边上，插入一个新的度数为2的结点，使一条的结点，使一条边分成

35、两条边，或者对于关于度数为边分成两条边，或者对于关于度数为2的结点的两条边，去的结点的两条边，去掉这个结点，使两条边化成一条边，这些都不会影响图的掉这个结点，使两条边化成一条边，这些都不会影响图的平面性。平面性。7、库拉托夫斯基定理、库拉托夫斯基定理(Kuratowski定理定理)定理定理7-5.4：一个图是平面图的充要条件是它不含：一个图是平面图的充要条件是它不含与与K5或或K3，3在二度结点内同构的子图。在二度结点内同构的子图。欧拉公式有时可以用来判定某个图是非平面图。欧拉公式有时可以用来判定某个图是非平面图。下面的下面的库拉托夫斯基定理给出了判定一个图是平库拉托夫斯基定理给出了判定一个图

36、是平面图的充要条件面图的充要条件.K3，3K5K5和和K3，3常称作库拉托夫斯基图。常称作库拉托夫斯基图。作业nP317： （1）（2）7-6 对偶图与着色对偶图与着色掌握对偶图的定义，会画图掌握对偶图的定义，会画图G的对偶图的对偶图 G*掌握自对偶图的定义及必要条件。掌握自对偶图的定义及必要条件。n与平面图有密切关系的一个图论的应用是图形的着与平面图有密切关系的一个图论的应用是图形的着色问题，这个问题最早起源于地图的着色，一个地色问题，这个问题最早起源于地图的着色，一个地图中相邻国家着以不同颜色，那么最少需用多少种图中相邻国家着以不同颜色，那么最少需用多少种颜色？颜色？n一百多年前，英国格色

37、里一百多年前，英国格色里(Guthrie)提出了用四种提出了用四种颜色即可对地图着色的猜想，颜色即可对地图着色的猜想，1879年肯普年肯普(Kempe)给出了这个猜想的第一个证明，但到给出了这个猜想的第一个证明，但到1890年希伍德年希伍德(Hewood)发现肯普证明是错误的，但他指出肯普发现肯普证明是错误的，但他指出肯普的方法的方法 虽不能证明地图着色用四种颜色就够了，但虽不能证明地图着色用四种颜色就够了，但可证明用五种颜色就够了，即五色定理成立。可证明用五种颜色就够了，即五色定理成立。n此后四色猜想一直成为数学家感兴趣而未能解此后四色猜想一直成为数学家感兴趣而未能解决的难题。决的难题。n直

38、到直到1976年美国数学家阿佩尔和黑肯宣布：他年美国数学家阿佩尔和黑肯宣布：他们用电子计算机证明了四色猜想是成立的。所以们用电子计算机证明了四色猜想是成立的。所以从从1976年以后就把四色猜想这个名词改成年以后就把四色猜想这个名词改成“四四色定理色定理”了。了。n为了叙述图形着色的有关定理，下面先介绍对为了叙述图形着色的有关定理，下面先介绍对偶图的概念。偶图的概念。一、对偶图一、对偶图1、对偶图、对偶图对具有面对具有面F1 ,F2,., Fn的连通平面图的连通平面图G=实施下列步骤所得到的图实施下列步骤所得到的图G*称为图称为图G的的对对偶图偶图（dual of graph）：）：如果存在一个

39、图如果存在一个图G*=满足下述条件：满足下述条件：（a）在）在G的每一个面的每一个面Fi的内部作一个的内部作一个G*的顶点的顶点vi* 。即即对图对图G的任一个面的任一个面Fi内部有且仅有一个结点内部有且仅有一个结点vi*V*。(b)若若G的面的面Fi，Fj有公共边有公共边ek，则作，则作ek*=(vi*，vj*)，且，且ek*与与ek相交。相交。 即若即若G中面中面Fi与与Fj有公共边界有公共边界ek ，那么过边界的，那么过边界的每一边每一边ek作关联作关联vi*与与vj*的一条边的一条边ek* =(vi*, vj*) 。 ek*与与G*的其它边不相交。的其它边不相交。(c)(c)当且仅当当

40、且仅当e ek k只是一个面只是一个面F Fi i的边界时的边界时( (割边割边) )，v vi i* *存存在一个环在一个环e e* *k k与与e ek k相交。相交。 即当即当e ek k为单一面为单一面F Fi i的边界而不是与其它面的公共的边界而不是与其它面的公共边界时，作边界时，作v vi i* *的一条环与的一条环与e ek k相交（且仅交于一处）。相交（且仅交于一处）。所作的环不与所作的环不与 G G* *的边相交。的边相交。则称图则称图G*为为G的对偶图。的对偶图。实线边图为平面图，虚线边图为其对偶图。v*=r，e*=e，r*=v2、自对偶图、自对偶图 如果图如果图G的对偶图

41、的对偶图G*同构于同构于G,则称则称G是是自对偶图。自对偶图。二、图的着色二、图的着色1、问题的提出、问题的提出n该问题起源于地图的着色问题。该问题起源于地图的着色问题。n图着色的三种情况图着色的三种情况:n对点着色对点着色 是对图是对图G的每个结点指定一种颜色，使得相邻的每个结点指定一种颜色，使得相邻结点的颜色不同结点的颜色不同;n对边着色对边着色 给每条边指定一种颜色使得相邻的边的颜色给每条边指定一种颜色使得相邻的边的颜色不同，不同，n给面着色给面着色 给每个面指定一种颜色使得有公共边的两个面给每个面指定一种颜色使得有公共边的两个面有不同的颜色。有不同的颜色。n对边着色和对面着色均可转化为

42、对结点着色问题。对边着色和对面着色均可转化为对结点着色问题。从对偶图的概念，可以看到，对于地图的着色问从对偶图的概念，可以看到，对于地图的着色问题，可以归纳为对于平面图的结点的着色问题，题，可以归纳为对于平面图的结点的着色问题，因此四色问题可以归结为要证明对于任何一个平因此四色问题可以归结为要证明对于任何一个平面图，一定可以用四种颜色，对它的结点进行着面图，一定可以用四种颜色，对它的结点进行着色，使得邻接的结点都有不同的颜色。色，使得邻接的结点都有不同的颜色。2、图的正常着色：图、图的正常着色：图G的正常着色的正常着色(或简称着色或简称着色)是指对它的每一个结点指定一种颜色，使得没是指对它的每

43、一个结点指定一种颜色，使得没有两个邻接的结点有同一种颜色。如果图在着有两个邻接的结点有同一种颜色。如果图在着色时用了色时用了n种颜色，我们称种颜色，我们称G为为n-色的图。色的图。3、色数：对于图、色数：对于图G着色时，需要的最少颜色数着色时，需要的最少颜色数称为称为G的色数，记作的色数，记作x(G)。 证明一个图的色数为n，首先必须证明用n种颜色可以着色该图，其次证明用少于n种颜色不能着色该图。4、对点着色的鲍威尔方法：、对点着色的鲍威尔方法：第一步：对每个结点按度数递减次序进行排列第一步：对每个结点按度数递减次序进行排列(相相同度数的结点次序可随意同度数的结点次序可随意)第二步：用第一种颜色对第一个结点着色，并按次第二步：用第一种颜色对第一个结点着色，并按次序对与前面着色点不相邻的每一点着同样的颜色。序对与前面着色点不相邻的每一