高等学校21卌纪教材 定义1.14图G中的一链(或路),若它通过 G中的每个结点恰好一次,则该链(或路)称为哈 密尔顿链(或路) 哈密尔顿图尽管在形式上与欧拉图极其相 似,但其结论上却有很大不同,至今还没有得 到关于哈密尔顿图的非平凡的充要条件,这是 图论尚未解决的主要问题之一。然而,还是有 不少重要成果,下面给出几个必要和充分条件 的定理 PT PRESS 人民邮电出版社
定义11.1.4 图G中的一链(或路)，若它通过 G中的每个结点恰好一次，则该链(或路)称为哈 密尔顿链(或路)。 哈密尔顿图尽管在形式上与欧拉图极其相 似，但其结论上却有很大不同，至今还没有得 到关于哈密尔顿图的非平凡的充要条件，这是 图论尚未解决的主要问题之一。然而，还是有 不少重要成果，下面给出几个必要和充分条件 的定理
高等学校21卌纪教材 定理111.5若连通图G=<V,E>是哈密尔 顿图,S是的任意真子集,则o(GS)≤S 本定理给出是哈密尔顿图的一个必要条件 但这个条件又不便于使用,因为它要求对G的结 点集合的所有真子集进行验证。尽管如此,利 用它还可以证明某些图不是哈密尔顿图。 PT PRESS 人民邮电出版社
定理11.1.5 若连通图G=<V，E>是哈密尔 顿图，S是V的任意真子集，则ω(G-S)≤|S|。 本定理给出是哈密尔顿图的一个必要条件， 但这个条件又不便于使用，因为它要求对G的结 点集合的所有真子集进行验证。尽管如此，利 用它还可以证明某些图不是哈密尔顿图
高等学校21卌纪教材 下面给出图G是哈密尔顿图的充分条件, 这个结果是于1952年 GA Dirac研究得到的。 定理1116给定简单图G=V,E>,|=n, 若n3和δ≥m2,则G是哈密尔顿图。 请注意,本定理给出的仅是充分条件。例 如,十多边形显然是哈密尔顿图,但δ=22 10 PT PRESS 人民邮电出版社
下面给出图G是哈密尔顿图的充分条件， 这个结果是于1952年G.A.Dirac研究得到的。 定理11.1.6 给定简单图G=<V，E>，|V|=n， 若n≥3和δ≥n/2，则G是哈密尔顿图。 请注意，本定理给出的仅是充分条件。例 如 ， 十多 边 形显 然是 哈 密尔 顿图 ， 但 δ=2≥ =5
高等学校21卌纪教材 Bondy和 Chvatol于1969年证明了更强的充 分条件。他们的方法是建立下面两个引理之上 的 引理1给定图G=<V,E>,|=n>3。 若u,v∈V,u与怀邻接且d(u)+d(v)≥,则G是 哈密尔顿图分G+(u,v)是哈尔密顿图 受引理1.11示,可以定义图的闭包概念。 PT PRESS 人民邮电出版社
Bondy和Chvatol于1969年证明了更强的充 分条件。他们的方法是建立下面两个引理之上 的。 引理11.1.1 给定图G=<V，E>，|V|=n≥3。 若u，v∈V，u与v不邻接且d(u)+d(v)≥n，则G是 哈密尔顿图G+〔u，v〕是哈尔密顿图。 受引理11.1.1启示，可以定义图的闭包概念
高等学校21卌纪教材 定义14给定图GV,E,|=n。 图G的闭包是由G通过相继地用边连接两 个其度之和至少为m的不邻接结点,直到 不能如此进行为止而得到的图。用C(G表 示图G的闭包。 引理12C(G)是唯一确定的。 PT PRESS 人民邮电出版社
定义11.1.4 给定图G=<V，E>，|V|=n。 图G的闭包是由G通过相继地用边连接两 个其度之和至少为n的不邻接结点，直到 不能如此进行为止而得到的图。用C(G)表 示图G的闭包。 引理11.1.2 C(G)是唯一确定的