(二)、性质与判定 1、性质 定理1（必要条件）若G为H图，则对V(G的任一非空 顶点子集S,有： o(G-S)≤S 证明：G是H图，设C是G的H圈。则对V(G)的任意 非空子集S,容易知道： o(C-S)≤S 所以，有： o(G-S)≤o(C-S)≤S
0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 −1 −0.5 0 0.5 1 n 6 (二)、性质与判定 1、性质 定理1 (必要条件) 若G为H图，则对V(G)的任一非空 顶点子集S，有： ( ) G S S − 证明：G是H图，设C是G的H圈。则对V(G)的任意 非空子集S, 容易知道: ( ) C S S − 所以，有： ( ) ( ) G S C S S − −
注：不等式为G是H图的必要条件，即不等式不满足 时，可断定对应图是非H图。 例3求证下图是非H图。 证明：取S={2,7,6),则有：o(G-S)=4>S=3 所以由定理1知，G为非H图
0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 −1 −0.5 0 0.5 1 n 7 注：不等式为G是H图的必要条件，即不等式不满足 时，可断定对应图是非H图。 例3 求证下图是非H图。 证明：取S=｛2, 7, 6｝,则有： 4 5 3 2 1 8 7 6 9 ( ) 4 3 G S S − = = 所以由定理1知，G为非H图。 G
注意：满足定理1不等式的图不一定是H图。 例如：著名的彼德森图是非H图，但它满足定理1的 不等式。 Peterson图 彼得森(1839-1910)，丹麦哥本哈根大学数学教授。 家境贫寒，因此而辍过学。但19岁就出版了关于对数的 专著。他作过中学教师，32岁获哥本哈根大学数学博士 学位，然后一直在该大学作数学教授
0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 −1 −0.5 0 0.5 1 n 8 注意：满足定理1不等式的图不一定是H图。 例如：著名的彼德森图是非H图，但它满足定理1的 不等式。 Peterson图 彼得森(1839-1910)，丹麦哥本哈根大学数学教授。 家境贫寒，因此而辍过学。但19岁就出版了关于对数的 专著。他作过中学教师，32岁获哥本哈根大学数学博士 学位，然后一直在该大学作数学教授
彼得森是一位出色的名教师。他讲课遇到推理困难时， 总是说：“这是显而易见的”，并让学生自己查阅他的著 作。同时，他是一位有经验的作家，论述问题很形象，讲 究形式的优雅。 1891年，彼得森发表了一篇奠定他图论历史地位的长达 28页的论文。这篇文章被公认是第一篇包含图论基本结论 的文章。同时也是第一次在文章中使用“图”术语。 1898年，彼得森又发表了一篇只有3页的论文，在这篇文 章中，为举反例构造了著名的彼得森图
0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 −1 −0.5 0 0.5 1 n 9 彼得森是一位出色的名教师。他讲课遇到推理困难时， 总是说：“这是显而易见的”，并让学生自己查阅他的著 作。同时，他是一位有经验的作家，论述问题很形象，讲 究形式的优雅。 1891年，彼得森发表了一篇奠定他图论历史地位的长达 28页的论文。这篇文章被公认是第一篇包含图论基本结论 的文章。同时也是第一次在文章中使用“图”术语。 1898年，彼得森又发表了一篇只有3页的论文，在这篇文 章中，为举反例构造了著名的彼得森图
2、判定 图的H性判定是NP-困难问题。到目前为止，有关的 定理有300多个，但没有一个是理想的。拓展H图的实 用特征仍然被图论领域认为是重大而没有解决的问题。 图的哈密尔顿问题和四色问题被谓为挑战图论领域 150年智力极限的总和。三位数学“诺奖”获得者 ErdOs、Whitney、Lovasz以及Dirac、.Ore等在哈密 尔顿问题上有过杰出贡献。 下面，介绍几个著名的定理。 10
0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 −1 −0.5 0 0.5 1 n 10 2、判定 图的H性判定是NP-困难问题。到目前为止，有关的 定理有300多个，但没有一个是理想的。拓展H图的实 用特征仍然被图论领域认为是重大而没有解决的问题。 图的哈密尔顿问题和四色问题被谓为挑战图论领域 150年智力极限的总和。三位数学“诺奖”获得者 ErdÖs、Whitney 、 Lovász 以及Dirac、Ore等在哈密 尔顿问题上有过杰出贡献。 下面，介绍几个著名的定理