欧拉图简述

主要参考大佬博客：https://blog.csdn.net/u011815404/article/details/86590498

欧拉图

欧拉图是在大家小学时学奥数都学习过的一个类型的题，无论你学得好不好，你都听过它的另外一个名字：一笔画问题；

一，首先来定义一下：

1.欧拉回路：图G的一个回路，如果恰通过图G的每一条边，则该回路称为欧拉回路，具有欧拉回路的图称为欧拉图。欧拉图就是从图上的一点出发，经过所有边且只能经过一次，最终回到起点的路径。

2.欧拉通路：即可以不回到起点，但是必须经过每一条边，且只能一次。也叫"一笔画"问题。

3.基图：基图是针对有向图的说法，是忽略有向图的方向得到的无向图。

4.欧拉图:存在欧拉回路的图。

欧拉回路一定要首尾相连，，通路不一定。

二.性质与定理

先说说有向图和无向图，显而易见，有向图就是有向的图，而无向图反之亦然。

呃，，此处及以下全转载至大佬博客：https://blog.csdn.net/qq_35649707/article/details/75578102

性质与定理

 定理1

无向图G为欧拉图，当且仅当G为连通图且所有顶点的度为偶数。

证明： 必要性

设图G的一条欧拉回路为C。由于C经过图G的每一条边，而图G没 有孤立点，所以C也经过图G的每一个顶点，G为连通图成立。而对于图G的任意一个顶点 v，经过C时都是从一条边进入，从另一条边离开，因此v经过C的关联边的次数为偶数。又由于C不重复地经过了图G的每一条边，因此 的度为偶数。

充分性

假设图G中不存在回路，而G是连通图，故 一定是G树，那么有|E|=|V|−1 |E|=|V|−1|E|=|V|-1由于图G所有顶点的度为偶数而且不含孤立点，那么图G的每一个顶点的度至少为2。

推论1

无向图G为半欧拉图，当且仅当G为连通图且除了两个顶点的度为奇数之外， 其它所有顶点的度为偶数。

证明：将两个度为奇数的顶点连接，由定理一得该图为欧拉图，故去掉环上一边为半欧拉图。

定理2

有向图G为欧拉图，当且仅当G的基图连通，且所有顶点的入度等于出度。

推论2

有向图G为半欧拉图，当且仅当G的基图连通，且存在顶点u的入度比出度大1 、v的入度比出度小 1，其它所有顶点的入度等于出度。证明同定理1相似。

性质1

设C是欧拉图G中的一个简单回路，将C中的边从图G中删去得到一个新的图G  ′   ′^{'},则 G  ′   ′^{'}的每一个极大连通子图都有一条欧拉回路。

证明  若G为无向图，则图G  ′   ′^{'}的各顶点的度为偶数；若G为有向图，则图 G  ′   ′^{'}的各顶点的入度等于出度。

性质2

设 C1、C2是图G的两个没有公共边，但有至少一个公共顶点的简单回路，我们可以将它们合并成一个新的简单回路 。

三.如何判定（是不是欧拉回路/图)

以下全是我个人理解，完全依据于小奥的学习经验，不一定全对，有错请指出。

我说的尽量简单一点：

首先每一个点都有它的度：即与它相连的边的个数

我们把奇度的点称为奇点，反之偶点

根据奥数知识一句话则可以判断无向图是否是欧拉图：有0或2个奇点

但是对于有向图判断则复杂一些：每条边只经过一次而且每个点也只过一次

四。如何实现判定

下面用一道模板题来简述一下吧。附:欧拉树的题往往无法判断是图论题

见下：

给定n个各不相同的无序字母对（区分大小写，无序即字母对中的两个字母可以位置颠倒）。请构造一个有n+1个字母的字符串使得每个字母对都在这个字符串中出现。

输入输出格式

输入格式：

第一行输入一个正整数n。

以下n行每行两个字母，表示这两个字母需要相邻。

输出格式：

输出满足要求的字符串。

如果没有满足要求的字符串，请输出“No Solution”。

如果有多种方案，请输出前面的字母的ASCII编码尽可能小的（字典序最小）的方案

输入样例#1：  输出样例#1：