第11章-参考资料：欧拉图及判别法.pptVIP

无向欧拉图的判别法 定理15.1 无向图G是欧拉图当且仅当G连通且无奇度数顶点. 证明：若G 为平凡图，结论成立。 下面设G为 n 阶 m 条边的无向图. 先证必要性。 设C 为G 中一条欧拉回路. (1) G显然是连通的. (2) ?vi?V(G)，vi在C上每出现一次获2度，所以vi为偶度顶点. 由vi 的任意性，结论为真. 充分性. 对边数m做归纳法（第二数学归纳法）. (1) m = 1时，G为一个环，则G为欧拉图. (2) 设m ? k (k ? 1)时结论为真，m = k+1时如下证明： 无向欧拉图的判别法(续) 定理15.1 无向图G是欧拉图当且仅当G连通且无奇度数顶点. 证明：充分性. 对边数m做归纳法. (2) 设m ? k (k ? 1)时结论为真，m = k+1时如下证明： ∵ G连通且无奇度数顶点 ∴ ? (G) ? 2，且G中必含有圈 设C为G中一个圈，删除C上所有边，则得到G的生成子图G’ 设G’具有s个连通分支G’1 G’2 …… G’s，每个连通分支至多有k条边，且无奇度数顶点 设与C的公共顶点为vji，由归纳假设可知G’1 G’2 …… G’s都是欧拉图，因而各自存在一条欧拉回路。 从某个顶点vr开始，沿C行走，每遇到一个vji，则经过该连通分支的欧拉回路，最后回到vr，得到一条欧拉回路。 ∴无向图G是欧拉图 无向欧拉图的判别法证明图示 半欧拉图的判别法 定理15.2 无向图G是半欧拉图当且仅当G 连通且恰有两个奇度顶点. 证明：必要性. G是半欧拉图，则存在一条欧拉通路? ，但不存在欧拉回路。? 中的两个端点必为奇度顶点。 对于? 中的其它顶点每次出现时必获得2度，所以必为偶度顶点。即G中恰有两个奇度顶点。 充分性(利用定理15.1). 设u, v为G 中的两个奇度顶点，令 G ? = G ∪(u, v) 则G ? 连通且无奇度顶点，由定理15.1知G ?为欧拉图，因而存在欧拉回路C，令 ? = C ? (u, v) 则? 为 G 中欧拉通路. 有向欧拉图的判别法 定理15.3 有向图D是欧拉图当且仅当D是强连通的且每个顶点的入度都等于出度. 本定理的证明类似于定理15.1. 定理15.4 有向图D是半欧拉图当且仅当D是单向连通的，且 D中恰有两个奇度顶点，其中一个的入度比出度大1，另一个 的出度比入度大1，而其余顶点的入度都等于出度. 本定理的证明类似于定理15.1. 定理15.5 G是非平凡的欧拉图当且仅当G是连通的且为若干个边不重的圈之并. 可用归纳法证定理15.5. 例题 例1 设G是欧拉图，但G不是平凡图，也不是一个环，则?(G) ? 2. 证明：只需证明G中不可能有桥。 设C为G中一条欧拉回路，则对任意边e ? G ，必有p(G – e) = p(G) 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(佛罗莱)算法实例 一种错误走法： v2e2 v3e3 v4e14 v9e10 v2e1 v1e8 v8e9 (在有其它边可选的情况下，选择了走桥) v8e11 …… * 广东工业大学计算机学院 PLAY 从以上证明不难看出：欧拉图是若干个边不重的圈之并，见示意图3. (1) (2) 上图中，(1), (2)两图都是欧拉图，均从A点出发，如何找到一条欧拉回路？ v2 v9 v1 e2 v8 v6 v5 v7 v4 v3 e9 e1 e10 e14 e3 e7 e6 e5 e13 e4 e12 e8 e11 找欧拉路(或回路)可以用Fleury算法，如下： ??? (1)找一个出发点P(如果图中有两个奇数度的点话，任取其一)。 ??? (2)找一条与P相连的边，伸展欧拉路(选边的时候应注意，最后再选取断边;断边是：当