7-4 欧拉图和汉.ppt

7-4 欧拉图和哈密尔顿图要求: 1、理解欧拉图、哈密尔顿图的定义。 2、掌握欧拉图的判定方法。 3、会判断一些图不是哈密尔顿图。 4、熟悉一些欧拉图和哈密尔顿图。一、欧拉图 1 、哥尼斯堡七桥问题 A B CD 七桥问题等价于在图中求一条回路,此回路经过每条边一次且仅有一次。欧拉在 1736 年的论文中提出了一条简单的准则,确定了哥尼斯堡七桥问题是不能解的。 2 、欧拉图(Euler) 7-4 .1无向图 G 具有一条欧拉路,当且仅当 G 连通,并且有零个或两个奇数度结点。 7-4 .1如果无孤立结点图 G上有一条经过G的所有边一次且仅一次的路径,则称该路径为图G的欧拉路径欧拉路径( Euler walk )。如果图 G上有一条经过 G边一次且仅一次的的回路,则称该回路为图 G 的欧拉回路欧拉回路,具有欧拉回路的图称为,具有欧拉回路的图称为欧拉图欧拉图( Euler graph )。?证明思路: 1) 先证必要性: G有欧拉路?G连通连通且( 且( 有有0 0个个或或2 2个奇数度结点个奇数度结点) ) 设设G的欧拉路是点边序列 v 0e 1v 1e 2…e kv k,其中结点可能重复,但边不重复。因欧拉路经过(所有边?) 所有结点,所以图 G是连通的。对于任一非端点结点对于任一非端点结点 v i, ,在欧拉路中每当在欧拉路中每当 v i出现依出现依次,必关联两条边,故次,必关联两条边,故 v i虽可重复出现,但是虽可重复出现,但是 deg deg ( (v i) )必必是偶数。对于端点是偶数。对于端点, ,若若v 0=v k,则,则 deg deg ( (v 0) )必是偶数,即必是偶数,即 G 中无奇数度结点中无奇数度结点。若。若 v 0≠v k,则,则 deg deg ( (v 0) )必是奇数, 必是奇数, deg deg ( (v k) )必是奇数必是奇数, ,即即G中有两个奇数度结点中有两个奇数度结点。。必要性证完。 2)再证充分性:(证明过程给出了一种构造方法) G 连通连通且( 且( 有有0 0个个或或2 2个奇数度结点个奇数度结点) )?G有欧拉路(1) (1) 若有若有 2 2个奇数度结点个奇数度结点, ,则从其中一个结点开始构造一条迹则从其中一个结点开始构造一条迹, , 即从即从 v 0出发经关联边出发经关联边 e 1进入进入 v 1, ,若若 deg deg ( (v 1) )为偶数为偶数, ,则必可由则必可由 v 1再经再经关联边关联边 e 2进入进入 v 2, ,如此下去如此下去, ,每边仅取一次每边仅取一次, ,由于由于 G是连通的是连通的, ,故必可故必可到达另一奇数度结点停下到达另一奇数度结点停下, ,得到一条迹得到一条迹 L L 1 1: :v 0e 1v 1e 2…e kv k。若。若 G中中没有奇数度结点没有奇数度结点, ,则从任一结点则从任一结点 v 0出发出发, ,用上述方法必可回到结点用上述方法必可回到结点 v 0, ,得到一条闭迹。得到一条闭迹。(2) (2) 若若L L 1 1通过了通过了 G的所有边的所有边, , L L 1 1就是一条欧拉路。就是一条欧拉路。(3) (3) 若若G中去掉中去掉 L L 1 1后得到子图后得到子图 G’, ,则则G’中每个结点度数都为中每个结点度数都为偶数偶数, ,因为原来的图因为原来的图 G是连通的是连通的, ,故故L L 1 1与与G’至少有一个结点至少有一个结点 v i重合重合, , 在在G’中由中由 v i出发重复出发重复(1) (1) 的方法的方法, ,得到闭迹得到闭迹 L L 2 2。。(4) (4) 当当L L 1 1与与L L 2 2组合组合, ,若恰是若恰是 G, ,得欧拉路得欧拉路, ,否则重复否则重复(3) (3) , ,可得闭迹可得闭迹 L L 3 3, ,依此类推可得一条欧拉路。依此类推可得一条欧拉路。充分性证完?由于有了欧拉路和欧拉回路的判别准则,因此哥尼斯堡七桥问题立即有了确切的否定答案,因为从图中可以看到 deg(A) =5 , deg(B) = deg(C) = deg(D)=3 ,故欧拉回路必不存在。 7-4 .1的推论无向图 G具有一条欧拉回路, 当且仅当 G连通且所有结点度数皆为偶数。 4 、一笔画问题要判定一个图 G 是否可一笔画出,有两种情况: 一是从图 G 中某一结点出发,经过图 G 的每一边一次仅一次到达另一结点。另一种就是从 G 的某个结点出发,经过 G 的每一边一次仅一次再回到该结点。上述两种情况分别可以由欧拉路和欧拉回路的判定条件予以解决。 5. 定义 7- :给定有向图 G ,通过图中每边一次且仅一次的一条单向路(回路),称