第11章-参考资料：欧拉图的判别法

广东工业大学计算机学院1无向欧拉图的判别法定理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时如下证明：广东工业大学计算机学院2无向欧拉图的判别法(续)定理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’1G’2……G’s，每个连通分支至多有k条边，且无奇度数顶点设与C的公共顶点为vji，由归纳假设可知G’1G’2……G’s都是欧拉图，因而各自存在一条欧拉回路。从某个顶点vr开始，沿C行走，每遇到一个vji，则经过该连通分支的欧拉回路，最后回到vr，得到一条欧拉回路。∴无向图G是欧拉图广东工业大学计算机学院3无向欧拉图的判别法证明图示PLAY从以上证明不难看出：欧拉图是若干个边不重的圈之并，见示意图3.广东工业大学计算机学院4半欧拉图的判别法定理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中欧拉通路.广东工业大学计算机学院5有向欧拉图的判别法定理15.3有向图D是欧拉图当且仅当D是强连通的且每个顶点的入度都等于出度.本定理的证明类似于定理15.1.定理15.4有向图D是半欧拉图当且仅当D是单向连通的，且D中恰有两个奇度顶点，其中一个的入度比出度大1，另一个的出度比入度大1，而其余顶点的入度都等于出度.本定理的证明类似于定理15.1.定理15.5G是非平凡的欧拉图当且仅当G是连通的且为若干个边不重的圈之并.可用归纳法证定理15.5.广东工业大学计算机学院6(1)(2)例题例1设G是欧拉图，但G不是平凡图，也不是一个环，则(G)2.证明：只需证明G中不可能有桥。设C为G中一条欧拉回路，则对任意边eG，必有p(G–e)=p(G)上图中，(1),(2)两图都是欧拉图，均从A点出发，如何找到一条欧拉回路？广东工业大学计算机学院7Fleury(佛罗莱)算法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中一条欧拉回路.广东工业大学计算机学院8Fleury(佛罗莱)算法实例一种错误走法：v2e2v3e3v4e14v9e10v2e1v1e8v8e9(在有其它边可选的情况下，选择了走桥)v8e11……v2v9v1e2v8v6v5v7v4v3e9e1e10e14e3e7e6e5e13e4e12e8e11