“欧拉回路”与“哈密尔顿回路”

1．欧拉回路

17世纪的东普鲁士有一座哥尼斯堡（Konigsberg）城（现为俄国的加里宁格勒（Kaliningrad）城），城中有一座奈佛夫（Kneiphof）岛，普雷格尔（Pregol）河的两条支流环绕其旁，并将整个城市分成北区、东区、南区和岛区4个区域，全城共有7座桥将4个城区相连起来，如图1所示。人们常通过这7座桥到各城区游玩，于是产生了一个有趣的数学难题：寻找走遍这7座桥，且只许走过每座桥一次，最后又回到原出发点的路径。该问题就是著名的“哥尼斯堡七桥问题”。

图1  哥尼斯堡地图

1736年，大数学家列昂纳德·欧拉（L.Euler）发表了关于“哥尼斯堡七桥问题”的论文—《与位置几何有关的一个问题的解》（Solutio Problematis ad Geomertriam Situs Pertinentis），他在文中指出，从一点出发不重复地走遍七桥，最后又回到原出发点是不可能的。

为了解决哥德斯堡七桥问题，欧拉对该问题进行了抽象，用4个字母A、B、C、D代表4个城区，用7条线表示7座桥，如图2所示。这样做抽象出了问题中最本质的东西，忽视问题非本质的东西（如桥的长度、宽度等），从而将哥尼斯堡七桥问题抽象为一个数学问题，即经过图中每边一次且仅一次的回路问题。欧拉在论文中论证了这样的回路是不存在的，后来，人们把有这样回路的图称为欧拉图。

欧拉在论文中将问题进行了一般化处理，即对给定的任意一个河道图与任意多座桥，判定可能不可能每座桥恰好走过一次（不一定回到原出发点），并用数学方法给出了3条判定的规则：

（1）如果通奇数座桥的地方不止两个，满足要求的路线是找不到的。

（2）如果只有两个地方通奇数座桥，可以从这两个地方之一出发，找到所要求的路线。

（3）如果没有一个地方是通奇数座桥的，则无论从哪里出发，所要求的路线都能实现。

上述3条判定规则包含了任一连通无向图是否存在“欧拉路径（Euler Path）”和“欧拉回路（EulerCircuit）”的判定条件。根据判定规则（3）可以得出，任一连通无向图存在欧拉回路的充分必要条件是图的所有顶点均有偶数度。

图2  图

2.哈密尔顿回路

“哈密尔顿回路问题”问题是爱尔兰著名学者威廉·哈密尔顿爵士（W.R.Hamilton）1859年提出的一个数学问题。其大意是：在任一给定的图中，能不能找到这样的路径，即从一点出发不重复地走过所有的结点（不必通过图中每一条边），最后又回到原出发点。

3.欧拉回路与哈密尔顿回路的区别

“哈密尔顿回路问题”与“欧拉回路问题”看上去十分相似，然而却是完全不同的两个问题。“哈密尔顿回路问题”是访问除原出发结点以外的每个结点一次且仅一次（图2有哈密尔顿回路，如B到C到A到D再到B就是一个回路），而“欧拉回路问题”是访问每条边一次且仅一次；对任一给定的图是否存在“欧拉回路”欧拉已给出了充分必要条件，而对任一给定的图是否存在“哈密尔顿回路”至今仍未找到满足该问题的充分必要条件。

4.例题

赛纳河流经巴黎的这一段河中有两个岛，河岸与岛间架设了15座桥。如下图所示。问：（l）能否从某地出发，经过这15座桥各一次后再回到出发点？

（2）若不要求回到出发点，能否在一次散步中，穿过所有的桥各一次？若可以，请把路径写出。

解：将该问题进行抽象,如下图所示.(1)就变成了是否存在欧拉回路的问题了;(2)就变成了是否存在欧拉路径的问题了.

    A和B是通偶数座桥的地方，C和D是通奇数座桥的地方，满足欧拉给出的判定规则（2），即如果只有两个地方通奇数座桥，可以从这两个地方之一出发，找到欧拉路径；但不满足规则（3），即不存在欧拉回路。

必为哈密尔顿回路的条件

任意两个结点的度数和>=n(点的个数)

一定有汉密尔顿路的图：任意两个结点的度数和>=n-1

哈密顿回路模板：

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
#include<stdlib.h>
#include<queue>
#include<set>
#include<iomanip>
#include<math.h>
using namespace std;
typedef long long ll;
typedef double ld;
const int INF = 0x3f3f3f3f;

int n, m, x, lenth, g[MAXN][MAXN], num[MAXN], ans[MAXN];
bool val[MAXN], visit[MAXN];
void print(){
    for(int i=1;i<lenth;i++) printf("%d ",ans[i]);
    printf("%d\n",ans[lenth]);
}
void dfs(int last, int cur){
    visit[cur] = true;
    ans[++lenth] = cur;
    for(int i=1;i<=n;i++){
        if(g[cur][i] && i==x&&x!=last){
            ans[++lenth] = i;
            print();
            lenth--; 
            //break;
        }
        if(!visit[i]&&g[cur][i]&&(i>cur)) dfs(cur,i);
    }
    lenth--;//»ØËÝ 
    visit[cur] = false;//»ØËÝ 
}
 
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        int u, v;
        scanf("%d%d",&u,&v);
        g[u][v]++;
        g[v][u]++;
    }
    for(x=1;x<=n;x++)
        {
        lenth=0;dfs(0,x);
        }
    return 0;
}