[科普中国]-福克曼图

福克曼图(Folkman graph)是一类极图，具有最少顶点(20个)的边可迁但非顶点可迁的正则图。

概念福克曼图(Folkman graph)是一类极图，具有最少顶点(20个)的边可迁但非顶点可迁的正则图(见图)。1

极图极图是一类特殊的图。指阶数一定在某种意义下最大的图。给定一个图族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年发表的文章中，由此而得名。

正则图正则图是一类特殊的图。指所有节点的次都相同的图。节点的次为k的正则图称为k正则图。一个图上某一条边的次是指这个图上与这条边有公共端点的边的数目。所有边的次都相同的图称为边正则图。对于一个图，若存在正整数k，λ，μ，使得下列条件成立，则称该图为强正则图：

1.G是k正则图。

2.对于图上任意两个不同节点v和w，若v和w相邻，则G上与v和w都相邻的节点的数目是λ，否则，G上与v和w都相邻的节点的数目是μ。

3.正则图是指所有节点的次都是3的图。每个连通片不是圈就是二阶完全图，即由一条杆组成的图，称为一个半正则图。1

格雷图格雷图是一种特殊的图。指一个有54个顶点(较福克曼图多)的3正则的边可迁但非顶点可迁的图。它是这样构造的：三个K3，3图，每个的九条边一一对应，每一对应的三边组中加一个剖分点，如图中v1，v2，v3，然后另加一点v4与此三点相连。下面的图只画出其中一组。

本词条内容贡献者为:

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