离散数学--第8章+图论-7ppt课件

1、1返回 结束第八章 图论-22返回 结束v一、欧拉Euler回路转化 Euler1736年 3返回 结束v判别定理：无向图G是欧拉图当且仅当G是连通图，且G中没有奇度顶点。 (充要条件)v证明反证法）：v 设C=(e1=(v0,v1),e2=(v1,v2),em=(vm-1 ,v0)是图中最大的回路。v 假设C不是Euler回路。则图G如下图所示：CC或4返回 结束 图是连通的，则顶点不可能出现下面的情况：C图中任意结点的度均为偶数，有如下所示：C与假设矛盾， C是Euler回路。C5返回 结束v推论：如果连通图G只有两个度为奇数的顶点，则存在以这两个顶点为两端点，且包含G所有边的Euler道

2、路。v补充：连通有向图存在Euler回路的充要条件是：每个顶点的入度出度。6返回 结束v欧拉回路求解方法v（Fleurys algorithm ）：v(1)可从任一点出发去掉连接此点的一边。 v(2)依序去掉相连的边但必须注意下列两条件： v a、如果某边去掉后会导致某点无连通的 边，则此顶点亦可去。 v b、去某边后不能造成图形的不连通。7返回 结束例1-1：如果可能求出下图的一条Euler回路。v1v2v5v3v4v6v7v8v98返回 结束解：首先看图中是否有Euler回路，即看每个顶点的度是否都是偶数。 d(V1)=2， d(V2)=4， d(V3)=2， d(V4)=4， d(V5)

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

4、接着去掉(v4,v3)v依序去掉相连的边但必须注意下列两条件： v a、如果某边去掉后会导致某点无连通的 边，则此顶点亦可去。 v b、去某边后不能造成图形的不连通。v1v2v5v3v4v6v7v8v91212返回 结束v(3)接着去掉(v3,v2)v依序去掉相连的边但必须注意下列两条件： v a、如果某边去掉后会导致某点无连通的v 边，则此顶点亦可去。 v b、去某边后不能造成图形的不连通。v1v2v5v3v4v6v7v8v912313返回 结束vv依序去掉相连的边但必须注意下列两条件： v a、如果某边去掉后会导致某点无连通的 v 边，则此顶点亦可去。 v b、去某边后不能造成图形的不连通。v1v2v5v3v4v6v7v8v912314返回 结束v依序去掉相连的边但必须注意下列两条件： v a、如果某边去掉后会导致某点无连通的 边，则此顶点亦可去。 v b、去某边后不能造成图形的不连通。v1v2v5v3v4v6v7v8v912345678这时，如果去掉(v6,v5)将导致图不连通15返回 结束v1v2v5v3v4v6v7v8v91234567891011121