哈密顿回路，简述欧拉回路和哈密尔顿回路的区别

本文目录一览

1，简述欧拉回路和哈密尔顿回路的区别
2，Hamilton什么意思
3，哈密顿回路的算法是怎样的
4，什么是哈密顿回路问题
5，hamilton圈算法是什么意思
6，n阶完全图中有多少条哈密顿回路

1，简述欧拉回路和哈密尔顿回路的区别

我只知道欧拉图这是数学家欧拉提出的.用几个圆圈表示几个概念的外延关系.下面是一个欧拉图，图片点击可以放大

从一个顶点出发每条边恰好经过一次，再回到出发点的巡回（闭通路）叫欧拉巡回，含有欧拉巡回的图叫欧拉图。从一个顶点出发每个顶点恰好经过一次，再回到出发点的圈叫哈密尔顿圈，含哈密尔顿圈的图叫哈密尔顿图

简述欧拉回路和哈密尔顿回路的区别

2，Hamilton什么意思

Hamilton 汉密尔顿

哈密顿图（哈密尔顿图）（英语：hamiltonian path，或traceable path）是一个无向图，由天文学家哈密顿提出，由指定的起点前往指定的终点，途中经过所有其他节点且只经过一次。在图论中是指含有哈密顿回路的图，闭合的哈密顿路径称作哈密顿回路（hamiltonian cycle），含有图中所有顶点的路径称作哈密顿路径。　　从图中的任意一点出发，路途中经过图中每一个结点当且仅当一次，则成为哈密顿回路。　　要满足两个条件：　　⒈封闭的环　　⒉是一个连通图，且图中任意两点可达　　经过图（有向图或无向图）中所有顶点一次且仅一次的通路称为哈密顿通路。　　经过图中所有顶点一次且仅一次的回路称为哈密顿回路。　　具有哈密顿回路的图称为哈密顿图，具有哈密顿通路但不具有哈密顿回路的图称为半哈密顿图。　　平凡图是哈密顿图。

Hamilton什么意思

3，哈密顿回路的算法是怎样的

哈密顿回路的算法是指:在图论中是指含有哈密顿回路的图，闭合的哈密顿路径称作哈密顿回路。哈密顿图（哈密尔顿图）（英语：Hamiltonian path，或Traceable path）是一个无向图，由天文学家哈密顿提出，由指定的起点前往指定的终点，途中经过所有其他节点且只经过一次。这个问题和著名的七桥问题的不同之处在于，过桥只需要确定起点，而不用确定终点。哈密顿问题寻找一条从给定的起点到给定的终点沿途恰好经过所有其他城市一次的路径。

哈密顿回路的算法是怎样的

4，什么是哈密顿回路问题

在图中找出一条包含所有结点的闭路，并且，出来起点和重点重合外，这条闭路所含结点是互不相同的可以在多项式时间类判断一个回路是否是哈密顿回路但目前没有算法直接解出哈密顿回路天文学家哈密顿(William Rowan Hamilton) 提出，在一个有多个城市的地图网络中，寻找一条从给定的起点到给定的终点沿途恰好经过所有其他城市一次的路径。这个问题和著名的过桥问题的不同之处在于，某些城市之间的旅行不一定是双向的。比如A→B,但B→A是不允许的。换一种说法，对于一个给定的网络，确定起点和终点后，如果存在一条路径，穿过这个网络，我们就说这个网络存在哈密顿路径。哈密顿路径问题在上世纪七十年代初，终于被证明是“NP完备”的。据说具有这样性质的问题，难于找到一个有效的算法。实际上对于某些顶点数不到100的网络，利用现有最好的算法和计算机也需要比较荒唐的时间（比如几百年）才能确定其是否存在一条这样的路径。

5，hamilton圈算法是什么意思

哈密顿图（哈密尔顿图）（英语：Hamiltonian path，或Traceable path）是一个无向图，由天文学家哈密顿提出，由指定的起点前往指定的终点，途中经过所有其他节点且只经过一次。在图论中是指含有哈密顿回路的图，闭合的哈密顿路径称作哈密顿回路（Hamiltonian cycle），含有图中所有顶点的路径称作哈密顿路径。　　从图中的任意一点出发，路途中经过图中每一个结点当且仅当一次，则成为哈密顿回路。　　要满足两个条件：　　⒈封闭的环　　⒉是一个连通图，且图中任意两点可达　　经过图（有向图或无向图）中所有顶点一次且仅一次的通路称为哈密顿通路。　　经过图中所有顶点一次且仅一次的回路称为哈密顿回路。　　具有哈密顿回路的图称为哈密顿图，具有哈密顿通路但不具有哈密顿回路的图称为半哈密顿图。　　平凡图是哈密顿图。

得看问你是不是有向的。。。无向的话除以2，有向的话不除。

6，n阶完全图中有多少条哈密顿回路

n阶完全图中哈密顿回路的条数为：（n-1)!/2选定一个点，从这点开始到每个点的走法，只要有三个点以上就是圈，因此只管走的方法，选定构成一个圈的点算了两次，所以要除以2。若一个图的每一对不同顶点恰有一条边相连，则称为完全图。完全图是每对顶点之间都恰连有一条边的简单图。n个端点的完全图有n个端点及n(n ? 1) / 2条边，以Kn表示。它是(k ? 1)-正则图。所有完全图都是它本身的团（clique）。

哈密顿图:图g的一个回路,若它通过图的每一个节点一次,且仅一次,就是哈密顿回路.存在哈密顿回路的图就是哈密顿图.哈密顿图就是从一点出发,经过所有的必须且只能一次,最终回到起点的路径.图中有的边可以不经过,但是不会有边被经过两次.n阶完全图中哈密顿回路的条数为：（n-1)!/2选定一个点，从这点开始到每个点的走法，只要有三个点以上就是圈，因此只管走的方法，选定构成一个圈的点算了两次，所以要除以2。若一个图的每一对不同顶点恰有一条边相连，则称为完全图。完全图是每对顶点之间都恰连有一条边的简单图。n个端点的完全图有n个端点及n(n ? 1) / 2条边，以kn表示。它是(k ? 1)-正则图。所有完全图都是它本身的团。你算出的那个是无项完全图的条数吧。设kn的每一条哈密顿回路是v1,v2...vn,v1v1,v2...vn对应完全图顶点的一个全排列所以kn中不同的哈密顿回路有n!条。

（n-1)!/2选定一个点，从这点开始到每个点的走法，只要有三个点以上就是圈，因此只管走的方法，选定构成一个圈的点算了两次，所以要除以2