《(53)--6.1 欧拉图离散数学离散数学.ppt》由会员分享，可在线阅读，更多相关《(53)--6.1 欧拉图离散数学离散数学.ppt（8页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
欧拉图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