(53)--6.1 欧拉图离散数学离散数学.ppt
( 4.5 )《(53)--6.1 欧拉图离散数学离散数学.ppt》由会员分享，可在线阅读，更多相关《(53)--6.1 欧拉图离散数学离散数学.ppt（8页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。
欧拉图1736年，数学家欧拉（Leonhard Euler,1707-1783）解决了著名的哥尼斯堡七桥问题。1、哥尼斯堡七桥问题n经过图中每条边一次且仅一次的通路/回路称作该图的一条欧拉通路/回路。n存在欧拉回路的图称为欧拉图。存在欧拉通路存在欧拉回路是欧拉图aba2、欧拉通路与欧拉回路(1)无向图G有欧拉通路，当且仅当G连通且有零个或两个奇度点。(2)无向图G是欧拉图，当且仅当G连通且所有结点的度数全为偶数。欧拉图存在欧拉通路哥尼斯堡七桥问题不存在满足要求的路线。3、无向欧拉图判定定理(1)有向图D有欧拉通路，当且仅当它连通且各结点的入度均等于出度，或者除两个结点外，各结点的入度均等于出度，这两个特殊的结点，一个结点的入度比出度大1，而另一个结点的出度比入度大1。(2)有向图D具有欧拉回路（D是欧拉图），当且仅当D连通且每个结点的入度等于出度。4、有向欧拉图判定定理例例：判断下列有向图是否为欧拉图。：判断下列有向图是否为欧拉图。dbaecdbaec具有欧拉通路，但具有欧拉通路，但不是欧拉图不是欧拉图具有欧拉回路具有欧拉回路是欧拉图是欧拉图一笔画本质上就是求图中是否存在欧拉通路(或欧拉回路)5、一笔画问题THANK YOU
- 配套讲稿：
如PPT文件的首页显示word图标，表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制：
部分文档作品中含有的国旗、国徽等图片，仅作为作品整体效果示例展示，禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词：
- 53-6.1 欧拉图离散数学离散数学 53 6.1 欧拉图 离散数学
淘文阁 - 分享文档赚钱的网站所有资源均是用户自行上传分享，仅供网友学习交流，未经上传用户书面授权，请勿作他用。
限制150内