[科普中国]-距离正则图

概念

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

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

图图论的研究对象。一个图是一个集合上的一种二元关系。这个集合的元素称为图的节点，若两节点之间有这种确定的二元关系，则称有一条边连这两个节点。一个图的节点的数目称为这个图的阶；图的边的数目称为它的度。在文献中，总是将一般的图记为G=(V，E)，其中，V=V(G)和E=E(G)分别表示G的节点集和边集。

若有一条边连一个图的某两个节点，则称这两个节点相邻，并称这两个节点为这条边的端点。若某一节点是某一条边的端点，则称这个节点和这条边关联。若两条边和同一节点关联，则称这两条边相邻，两个端点是同一个节点的边称为环。若某条边的两个端点不是同一个节点，且只有一条边连这两个节点，则称这条边为杆。

只有一个节点而没有边的图称为平凡图。没有边的图称为孤立图。以某两节点为端点的边可能不止一条，这时称连这两个节点的边为重边。既可以有环，也可以有重边的图称为准图；没有环而可能有重边的图称为带重图；没有重边而可能有环的图称为带环图；既没有重边也没有环的图称为简单图。若一个图的阶是有限的，则称这个图为有限图，否则称这个图为无限图。每两个节点都相邻的简单图称为完全图。若一个n阶图的节点用1，2，…，n来代表，则称它为标定图。若在图的每一条边上赋以一个实数或者对于每个节点赋以一个实数，则称它为赋权图。2

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

1.G是k正则图。

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

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

连通图在图论中，连通图基于连通的概念。在一个无向图G 中，若从顶点vi到顶点vj有路径相连（当然从vj到vi也一定有路径），则称vi和vj是连通的。如果 G 是有向图，那么连接vi和vj的路径中所有的边都必须同向。如果图中任意两点都是连通的，那么图被称作连通图。如果此图是有向图，则称为强连通图（注意：需要双向都有路径）。图的连通性是图的基本性质。

对一个图G=(V,E) 中的两点x和y，若存在交替的顶点和边的序列：

Γ=(x=v0-e1-v1-e2-...-ek-(vk+1)=y) (在有向图中要求有向边vi−(vi+1)属于E)，则两点x和y是连通的。Γ是一条x到y的连通路径，x和y分别是起点和终点。当x=y时，Γ 被称为回路。如果通路 Γ 中的边两两不同，则 Γ 是一条简单通路，否则为一条复杂通路。如果图G中每两点间皆连通，则G是连通图。

连通分量：无向图G的一个极大连通子图称为G的一个连通分量（或连通分支）。连通图只有一个连通分量，即其自身；非连通的无向图有多个连通分量。

强连通图：有向图G=(V,E) 中，若对于V中任意两个不同的顶点x和y，都存在从x到y以及从y到x的路径，则称G是强连通图。相应地有强连通分量的概念。强连通图只有一个强连通分量，即是其自身；非强连通的有向图有多个强连分量。

单向连通图：设G=是有向图，如果u->v意味着图G至多包含一条从u到v的简单路径，则图G为单连通图。

弱连通图：将有向图的所有的有向边替换为无向边，所得到的图称为原图的基图。如果一个有向图的基图是连通图，则有向图是弱连通图。3

初级通路：通路中所有的顶点互不相同。初级通路必为简单通路，但反之不真。