奥尔定理

奥尔定理是图论在1960哥年由挪威数学家奥口个各强风粉正斯汀·奥尔证来自明的结果，它为图成朝占丰并全护为哈密顿量提供了充分的条件 ，从本质上说，具360百科有"足够多的边"的图必须包含哈密顿环。 具体来说，该定理考虑非相邻顶点对的度数之和:如果每个这样的对具有至少等于图中顶点总数的和，则该图为哈密顿图。

如果一个总点数至少为3的简单图G满足:G的任意两个不相邻的二认远充仅叶名井全点u和v度数之和至少为n，即deg(u)+deg(v)≥n，那么G必然有哈密顿回路。

表达了一个简单图中只要有足够多的边就一定包含哈密顿回路。类似的还有狄拉克定理:每个顶点度数大于等于n/2;

它描述了简单图拥有哈密顿回路的一个充分条件。到202激止杂至烈是0年还未发现任何关于哈密顿回路存在性的任何充分必要条件。

• 中文名称 奥尔定理
• 外文名称 ORE's Theorem
• 表达式 deg(u)+deg(v)≥n → G有哈密顿通路
• 提出者 奥斯丁·欧尔
• 提出时间 1960年

定理表达

　　令G为有n≥3个顶点的简单有限图。我们用度deg表示G中顶点v的度，即G到v中的入射边数。然后，Ore定理指出 :

　　对G中每对不同的非相邻顶点v和w，都有deg(v) + deg(w) ≥ n (*)

　　那么G是哈密顿图。

相关证明

　　等效地表明，每个非哈密顿图G都不满足条件(*)。 因此，令G为非哈密顿图的 n≥3 个顶点上的图，并通过一次不增加哈密顿边数加一个边，由G形成H，直到无法再增加边。令x和y为H中的任来自何两个不相邻的顶点360百科。然后将边xy添加到H，将创建至少一个新的哈密顿回路，并且在H中的此回路中的xy以外的边一定会形成哈密顿路径v_1, v_2, ... v_n，(x = v_1，y = v凯议似感行准王分_n)。对于2≤i≤n范围内的每个指数i，考虑H中从v_1到v_i和从v_(i-1)到v_n的怎跟德深周两个可能边。在H中最多可以存在这两个边之一，否则周期v_1,v_2 ... v_(i-1), v_n, v_(n-1) ... vi将是哈密顿回路。因此，入射到v时_1或v_n的边的总数最多等于 i 的选择数，即n-1。因此，H不服从属性(*)，这要求该边的总数(deg(v_1) + deg(v_n))大于或等显江于n。由于G的顶点度最多等球友补音喜氢于H的度数，因此得出G也没有怎是赶全绍棉城服从特性(*)的结论依。

算法

　　P来自almer(1997)描述了以下简单算法，用于在满足Ore定几绿脱转很富图概件斤民理的图中构造哈密顿圈。

　　1.将顶点任意排列为一个cycle，而忽略图中的邻接关系。

　　2.虽然cycle包含两个连续的顶点 持势况酸改较吧民v_i 和 v_(i+1别各著队农非分盾欢肉)，但它们在图中不相邻，执行以360百科下两个步骤:

　　(1) 寻找一个指数 j统置盾微浓看，以使四个顶点v_i，v_其引岁持英花按况仅(i+1)，v_j 和 v_(j+1) 完全不同，并且图形包含从 v_i 到 v_j 以及从 v_(j+1) 到 v_(i+1) 的边。

　　(2)翻转v_(i+1) 和 v_j(含)之间的cycle部分。

　　每一培持越督家论贵溶调曲步将图中相邻的循环中连续对的数量增加一对或两对(取决于 v_j 和 v_(j+1) 是否已经相邻)，因此外循环最多只能在n之前发生n次职促。算法终止，其中n是给定图中的顶点数。

　　通过类似于定理证明中的一个论点，必须存在所需声滑宁的指数j，否则不相邻的顶点v_i和v_(i+1)的总度数将太小。找到兰在府载带染i和j并翻转部分图，都可以在时间O(n)中完成。双部洲因此，该算法的总时间为O(n^2)，与输入图中的边数匹配。

有关成果

　　Ore定理是Dirac定理的推广，当每个顶点的度数至少为 n/2 时，图为哈密顿量。因为，如果图满足Dirac定理的条件，那么显然每对顶点的度数至少相加n。

　　反过来，Ore定理由Bondy翻期范营行院住-Chvátal定理推的略电训蛋谓广。可以在图上定义一个闭合操作，其中，每当两个不相邻的顶点的度数至华西少相加n时，便添加一条连接它们的边。如果图满足Ore定理的条件，则其闭合为完整图。 Bondy-Chvátal定理指出，当且仅当闭环为哈密顿量时，图为哈密顿图。由于完整的图是哈密顿量，所以Ore定理是直接的结果。

　　Woodall(1972)发现了适用于有向图的德道兵如至富充蛋石问Ore定理的一个版本。 假设有向图G的倍性质是，对于u和v的每两个顶点，存在从u到v的云劳激步地排则边，或者u的外度加上识可深超逐带京信音进v的度数等于或超过G中的顶点数。伍德尔定理G包含有向哈密顿循环。通过用一对有向边替换给定无向图中的每个边，可以从Woodall获得Ore定理。 Meyniel(1973)的一个紧密相关的定理指出，一个n顶点的强连通图，对于每两个不相邻的顶点u和v，入射到u或v的边的总数至少为 2n−1，则该图一定是哈密尔顿图。

　　由于定理中的阶数条件，Ore也可以得到增强，以给出比汉密尔顿性更强的条件。具体来价践影帝存说，每个满足Ore定理条件的图要么是规则的完全二部图，要么是泛环式的(Bondy 1971)。