还在持续更新ing

前言

此乃小 Oler 的一篇算法随笔，从今日后，还会进行详细的修订。

注明：有参考自论文《欧拉图相关的生成与计数问题探究》

简单介绍

• 著名的哥尼斯堡七桥问题是18世纪著名的古典数学问题之一，该问题在相当长的时间里无人能解。欧拉经过研究，于1736年发表了论文《哥尼斯堡的七座桥》。这篇论文不仅圆满地回答了哥尼斯堡居民提出的问题，而且给出并证明了更为广泛的一般性结论。从那时起，图论作为数学的一个新的分支而诞生。因此，欧拉图问题是图论的起源，也是图论研究中十分重要的一部分。

• 欧拉图是指通过图（无向图或有向图）中所有边且每边仅通过一次通路，相应的回路称为欧拉回路。具有欧拉回路的图称为欧拉图（Euler Graph），具有欧拉通路而无欧拉回路的图称为半欧拉图。对欧拉图的一个现代扩展是蜘蛛图，它向欧拉图增加了可以连接的存在点。这给予欧拉图析取特征。欧拉图已经有了合取特征(就是说区定义了有着与起来的那些性质的对象在区中的存在)。所以蜘蛛图允许使用欧拉图建模逻辑或的条件。

    								注明：该介绍均来自于网络。
  

1 基本概念

定义 1.1. 图 \(G\) 中与顶点 \(v\) 关联的边数（自环统计两次）称为图 \(G\) 中顶点 \(v\) 的度。特别地，对于有向图 \(G\)，进入顶点 \(v\) 的边的条数称为顶点 \(v\) 的入度；从顶点 \(v\) 引出的边的条数称为顶点 \(v\) 的出度。

定义 1.2. 图 \(G\) 中度为奇数的点称为奇顶点，度为偶数的点称为偶顶点，度为 \(0\) 的点称为孤立点。

定义 1.3. 对于无向图 \(G\) 中的两点 \(u\) 和 \(v\) ，若存在 \(u\) 到 \(v\) 的路径，则称 \(u\) 和 \(v\) 是连通的。如果图 \(G\) 中任意两点都是连通的，则称图 \(G\) 为连通图。对于有向图 \(G\)，将所有的有向边替换为无向边得到图 \(G\) 的基图，若图 \(G\) 的基图是连通的，则称图 \(G\) 是弱连通图。

定义 1.4. 对于图 \(G\) 中边 \(e\) ，若删去 \(e\) 后图 \(G\) 的连通分量的数量增加，则称边 \(e\) 为 \(G\) 的桥（割边）。

定义 1.5. 图 \(G\) 中一条路径指一个顶点与边的交替序列 \(v_0, e_1, v_1, ..., e_m, v_m\)，其中 \(e_i\) 为 \(v_{i−1}\) 到 \(v_i\) 的一条边。回路指满足 \(v_0 = v_m\) 的一条路径，一般不区分起点。

定义 1.6. 图 \(G\) 中经过每条边恰一次的回路称为欧拉回路，经过每条边恰一次的路径称为欧拉路径。

定义 1.7. 存在欧拉回路的图称为欧拉图，存在欧拉路径但不存在欧拉回路的图称为半欧拉图。

定义 1.8. 不含平行边（也称重边）也不含自环的图称为简单图。

2 关于欧拉图的判定

2.1 无向图的判定

这里我们需要分类讨论，可以按顶点的度的奇偶性分类，如下

对于只存在偶顶点的图：

定理 2.1. 无孤立点的无向图 \(G\) 为欧拉图，当且仅当图 \(G\) 连通且所有顶点的度都是偶数。

证明. 首先证明必要性。因为图 \(G\) 存在欧拉路径且没有孤立点，所以任意两个点都可以相互到达，图 \(G\) 一定是连通图。如果图G存在回路 \(v_0, v_1, ..., v_{m−1}, v_0\)，那么对于顶点 \(v_i(i = 0, 1, 2, 3,..., m − 1)\) 来说，有一条进入 \(v_i\) 的边就有一条从 \(v_i\) 引出的边，所以与 \(v_i\) 相邻的边总是成对的，得到 \(v_i\) 的度为偶数。因此，如果图 \(G\) 存在欧拉回路，那么图 \(G\) 为连通图且所有顶点的度都是偶数。

接着我们来说明充分性。从 \(G\) 中任意顶点 \(v_0\) 出发，经关联的边 \(e_1\) 进入 \(v_1\)，因为 \(v_1\) 的度数是偶数，一定可以由 \(v_1\) 再经关联的边 \(e_2\) 进入 \(v_2\)，如此继续下去，每条边仅经过一次，经过若干步后必可回到 \(v_0\)，于是得到了一个圈 \(c_1\)。如果 \(c_1\) 恰是图 \(G\) ，则命题得证。否则在 \(G\) 中去掉 \(c_1\) 后得子图 \(G_1\)，\(G_1\) 中每个顶点也是偶顶点，又因为图 \(G\) 是连通的，所以在 \(G_1\) 中必定存在一个和 \(c_1\) 公共的顶点 \(u\)，在 \(G_1\) 中存在一个从 \(u\) 出发，到 \(u\) 结束的圈 \(c_2\)，于是 \(c_1\) 和 \(c_2\) 合起来仍是一个回路。重复上述过程，因为 \(G\) 中总共只有有限条边，总有一个时候得到的图恰好是 \(G\)。

来自蒟蒻的理解 2.1. 简单的来说，对于一个没有孤立点的无向欧拉图来说，要使其成为欧拉回路，先要保证图为连通，这个很容易理解。那么再到图中的任意一点 \(v\) 都必须最终回到自己，那么就会有 \(d\) 条边出去，最后又有 \(d\) 条边进来，计算度数即为 \(2 \times d\)，由此可知图中的点都会是偶数个。

对于存在奇顶点的图：

定理 2.2. 如果无向连通图有 \(2k\) 个奇顶点，则图 \(G\) 可以用 \(k\) 条路径将图 \(G\) 的每一条边经过一次，且至少要使用 \(k\) 条路径。

证明. 我们先来证明路径条数的下界。设图 \(G\) 可以分解成 \(h\) 条链，每条链上至多有两个奇顶点，所以有 \(2h \ge 2k\)，即 \(h \ge k\)。因此 \(k\) 是路径数量的下限。

接下来我们只需要构造一组方案。把这 \(2k\) 个奇顶点分成 \(k\) 对 \((v_1, v_1') , (v_2, v_2') , ... , (v_k, v_k')\)。在每对点 \((v_i, v_i')\) 之间添加一条边，得到图 \(G'\)。图 \(G'\) 连通且没有奇顶点，所以 \(G'\) 存在欧拉回路。再把这 \(k\) 条新添的边从回路中去掉，这个圈至多被分为 \(k\) 段，我们就得到了 \(k\) 条链。这说明图 \(G\) 是可以用 \(k\) 条路径将图 \(G\) 的每一条边经过一次的。

来自蒟蒻的理解 2.2. 同上一个定理所述的差不多，但图中出现了奇数度的顶点，若

综合上述两个定理，我们已经了解了欧拉回路与欧拉路径存在的充要条件。我们可以由此推导出半欧拉图的判定条件：

定理 2.3. 无孤立点的无向图 \(G\) 为半欧拉图，当且仅当图 \(G\) 连通且 \(G\) 的奇顶点个数为 \(2\) 。

此时两个奇顶点分别为欧拉路径的起点和终点。