回路：判断图的联通无向图存在欧拉回路

确定图的连通性

无向图中欧拉循环存在的充分必要条件：

无向图存在欧拉循环当且仅当该图所有顶点的度数均为偶数且该图是连通图。

有向图中欧拉回路存在的充要条件：

有向图具有欧拉环，所有顶点的入度等于出度，该图是连通图，或者说是一个顶点

度数为 1，另一个顶点的度数为 -1，其他顶点的度数为 0。

混合图中存在欧拉循环条件：

假设有一个有向图G'，无论方向如何，它都同构于G。 并且G'包含G的所有有向边。那么如果存在图G'使得G'具有欧拉回路，则G具有欧拉回路。 思路是将混合图转化为有向图判断。 实施时，

我们使用网络流模型。 现在任意构造一个G'。 令Ii表示第i个点的入度，Oi表示第i个点的出度。

若存在点k，|Ok-Ik|mod 2=1，则G中不存在欧拉回路。

接下来，对于所有点 Ii>Oi，从源点到 i 连接一条容量为 (Ii-Oi)/2 的边，

对于所有 Ii，如果对于节点 U 和 V，无向边 (U, V) ∈ E，

然后U和V在彼此之间建立一条容量无限的边。

如果该网络的最大流量等于Σ|Ii-Oi|/2，则存在欧拉循环。

欧拉电路

对有向无环图（Graph，简称DAG）G进行拓扑排序，

就是将G中的所有顶点排列成线性序列，使得对于图中的任意一对顶点u和v，如果ε E(G)，

那么在线性序列中u出现在v之前。

拓扑排序

什么是拓扑序列

通常，这样的线性序列称为满足拓扑序（Order）的序列，或者简称为拓扑序列。 简单的说，

从集合上的偏序获得集合上的全序称为拓扑排序。 离散数学中偏序和全序的定义：

如果集合 X 上的关系是 R，且 R 是自反、反对称和传递的，则称 R 是集合 X 上的偏序关系。

假设 R 是集合 X 上的偏序（Order）。如果对于每个 x 和 y 属于

比较简单的理解：偏序是指只能比较集合的部分成员，全序是指集合的所有成员都可以比较。

注意：

① 如果图中的顶点按拓扑顺序排列成一条线，则图中所有有向边都从左到右指向。

② 如果图中存在有向环，则不可能使顶点满足拓扑顺序。

③DAG的拓扑序列通常表明某个解是可行的。

一般应用

拓扑排序通常用于确定一组依赖关系中事物发生的顺序。 比如在日常工作中，

该项目可以分为四个子部分A、B、C、D来完成，但是A依赖于B和D，C依赖于D。为了计算这个项目应该执行的顺序，

可以对这个关系集进行拓扑排序，得到线性序列，排在第一位的任务就是需要先完成的任务。

基本实施方法

拓扑排序方法如下：

(1) 从有向图中选择一个没有前驱的顶点（即入度为0）并输出。

(2) 从网络中删除该顶点并删除从该顶点发出的所有有向边。

(3) 重复上述两步，直到剩余网络中不再有没有前驱的顶点。

拓扑排序