第8章 节 +图论-7（+Euler图与Hamilton图） 离散数学-图论课件.ppt

* 返回 结束 第八章 图论-2 8.1 Euler图与Hamilton图 8.2 树 8.3 生成树 8.4 平面图 8.1 Euler图与Hamilton图 一、欧拉（Euler）回路 转化 Euler 1736年 定义：对于连通的无向图G，若存在一简单回路，它通过G的所有边，则这回路称为G的Euler回路； 若图G中存在Euler回路，则称G为Euler图； 在图G中，若存在包含所有边的简单路径，则称这条路径为Euler道路(Euler tour)。 8.1 Euler图与Hamilton图 判别定理：无向图G是欧拉图当且仅当G是连通图，且G中没有奇度顶点。 (充要条件) 证明（反证法）： 设C=(e1=(v0,v1),e2=(v1,v2),…,em=(vm-1 ,v0))是图中最大的回路。 假设C不是Euler回路。则图G如下图所示： C C 或 8.1 Euler图与Hamilton图 ∵ 图是连通的，则顶点不可能出现下面的情况： C ∵图中任意结点的度均为偶数，∴有如下所示： C 与假设矛盾， ∴C是Euler回路。 C 8.1 Euler图与Hamilton图 推论：如果连通图G只有两个度为奇数的顶点，则存在以这两个顶点为两端点，且包含G所有边的Euler道路。 补充：连通有向图存在Euler回路的充要条件是：每个顶点的入度＝出度。 8.1 Euler图与Hamilton图 解：首先看图中是否有Euler回路，即看每个顶点的度是否都是偶数。 d(V1)=2， d(V2)=4， d(V3)=2， d(V4)=4， d(V5)=4， d(V6)=4， d(V7)=2， d(V8)=2， d(V9)=4。 所以存在Euler回路。 可以任意一个顶点为起点，这里以v2为起点: v1 v2 v5 v3 v4 v6 v7 v8 v9 8.1 Euler图与Hamilton图 依序去掉相连的边但必须注意下列两条件： a、如果某边去掉后会导致某点无连通的边，则此顶点亦可去也。 b、去某边后不能造成图形的不连通。 v1 v2 v5 v3 v4 v6 v7 v8 v9 8.1 Euler图与Hamilton图 (1)先去掉(v2,v4) 依序去掉相连的边但必须注意下列两条件： a、如果某边去掉后会导致某点无连通的 边，则此顶点亦可去。 b、去某边后不能造成图形的不连通。 v1 v2 v5 v3 v4 v6 v7 v8 v9 1 8.1 Euler图与Hamilton图 (2)接着去掉(v4,v3) 依序去掉相连的边但必须注意下列两条件： a、如果某边去掉后会导致某点无连通的 边，则此顶点亦可去。 b、去某边后不能造成图形的不连通。 v1 v2 v5 v3 v4 v6 v7 v8 v9 1 2 * * * 返回 结束