第二节--欧拉图.ppt

退 出目 录前一页后一页第二节第二节 欧拉图欧拉图本节的内容本节的内容 ＊＊ 欧拉图的定义欧拉图的定义 ＊＊ 欧拉图的判别法欧拉图的判别法 ＊＊ Fleury算法算法退 出目 录前一页后一页 历史背景：哥尼斯堡七桥问题与欧拉图历史背景：哥尼斯堡七桥问题与欧拉图 （（1 1）） （（2 2）） 图图1 1 其实，欧拉图是一笔画出的边不重复的回路其实，欧拉图是一笔画出的边不重复的回路. . 退 出目 录前一页后一页一、欧拉图的定义一、欧拉图的定义 1 1、欧拉图的定义、欧拉图的定义 定义定义1 1 （（1 1）欧拉通路）欧拉通路————经过图中每条边一次且经过图中每条边一次且 仅一次行遍所有顶点的通路仅一次行遍所有顶点的通路. . （（2 2）欧拉回路）欧拉回路————经过图中每条边一次且经过图中每条边一次且 仅一次行遍所有顶点的回路仅一次行遍所有顶点的回路. .（（3 3）欧拉图）欧拉图————具有欧拉回路的图具有欧拉回路的图. .（（4 4）半欧拉图）半欧拉图————具有欧拉通路而无欧拉具有欧拉通路而无欧拉 回路的图回路的图. .退 出目 录前一页后一页几点说明：几点说明： ＊＊ 规定平凡图为欧拉图规定平凡图为欧拉图. . ＊＊ 欧拉通路是生成的简单通路，欧拉回路欧拉通路是生成的简单通路，欧拉回路 是生成的简单回路是生成的简单回路. . ＊＊ 环不影响图的欧拉性环不影响图的欧拉性. .退 出目 录前一页后一页易知，图易知，图2 2中，（中，（1 1）、（）、（4 4）为欧拉图，（）为欧拉图，（2 2）、）、（（5 5）为半欧拉图，（）为半欧拉图，（3 3）、（）、（6 6）既不是欧拉图，）既不是欧拉图，也不是半欧拉图也不是半欧拉图. . 在（在（3 3），（），（6 6）中各至少加几）中各至少加几条边才能成为欧拉图？条边才能成为欧拉图？ （1） （2） （3）（4） （5） （6）退 出目 录前一页后一页二、欧拉图的判别法二、欧拉图的判别法1 1、无向、无向欧拉图的判别法欧拉图的判别法定理定理1 1 无向图无向图G是欧拉图当且仅当是欧拉图当且仅当G连通且连通且无奇度数顶点无奇度数顶点. .证证 若若G为平凡图无问题为平凡图无问题. . 下设下设G为为n阶阶m条条边的无向图边的无向图. . 必要性必要性 设设C为为G中一条欧拉回路中一条欧拉回路. .（（1））G连通显然连通显然. .（（2）） vi V(G)，，vi在在C上每出现一次获上每出现一次获2 2度，度，所以所以vi为偶度顶点为偶度顶点. . 由由vi的任意性，结论为真的任意性，结论为真. . 退 出目 录前一页后一页充分性充分性 对边数对边数m做归纳法（第二数学归纳法）做归纳法（第二数学归纳法）. .（（1））m=1时，时，G为一个环，则为一个环，则G为欧拉图为欧拉图. .（（2））设设m k（（k 1））时结论为真，时结论为真，m=k+1时时如下证明：如下证明：（（a））制造满足归纳假设的若干个小欧拉图制造满足归纳假设的若干个小欧拉图. . 由连通及无奇度数顶点可知，由连通及无奇度数顶点可知， (G) 2，，用扩用扩大路径法可得大路径法可得G中长度中长度 3的圈的圈C1. 删除删除C1上所上所有的边（不破坏有的边（不破坏G中顶点度数的奇偶性）得中顶点度数的奇偶性）得G ，，则则G 无奇度顶点，设它有无奇度顶点，设它有s（（s 1））个个连通分支连通分支G1 , G2 , …, Gs ,它们的边数均它们的边数均 k，，退 出目 录前一页后一页因而它们都是小欧拉图因而它们都是小欧拉图. . 设设C1 , C2 , …, Cs 是是G1 , G2 , …, Gs 的欧拉回路的欧拉回路. . （（b））将将C1上被删除的边还原，从上被删除的边还原，从C1上某一上某一顶点出发走出顶点出发走出G的一条欧拉回路的一条欧拉回路C.定理定理2 2 无向图无向图G是半欧拉图当且仅当是半欧拉图当且仅当G连连通且恰有两个奇度顶点通且恰有两个奇度顶点. .证证 必要性简单必要性简单. . 充分性（利用定理充分性（利用定理1 1））退 出目 录前一页后一页设设u,v为为G中的两个奇度顶点，令中的两个奇度顶点，令G =G (u,v)则则G 连通且无奇度顶点，由定理连通且无奇度顶点，由定理15.1知知G 为为欧拉图，因而存在欧拉回路欧拉图，因而存在欧拉回路C，，令令 =C (u,v)则则 为为G中欧拉通路中欧拉通路.2 2、有向欧拉图的判别法、有向欧拉图的判别法定理定理3 3 有向图有向图D是欧拉图当且仅当是欧拉图当且仅当D是强连是强连通的且每个顶点的入度都等于出度通的且每个顶点的入度都等于出度. .本定理的证明类似于定理本定理的证明类似于定理1 1. . 退 出目 录前一页后一页定理定理4 4 有向图有向图D是半欧拉图当且仅当是半欧拉图当且仅当D是单是单向连通的，且向连通的，且D中恰有两个奇度顶点，其中中恰有两个奇度顶点，其中一个的入度比出度大一个的入度比出度大1 1，另一个的出度比入，另一个的出度比入度大度大1 1，而其余顶点的入度都等于出度，而其余顶点的入度都等于出度. . 本定理的证明类似于定理本定理的证明类似于定理1 1. . 定理定理5 5 G是非平凡的欧拉图当且仅当是非平凡的欧拉图当且仅当G是连是连通的且为若干个边不重的圈之并通的且为若干个边不重的圈之并. . 可用归纳法证定理可用归纳法证定理5 5. . 退 出目 录前一页后一页例例1 1 设设G是欧拉图，但是欧拉图，但G不是平凡图，也不是不是平凡图，也不是一个环，则一个环，则 (G) 2.证证 只需证明只需证明G中不可能有桥（如何证明？）中不可能有桥（如何证明？） （（1）） （（2））图中，（图中，（1），（），（2））两图都是欧拉图，均两图都是欧拉图，均从从A点出发，如何一次成功地走出一条欧拉点出发，如何一次成功地走出一条欧拉回路来？回路来？退 出目 录前一页后一页三三、、Fleury算法算法 Fleury算法：算法：(1) 任取任取v0 V(G)，令，令P0=v0. (2) 设设Pi = v0e1v1e2…eivi已经行遍，按下面方法已经行遍，按下面方法来从来从E(G) {e1,e2,…,ei}中选取中选取ei+1：：(a) ei+1与与vi相关联；相关联；(b) 除非无别的边可供行遍，否则除非无别的边可供行遍，否则ei+1不应该为不应该为Gi = G {e1,e2,…,ei}中的桥中的桥. 退 出目 录前一页后一页(3) 当当 (2)不能再进行时，算法停止不能再进行时，算法停止.可以证明，当算法停止时所得简单通路可以证明，当算法停止时所得简单通路Pm = v0e1v1e2…emvm（（vm=v0））为为G中一条欧中一条欧拉回路拉回路. 用用Fleury算法走出例算法走出例1中中(1)，，(2)从从A出发出发（其实从任何一点出发都可以）的欧拉回（其实从任何一点出发都可以）的欧拉回路各一条路各一条. 退 出目 录前一页后一页小结小结一、一、 欧拉图的定义欧拉图的定义二、二、 欧拉图的判别法欧拉图的判别法三、三、 Fleury Fleury算法算法。