欧拉图的构造性证明与算法实现
1. 实验教学与指导
结合DFS，对于欧拉图定理进行构造性证明，证明过程就是算法实现过程。
定义（欧拉图）： 如果在图G中具有一条包含G中所有边的闭链，则称它为欧拉闭链，简称为欧拉链，称G为欧拉图。
定理： G是连通图，则G是欧拉图当且仅当G的所有节点都是偶节点。
证明：如果图G是欧拉图，则在G中有一条包含G中所有边的闭链（欧拉链）x1 x2 … xm，且x1= xm。如xi在序列x1 x2 … xm中出现k次，1£i£m-1，则d(xi)=2k。所以 G的所有节点都是偶节点。
图G是连通图且每个节点都是偶节点，可以用DFS在图G中搜索出一条闭链C。如果C不是欧拉链，则在C中必有一个节点vk，其度数大于在C中vk连接的边的数目，就用DFS从vk开始搜索一条边不在C中的闭链C’。如果CÈC’=G，则CÈC’是欧拉链；否则同理，在CÈC’中必有一个节点vk’，其度数大于在CÈC’中vk’连接的边的数目，再用DFS从vk’开始搜索一条边不在CÈC’中的闭链C”，加入到CÈC’中；以此类推，直到获得欧拉链。
显然，必要性的证明过程也是获得欧拉链的算法。
图的建模
图论提供了一个自然的结构，由此产生的数学模型几乎适合于所有科学（自然科学和社会科学）领域，只要这个领域研究的主题是“对象”与“对象”之间的关系。
建立图模型的首要问题是：在图中，什么为节点（对象）？什么为边（对象之间的关系）？
如果以直观的做法，珠子为节点，珠子串接的可能为边，则建立的图无法将问题的内容表达完全。例如，有3颗珠子（red | green），（red | white）和（red | red），则在图中可以给出回路（green | red）（red | white）（red | red），得到的图不符合题意，不能表示“对象”与“对象”之间的关系。
设图G(V, E)，每种颜色对应一个节点，V={ v1, v2, ……, vm }，每颗珠子对应一条边，若有珠子(c1, c2), 就有无向边{vc1, vc2}。收集的珠子是否能够串连成项链的问题就转化为在图G中是否存在欧拉链的问题。
2. 实验原理及方案
每种颜色代表一个节点，每颗珠子代表一条无向边，以此构成图G(V, E)。试题要求判别这个无向图是否为欧拉图。算法如下：
在输入测试用例的同时构造图G；计算每个节点的度数；对于一条边的两个节点，合并节点所在的并查集；找出序号值最小的节点s；
按照顺序搜索每个节点所在并查集的根：若存在两个节点分属不同的并查集，则说明图G是不连通图，欧拉链不存在；否则，
按照顺序分析每个节点的度：若存在度数为奇数的节点，则判定欧拉链不存在，无法连成项链；否则，
从s出发，通过DFS寻找欧拉链。
3. 前导实验理论：并查集及图的连通
在现实中，存在“物以类聚，人以群分”的关系，定义如下：
定义1（划分，块）. 设S是任意一个集合。SiÍS，Si¹Æ，i=1,2,…, n。如果S1ÈS2È……ÈSn=S，并且Si∩Sj=Æ（i,j=1, 2, …, n，i¹j），则称p={S1, S2, …, Sn}是S的一个划分，其中每个Si称为划分p的一个块。
由于这类问题主要涉及对集合的合并和查找，因此也称p={S1, S2, …, Sn}为并查集。
并查集维护互不相交的集合S1, S2, …, Sn，每个集合Si都有一个特殊元素rep[Si]，称为集合Si的代表元。并查集支持如下三种操作：
1．make_set(x)：加入一个含单元素的集合{x}到并查集p={S1, S2, …, Sn}中，则rep[{x}]=x。注意x不能被包含在任何一个Si中, 因为在p中任何两个集合都是不相交的。初始时，对每个元素x执行一次make_set(x)。
2．join(x, y)：把x和y所在的集合Sx和Sy合并，也就是说，从p中删除Sx和Sy，并加入SxSy。
3．set_find(x)：返回x所在集合Sx的代表元rep[Sx]。
并查集的存储结构一般采用树结构，每个集合用一棵树表示, 集合中的每个元素表示为树中的一个节点，根为集合的代表元（如图1）。
图1
每个节点p设一个指针set[p]，记录它所在树的根节点序号。如果set[p]<0，则表明p为根节点。初始时，为每一个元素建立一个集合，即set[x]=-1（1≤x≤n）。
对于查找操作，我们采用边查找边“路径压缩”的办法，在查找过程的同时，也减少树的深度。例如在图2(a)所示的集合中，查找元素y2所在集合的代表元，就从y2出发，沿路径y2-y3-y1-x1查找到x1，并依次将路径上的y2、y3、y1的set指针设为x1，如图2(b)。
图2
边查找边“路径压缩”的算法如下：
首先，从节点x出发，沿set指针查找节点x所在树的根节点f（set[f]<0）。然后进行路径压缩，将x至f的路径上经过的每个节点的set指针都指向f。查找过程如下：
int set_find(intp) // 查找p所在集合的代表元，用路径压缩优化
{
if (set[p]<0)
return p;
return set[p]=set_find(set[p]);
}
合并操作只需将两棵树的根节点相连即可。例如，将x所在的集合（树根fx）并入y所在的集合（树根fy），即以fx为根的子树上根节点的set指针指向fy，如图3。
图3
合并的算法如下：
计算x元素所在并查集的树根fx和y元素所在并查集的树根fy。如果fx==fy，则说明元素x和元素y在同一并查集中；否则将x所在的集合并入y所在的集合，也就是将fx的set指针设为fy：
void join(intp, int q) // 将p所在的集合并入q所在的集合
{
p=set_find(p);
q=set_find(q);
if (p!=q)
set[p]=q;
}
“路径压缩”是在查找过程中进行，而不在合并过程中进行，因为合并需要查找待合并的两个集合的根节点，路径压缩实际上就是减少查找中树的深度，从而减少查找的时间消耗。
判断图的连通性，可以用BFS、DFS、Warshell算法等，也可以通过并查集判断图的连通性：根据图的边给出节点集合的划分。一条边关联的两个点是相连的，就被划分到同一个集合中。初始时，图中每个节点构成一个集合。然后，依次输入边；如果输入的边所关联的两个节点是在同一个集合中，则这两个节点已经是连通的；如果输入的边所关联的两个节点是在两个不同集合中，则这两个集合中的节点至少可以通过该边连通，就将这两个集合进行合并。重复以上过程，就可得到节点集合的划分。如果所有节点在一个集合中，则图是连通图；否则，图不连通，而节点集合的每个划分是一个连通分支。
实验链接：https://developer.aliyun.com/adc/scenario/05a6a8a0d4be4385ad03d79ad3a21115
