张图

张图(Chang graphs)是一种重要的图组，由张里千于1960年发现，它是与三角形图T(8)具有相同参数但互不同构的三个强正则图1。

基本介绍张图是由张里千于1960年发现，它是与三角形图T(8)具有相同参数但互不同构的三个强正则图。三角形设计中所出现的结合方案是一个约翰生结合方案J(n，2)，因而是一个度量方案，相应的距离正则图是强正则图，记为T(n)，称为三角形图，张里千于1959年、霍夫曼(A.J.Hoffman)于1960年证明：若Γ为与三角形图T(n)有相同参数的强正则图，则当n>8时，Γ与T(n)同构，当n=4，5，6，7时，上述结论也成立，张里千指出：当n=8时，除T(8)外，恰有三个与T(8)有相同参数但不同构的强正则图，通常记为T′(8)，T"(8)及T〞(8)，它们被称为张图，名称由此而来。1

相关概念距离正则图距离正则图(distance-regular graph)是一类与结合方案有关的图，设Γ是一个连通图，有v个顶点，无环边及重边，Γ中两顶点间的距离是连结这两点的最短路所含的边数，Γ中任意两个顶点之间距离的最大值称为Γ的直径，若对Γ中距离为k的任意两个顶点x，y，与x的距离为i且与y的距离为j的顶点z的个数是一个常数Cijk，与x，y的选择无关，则称Γ为距离正则图，直径为2的距离正则图称为强正则图1。

度量方案度量方案(metric scheme)是一类结合方案，由距离正则图定义，若Γ为直径d的距离正则图，规定两个顶点的距离为i时它们有第i种结合关系，则在Γ的顶点集合上有一个d个结合类的结合方案，称为度量方案。许多最重要的结合方案都是度量方案。例如，具两个结合类的结合方案一定是度量方案。汉明结合方案与约翰生结合方案也都是度量方案。但是，并非所有的结合方案都是度量方案1。

约翰生结合方案约翰生结合方案(Johnson association scheme)亦称三角形结合方案，是一类度量方案，设k≤v/2，以J(v，k)记某个v元集的k元子集的全体，若当两个k元子集的交为k-i元子集时，规定它们有第i种结合关系，则J(v，k)是有

个处理及k个结合类的结合方案，称为约翰生结合方案。当k=2时，约翰生结合方案即为三角形设计中的结合方案。约翰生结合方案在编码理论中也有重要应用，例如，每一个等重量码都可看做某个约翰生结合方案中的子集。

本词条内容贡献者为:

王海侠 - 副教授 - 南京理工大学