若干小回路串成欧拉回路 ·若连通图G中所有的边包含在若干边不相交的简单回路中，则G中含欧拉 回路。 ·证明：对G中简单回路个数施归纳法。当=1时显然。 ·假设dkk21)时结论成立。考虑d=k+1. ·按某种方式对k+1个简单回路排序，令G=G-E(Ck+),设G中含s个连 通分支，则每个非平凡分支所有的边包含在相互一 路中，且回路个数不大于k。由归纳假 问题3：你能够从 欧拉图，设其欧拉回路是C。因G连 G中的欧拉回路构造如下：从Ck+ 这样的数学归纳法 边，每当遇到一个尚未遍历的C'与 中，看到寻找欧拉 上的边，回到v'继续沿Ck进行。 回路的算法吗？若干小回路串成欧拉回路 • 若连通图G中所有的边包含在若干边不相交的简单回路中，则G中含欧拉 回路。 • 证明：对G中简单回路个数d施归纳法。当d=1时显然。 • 假设dk(k1)时结论成立。考虑d=k+1. • 按某种方式对k+1个简单回路排序，令G‘=G-E(Ck+1)，设G’中含s个连 通分支，则每个非平凡分支所有的边包含在相互没有公共边的简单回 路中，且回路个数不大于k。由归纳假设，每个非平凡连通分支Gi均为 欧拉图，设其欧拉回路是Ci '。因G连通，故Ck+1与诸Ci ’都有公共点。 • G中的欧拉回路构造如下：从Ck+1上任一点(设为v0 )出发遍历Ck+1上的 边，每当遇到一个尚未遍历的Ci '与Ck+1的交点(设为vi '), 则转而遍历Ci ' 上的边，回到vi '继续沿Ck+1进行。 问题3：你能够从 这样的数学归纳法 中，看到寻找欧拉 回路的算法吗？