欧拉图和哈密尔顿图精.ppt

该【欧拉图和哈密尔顿图精 】是由【相惜】上传分享，文档一共【50】页，该文档可以免费在线阅读，需要了解更多关于【欧拉图和哈密尔顿图精 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。欧拉图和哈密尔顿图信号处理中的数学方法第2-:一般不限于简单图,一般指无向图原问题:“右边的图中是否存在包含每条边一次且恰好一次的回路?〞原问题等价于:<定义>欧拉回路,欧拉通路图G的一个回路/通路,它经过G中每条边恰好一次,那么回路/通路称为欧拉回路/通路。定义:如果图G中含欧拉回路,那么图G称为欧拉图。定义:如果图G中仅有欧拉通路,但没有欧拉回路,那么图G称为半欧拉图。整理ppt例“一笔划〞问题——G中有欧拉通路?整理ppt实例上图中,(1),(4)为欧拉图整理ppt例多米诺骨牌,28块能否排成一圈使两两相邻的半边的点数相同,问是否可能?整理ppt将0-6看作7个结点,任2点的边看作一块骨牌这样,该问题转化为G有无欧拉回路的问题整理ppt[定理]对连通图,以下命题等价1〕G是欧拉图2〕G的每个结点为偶度数3〕G的边集能划分成为根本回路,[证]1)?2)?3)?1)1)?2):设Go为G的欧拉回路,可将Go表示为v1e1v2e2……envn+1(vn+1=v1),其中vi的一次出现总关联于左右2条边,对应度数为2又Go的e1,e2,……en互不相同,且穷尽了所有的边,这样任一点vi的度数为vi在Go中出现的度数之和——必为2的倍数。//整理ppt2)?3):G连通,不妨设G是非平凡图由2〕每个结点度数至少为2,所以G中含一基回Z1,Z1的度数为偶度数,删去Z1的边得到G’,原G为偶度数,删去G’的每个点仍为偶度数除孤立点外其余点至少为2度,即余连通点所图至少2连通如法炮制,直至余图不含边{Z1},{Z2},…..,{Zk}为E的一个划分。//整理ppt