欧拉图和汉.ppt

7-4欧拉图和哈密尔顿图 一、欧拉图 1、哥尼斯堡七桥问题 2、欧拉图(Euler) 4、一笔画问题 要判定一个图G是否可一笔画出，有两种情况：一是从图G中某一结点出发，经过图G的每一边一次仅一次到达另一结点。另一种就是从G的某个结点出发，经过G的每一边一次仅一次再回到该结点。上述两种情况分别可以由欧拉路和欧拉回路的判定条件予以解决。 5.定义7-4.2：给定有向图G，通过图中每边一次且仅一次的一条单向路（回路），称作单向欧拉路（回路）。 1、定义7-4.3：给定图G，若存在一条路经过图中的每个结点恰好一次，这条路称作哈密尔顿路。若存在一条回路，经过图中的每个结点恰好一次，这条回路称作哈密尔顿回路。 具有哈密尔顿回路的图称作哈密尔顿图。 2、定理7-4.3 若图G＝V，E具有哈密尔顿回路，则对于结点集V的每个非空子集S均有W(G-S)≤|S|，其中W(G-S)是G-S的连通分支数。 此定理是必要条件，可以用来证明一个图不是哈密尔顿图。 下面的定理给出一个无向图具有哈密尔顿路的充分条件。 3.定理7-4.4 设图G具有n个结点的简单图,如果G中每一对结点度数之和大于等于n-1,则G中存在一条哈密尔顿路。 2) 先证(构造)要求的汉密尔顿路存在: 设G中有p-1条边的路,pn,它的结点序列为v1, v2,…, vp。如果有v1或vp邻接于不在这条路上的一个结点,立刻扩展该路,使它包含这个结点,从而得到p条边的路。否则v1和vp都只邻接于这条路上的结点,我们证明在这种情况下,存在一条回路包含结点v1, v2,…, vp。 至此，已经构造出一条包含结点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条边的路。 ? 例：在七天内安排七门课程的考试，使得同一位教师所任的两门课程不排在接连的两天中，试证明如果没有教师担任多于四门课程，则符合上述要求的考试安排总是可能的。 5、图的闭包 定义7-4.4：给定图G=V，E有n个结点，若将图G中度数之和至少是n的非邻接结点连接起来得图G’，对图G’重复上述步骤，直到不再有这样的结点对存在为止，所得到的图，称为是原图G的闭包，记作C(G)。 6、定理7-4.6：当且仅当一个简单图的闭包是汉密尔顿图时，这个简单图是汉密尔顿图。 7、推论：n?3的有向(无向)完全图Kn为汉密尔顿图。 判别汉密尔顿路不存在的标号法 关于图中没有汉密尔顿路的判别尚没有确定的方法，下面通过一个例子，介绍一个判别汉密尔顿路不存在的标号法。 * * 要求： 1、理解欧拉图、哈密尔顿图的定义。 2、掌握欧拉图的判定方法。 3、会判断一些图不是哈密尔顿图。 4、熟悉一些欧拉图和哈密尔顿图。 A B C D 七桥问题等价于在图中求一条回路，此回路经过每条边一次且仅有一次。欧拉在1736年的论文中提出了一条简单的准则，确定了哥尼斯堡七桥问题是不能解的。 2.定理7-4.1 无向图G具有一条欧拉路，当且仅当G连通，并且有零个或两个奇数度结点。 1.定义7-4.1 如果无孤立结点图G上有一条经过G的所有边一次且仅一次的路径，则称该路径为图G的欧拉路径（Euler walk）。如果图G上有一条经过G边一次且仅一次的的回路，则称该回路为图G的欧拉回路，具有欧拉回路的图称为欧拉图（Euler graph）。 ? 证明思路：1) 先证必要性: G有欧拉路 ? G连通 且（有0个 或 2个奇数度结点） 设G的欧拉路是点边序列v0e1v1e2… ekvk，其中结点可能重复，但边不重复。因欧拉路经过（所有边?）所有结点，所以图G是连通的。 对于任一非端点结点vi，在欧拉路中每当vi出现依次，必关联两条边，故vi虽可重复出现，但是deg(vi)必是偶数。对于端点,若v0=vk ，则deg(v0)必是偶数，即G中无奇数度结点 。若v0≠vk ，则deg(v0)必是奇数， deg(vk)必是奇数,即G中有两个奇数度结点 。必要性证完。 2)再证充分性:(证明过程给出了一种构造方法) G连通且（有0个 或 2个奇数度结点）? G有欧拉路 (1)若有 2个奇数度结点,则从其中一个结点开始构造一条迹,即从