[科普中国]-麦雷迪斯图

麦雷迪斯图(Meredith graph)是一特殊的图。它是猜想“每一个4正则4连通图是哈密顿图”的反例。它是H.J.麦雷迪斯在1973年发现的具有70个顶点和140条边的图。

概念麦雷迪斯图(Meredith graph)是一特殊的图。它是猜想“每一个4正则4连通图是哈密顿图”的反例(见图)。它是H.J.麦雷迪斯在1973年发现的具有70个顶点和140条边的图。

极图极图是一类特殊的图。指阶数一定在某种意义下最大的图。给定一个图族L，在所有n阶图中含边最多，不以L中图为其子图的图。这个给定的图族L称为禁用图类。关于L的全部n阶极图的集记为Ex(n，L)，其中每个极图边数相等，记为ex(n，L)。例如，Tm，n图，即有n个节点，各部节点数分别为[n/m](即n/m的整数部分)或[n/m]+1的完全m部图，就是一个极图。其中，L是m+1阶完全图.Tm，n常称为图兰图。事实上，有图兰定理：在所有不含完全图Kn作为子图的m阶图中，边数最多的图只有一个，就是Tm，n-1.它第一次出现在图兰(Turn，P.)1941年发表的文章中，由此而得名。

哈密顿图1859年，英国数学家哈密顿提出一种名为“周游世界”的游戏。他用正十二面体(如图1)的20个顶点代表20个大城市，要求沿着棱从一个城市出发，经过每个城市恰好一次，然后回到出发点。

这个游戏曾经风靡一时。为了清楚起见，我们作一个平面图(如图2)，与这个十二面体的顶点和棱所组成的图同构，则图中粗的边组成的圈就是一个所求的路线。我们还可以找到其他的路线。

一般地，在一个给定的图中，若存在一条回路，经过每个顶点恰好一次，则这个回路称为哈密顿回路;若一个图中可以找到一个哈密顿回路，则这个图称为哈密顿图。表面上看哈密顿图的概念与欧拉图的概念非常相似，但两者迥然不同。可以找到一个欧拉图但不是哈密顿图的例子，也可以找到一个哈密顿图但不是欧拉图的例子。

对哈密顿图的判定问题，迄今还没有像欧拉图那样能找到一个很漂亮的充分必要条件。奥尔给出了一个很重要的充分条件：G为简单图，顶点数n≥3，且对每一对不相邻的点u，v，有：

这里degu表示与u相关联的边数，则G为哈密顿图。由此还可以得到一个推论：G为简单图，顶点数n≥3，若对G中任何点u，有：degu≥n/2，则G为哈密顿图。

图论近年来比较活跃的数学分支之一。图论是研究各种图的性质和特征的一门理论，主要包括图与子图、图的连通性、可平面性、正则图、树、着色问题、图的矩阵以及网络等内容。图论的发展已有200多年的历史。早在18世纪中叶就已出现有关图的文字记载。这时的图论尚处于萌芽阶段，多数问题是围绕着游戏而产生的，最有代表性的是著名的哥尼斯堡七桥问题(相当于我国的一笔画问题)。19世纪中叶到20世纪中叶，图论问题大量出现，诸如哈密尔顿“绕行世界”问题，关于地图着色的四色问题以及与之有关联的图的可平面性等等。在这个阶段，也出现了以图为工具去解决其他领域中一些问题的成果，例如，凯莱把图论应用到有机化学中关于同分异构物的计数问题，克希霍夫应用树研究电网络的分析问题等等。20世纪中叶以后，由于生产管理、军事、交通运输、计算机网络等方面提出的实际问题的需要，特别是许多离散性问题的出现，以及由于有了大型超高速计算机，而使大规模问题的求解成为可能，图论及其应用的研究得到了飞速发展。这个阶段的开创性工作是以福特和福克逊建立的网络流理论为代表的。图论和线性规划、动态规划等优化理论和方法的相互渗透，促进了组合最优化理论和算法的研究以及图论对实际问题的应用，与此同时也丰富了图论的内容，使图论的发展更加充满活力。1

本词条内容贡献者为:

李宗秀 - 副教授 - 黑龙江财经学院