全国科学技术大会奖励专栏 >> 2005年度国家自然科学奖目录

2005年度国家自然科学奖


哈密顿圈及圈覆盖理论

由福州大学范更华完成

   该项目属图论中的基础理论研究。现实世界中,许多问题的数学抽象形式可以用图来描述,如互联网、通讯网、集成电路、分子结构等都可用图来描述。对图的研究形成了一个专门的数学学科:图论。
    过图中每点恰好一次的圈称为哈密顿圈。哈密顿圈问题是图论最古老的研究课题之一,是至今未解决的世界难题,在许多领域有着重要应用。该项目在这一问题的研究上开辟了一条新途径,引发了大量后续工作。以“范定理”、“范条件”、“范类型”被广泛引用,并作为定理出现在国外的教科书中。
    若一个图的某些子图共同包含了该图的所有边,则称该图被这些子图覆盖。子图覆盖是图论学科最具基础性的研究课题。圈是一类重要的子图。圈覆盖是子图覆盖研究的一个重要方向。著名“四色问题”的一个等价形式是:无割边平面图可被两个偶子图(圈的并)覆盖。Itai-Rodeh猜想:若图的边数为m,点数为n,则一定有长度不超过m+n-1的圈覆盖。二十多年来,此猜想吸引了许多国际一流学者,久而未决。该项目攻克了这一猜想。
    在子图覆盖理论的研究上,该项目创立了一种新方法,为这一研究领域提供了一个强有力的新工具。通过该方法,该项目彻底解决了有二十多年历史的Chung路覆盖猜想:任何n顶点的连通图可被一组个数不超过[n/2]的路所覆盖。

权所有:国家科学技术奖励工作办公室 E-Mail:nosta@mail.nosta.gov.cn 联系电话:010-68511819