离散数学--第8章+图论-7(+Euler图与Hamilton图)

《离散数学--第8章+图论-7(+Euler图与Hamilton图)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第八章图论-28.1Euler图与Hamilton图8.2树8.3生成树8.4平面图8.1Euler图与Hamilton图一、欧拉（Euler）回路转化Euler1736年定义：对于连通的无向图G，若存在一简单回路，它通过G的所有边，则这回路称为G的Euler回路；若图G中存在Euler回路，则称G为Euler图；在图G中，若存在包含所有边的简单路径，则称这条路径为Euler道路(Eulertour)。8.1Euler图与Hamilton图判别定理：无向图G是欧拉图当且仅当G是连通图，且G中没有奇度顶点。(充要条件)证明（反证法）：设C=(e1=(v

2、0,v1),e2=(v1,v2),…,em=(vm-1,v0))是图中最大的回路。假设C不是Euler回路。则图G如下图所示：CC或8.1Euler图与Hamilton图∵图是连通的，则顶点不可能出现下面的情况：C∵图中任意结点的度均为偶数，∴有如下所示：C与假设矛盾，∴C是Euler回路。C8.1Euler图与Hamilton图推论：如果连通图G只有两个度为奇数的顶点，则存在以这两个顶点为两端点，且包含G所有边的Euler道路。补充：连通有向图存在Euler回路的充要条件是：每个顶点的入度＝出度。8.1Euler图与Hamilton图欧拉回路求解方

3、法（Fleury‘salgorithm）：(1)可从任一点出发去掉连接此点的一边。(2)依序去掉相连的边但必须注意下列两条件：a、如果某边去掉后会导致某点无连通的边，则此顶点亦可去。b、去某边后不能造成图形的不连通。8.1Euler图与Hamilton图例1-1：如果可能求出下图的一条Euler回路。v1v2v5v3v4v6v7v8v98.1Euler图与Hamilton图解：首先看图中是否有Euler回路，即看每个顶点的度是否都是偶数。d(V1)=2，d(V2)=4，d(V3)=2，d(V4)=4，d(V5)=4，d(V6)=4，d(V7)=2，

4、d(V8)=2，d(V9)=4。所以存在Euler回路。可以任意一个顶点为起点，这里以v2为起点:v1v2v5v3v4v6v7v8v98.1Euler图与Hamilton图依序去掉相连的边但必须注意下列两条件：a、如果某边去掉后会导致某点无连通的边，则此顶点亦可去也。b、去某边后不能造成图形的不连通。v1v2v5v3v4v6v7v8v98.1Euler图与Hamilton图(1)先去掉(v2,v4)依序去掉相连的边但必须注意下列两条件：a、如果某边去掉后会导致某点无连通的边，则此顶点亦可去。b、去某边后不能造成图形的不连通。v1v2v5v3v4v6

5、v7v8v918.1Euler图与Hamilton图(2)接着去掉(v4,v3)依序去掉相连的边但必须注意下列两条件：a、如果某边去掉后会导致某点无连通的边，则此顶点亦可去。b、去某边后不能造成图形的不连通。v1v2v5v3v4v6v7v8v9128.1Euler图与Hamilton图(3)接着去掉(v3,v2)依序去掉相连的边但必须注意下列两条件：a、如果某边去掉后会导致某点无连通的边，则此顶点亦可去。b、去某边后不能造成图形的不连通。v1v2v5v3v4v6v7v8v91238.1Euler图与Hamilton图……依序去掉相连的边但必须注意下

6、列两条件：a、如果某边去掉后会导致某点无连通的边，则此顶点亦可去。b、去某边后不能造成图形的不连通。v1v2v5v3v4v6v7v8v91238.1Euler图与Hamilton图依序去掉相连的边但必须注意下列两条件：a、如果某边去掉后会导致某点无连通的边，则此顶点亦可去。b、去某边后不能造成图形的不连通。v1v2v5v3v4v6v7v8v912345678这时，如果去掉(v6,v5)将导致图不连通8.1Euler图与Hamilton图v1v2v5v3v4v6v7v8v91234567891011121314V2-v4-v3-v2-v1-v4-v5

7、-v9-v6-v8-v9-v7-v6-v5-v2Euler回路：从上例可知，Euler回路不唯一。