哈密顿图
哈密顿图
重定向;重新导向;字符;字元;文件; 档案;快捷方式; 捷径;项目;专案;计划;计划;计划;计算机; 电脑; 电脑;
匈牙利人名顺序为先姓后名。本条目中的译名遵从此顺序。
定义.
下列定义，既适用于无向图，亦适用于有向图。
性质.
哈密尔顿图的必要条件：
若G=(V,E) 是一个哈密尔顿图，则对于V的每一个非空子集S，均有W(G－S) ≤|S|。其中|S|是S中的顶点数，W(G－S)表示图G擦去属于S中的顶点后，剩下子图的连通分支的个数。
充分条件.
对欧拉图而言，有某个充要条件，可用作简单判定一幅图是否欧拉图（欧拉定理）。然而，对于哈密顿图，并无相应的结果。
不过，仍有一系列越来越松的判别条件，能够断定一幅图必定为哈密顿图。此类定理，最早见于1952年的研究，其想法直观，即只要有「足够多」边，就能迫得图有哈密顿圈。用顶点的度推出存在哈密顿圈的定理之中，目前最优的，是1976年邦迪与赫瓦塔尔的定理。
以上是有关无向图的部分。对于有向图，相应的定理举例有Ghouila–Houiri。
狄拉克定理.
于1952年证明以下定理：
formula_1个顶点的简单图（formula_2）中，若每个顶点的度皆至少为formula_3，则必为哈密顿图。
欧尔定理.
设 formula_4 是一个无向简单图，formula_5，formula_6。若对于任意两个不相邻的顶点 formula_7，都有 formula_8 和 formula_9 的度，即 formula_10 与 formula_11 满足 formula_12，那么，formula_13 是哈密尔顿图。
此条件由挪威图论数学家奥斯丁·欧尔在1960年给出。
波绍定理.
证明了几条有关哈密顿圈的定理。以下具体引用一条1962年的定理，有关连边少的顶点：
一幅formula_1个顶点的完全图（formula_2），若满足：
则必为哈密顿图。
注意formula_1为偶时，条件2已包含于条件1，所以只在formula_1为奇数时，条件2才需要分开列出。
作为例子，考虑附图中，具有formula_24个顶点的图。其为哈密顿图：已经将顶点排列好，使哈密顿圈formula_25（以红色标示）正好是外圈。
哈密顿路径问题.
寻找哈密顿路径是一个典型的NP-完全问题。后来人们也证明了，找一条哈密顿路的近似比为常数的近似算法也是NP-完全的。
寻找哈密顿路的确定算法虽然很难有多项式时间的，但是这并不意味着只能进行时间复杂度为formula_43暴力搜索。利用状态压缩动态规划#重定向
重定向;重新导向;，可以将时间复杂度降低到formula_44，具体算法是建立方程f[i][S][j]，表示经过了i个节点，节点都是集合S的，到达节点j时的最短路径。每次都按照点j所连的节点进行转移。
本站由爱斯园团队开发维护，感谢那些提出宝贵意见和打赏的网友，没有你们的支持，网站不可能发展到今天，
继往开来，善终如始，我们将继续砥砺前行。
Copyright ©2014 iissy.com, All Rights Reserved.