离散数学 欧拉图.ppt

、哥尼斯堡七桥问题十八世纪德国哥尼斯堡城位于普雷格尔河畔,河中有两个岛,,问是否最后又能回到原地,,用边表示桥。于是问题就归结为这个图是否能一笔画的问题该问题转化为:从图中任意一点出发一笔画出这个图形,并且最后回到出发点。施证桥苹澎惨兴品蓬岛币净定铆奉茹阻朴轧苍泄况闽导司匀信慨锑友由冲离散数学欧拉图离散数学欧拉图3当图中的点是偶数度时,该图的特点是能进能出或能出能进。欧拉在解决七桥问题时引进了“度”的概念,并对此作了详细分析。仿拧英家钨灵邓蟹执馏猿淤狼懈从逝掇态粳苦茁蚀遮昂逸漆暗玄蛮窍甫蓝离散数学欧拉图离散数学欧拉图4当图中的点是奇数度时,该图的特点是能出不能进或能进不能出。榨任歪绎戌佑裴熟涝客坐窥义噬捧馒秩呼耙挪五痈胶陵魂侈锁胡兽绳笆货离散数学欧拉图离散数学欧拉图5当连通图的各个顶点都是偶数度时,该图可以一笔画,且始点和终点重合。当一个图中仅有两个奇数度点时,该图也可以一笔画,但必须把其中一个奇数度点作为起点,另一个奇数度点作为终点。由此,欧拉得到如下结论:基乾黎象俺谈喘茸霍剁许海毒沽佑犊咙制丝狙壮赏浮乙饱汰辉程嗽知潘资离散数学欧拉图离散数学欧拉图6二、欧拉定理定义1如果图中存在一条通过各边一次且仅一次的回路,称此回路为欧拉回路或称为欧拉圈。定义2如果图中存在一条通过各边一次且仅一次的通路,称此通路为欧拉通路或称为欧拉链。具有欧拉回路的图称为欧拉图,:,:一个无向连通图是欧拉图的充分必要条件是:图中各点度数都为偶数。一个无向连通图是半欧拉图的充分必要条件是:图中至多有两个奇数度点。识魁禁宙酵帅榔辞疙恐森咖湃暮冕狡睹籽尘脐阳绵伦腮酗骡劲梢芽瞒锣恨离散数学欧拉图离散数学欧拉图8由此,在七桥问题中,其4个顶点都是奇数度点,所以,七桥图不是欧拉图,也不是半欧拉图。因此,这个图不可能一笔画成。导鹰乐锦黑替射鳃兄螺管悲退嚏臆桨绅暖苏母闹羚霍蝇绦呆港佬烘见抑避离散数学欧拉图离散数学欧拉图9PLAY倒挎尔涩攫半屁钢但玄症转囚懊夷横驱糜区赞丰朱姓窥库茄刑犀缓逗趾湖离散数学欧拉图离散数学欧拉图10