哈密尔顿图
哈密尔顿图是图论中的一个重要概念,它涉及到图中的一种特殊路径——哈密尔顿路径或哈密尔顿圈。哈密尔顿图问题起源于旅行商问题,即寻找一条通过图中所有顶点恰好一次并回到起点的路径。在给定的例子中,用正十面体和正十二面体的顶点和棱代表城市和旅游路线,寻找的就是这样的哈密尔顿路径。 定义11.2.1明确了哈密尔顿路径和哈密尔顿圈的含义。如果图中存在一条包含所有顶点的路径,那么这条路径就是哈密尔顿路径。如果这个路径形成了一个闭合的圈,那么这个圈就是哈密尔顿圈。一个包含哈密尔顿圈的图被称为哈密尔顿图。 然而,判断一个图是否为哈密尔顿图是一个复杂的问题,目前还没有找到一种通用的充要条件。例如,图11.2.2中的两个图都不是哈密尔顿图。定理11.2.1提供了一个必要条件,即对于哈密尔顿图G,如果删除任意非空真子集S的顶点,剩余子图的连通分支数不超过S的顶点数。但这个条件并不充分,如彼得森图就是一个反例。 定理11.2.2和推论11.2.1给出了哈密尔顿图的一些充分条件。如果图G的任意两个非邻接顶点的度数之和大于等于顶点总数n,或者每个顶点的最小度数至少为n/2,那么G是哈密尔顿图。 对于有向图,哈密尔顿有向图的概念类似,其中路径必须是定向的。哈密尔顿有向图是强连通的,意味着从任一顶点都能到达其他所有顶点。定理11.2.3指出,如果一个有向图G满足任意顶点的入度加上出度大于等于顶点总数,且G是强连通的,那么G是哈密尔顿有向图。 在竞赛图的背景下,定理11.2.4表明在没有平局的循环赛中,总存在一个哈密尔顿有向路径,即存在一个选手的胜利顺序。如果图还是强连通的(如定理11.2.5所述),则图是哈密尔顿有向图,这意味着所有比赛选手之间可以形成一种连贯的胜败关系。 定义11.2.3引入了传递竞赛图,这是一种理想化的竞争模型,表示排名靠前的选手总是能战胜排名靠后的选手。定理11.2.6指出,一个竞赛图是传递竞赛图的充要条件是图中没有圈,即不存在甲胜乙、乙胜丙、丙胜甲的循环。 推论11.2.2进一步指出,如果一个竞赛图不是传递竞赛图,那么图中必然存在长度为3的圈,揭示了在实际比赛中可能存在以弱胜强的情况。 哈密尔顿图及其相关理论在图论中占有重要地位,它们不仅涉及基本的数学概念,还与实际问题如旅行商问题、网络设计等紧密相关。理解和应用这些理论有助于解决实际中的优化问题。