文 献 综 述
本文研究的是强正则图的的识别码问题，那么首先就得知道什么是强正则图？什么又是识别码？再将二者联系起来进行分析研究，从而得到我们所需要的结论。
说到强正则图，那么我们必须先从图论开始了解。图G=(V,E)是一个二元组(V,E)使得Esube;[V]的平方，所以E的元素是V的2-元子集。为了避免符号上的混淆，我们总是默认Vcap;B=Oslash;。集合V中的元素称为图G的定点(或节点、点)，而集合E的元素称为边(或线)。通常，描绘一个图的方法是把定点画成一个小圆圈，如果相应的顶点之间有一条边，就用一条线连接这两个小圆圈，如何绘制这些小圆圈和连线时无关紧要的，重要的是要正确体现哪些顶点对之间有边，哪些顶点对之间没有边。图论本身就是应用数学的一部分，众所周知许多新的理论往往源于问题，图论也不例外，它最早起源于一个著名的问题——柯尼斯堡问题，1738年被瑞典数学家欧拉成功解决，标志着图论的诞生，同时把欧拉当作了图论的创始人。图论真正意义上引起广泛的注意和研究是在1859年，英国数学家汉密尔顿发明了一种游戏:用一个规则的实心十二面体，它的20个顶点标出世界著名的20个城市，要求游戏者找一条沿着各边通过每个顶点刚好一次的闭回路，即'绕行世界'。用图论的语言来说，游戏的目的是在十二面体的图中找出一个生成圈。这个生成圈后来被称为汉密尔顿回路。这个问题后来就叫做汉密尔顿问题。而运筹学、计算机科学和编码理论中的很多问题都可以化为汉密尔顿问题，彰显了图论的重要性。在图论的历史中，还有一个最著名的问题--四色猜想。这个猜想说，在一个平面或球面上的任何地图能够只用四种颜色来着色，使得没有两个相邻的国家有相同的颜色。每个国家必须由一个单连通域构成，而两个国家相邻是指它们有一段公共的边界，而不仅仅只有一个公共点。这一问题最早于1852年由Francis Guthrie提出，最早的文字记载则现于德摩根于同一年写给哈密顿的信上。包括凯莱、肯普等在内的许多人都曾给出过错误的证明。泰特(Tait)、希伍德(Heawood)、拉姆齐和哈德维格(Hadwiger)对此问题的研究与推广引发了对嵌入具有不同亏格的曲面的图的着色问题的研究。一百多年后，四色问题仍未解决。1969年，Heinrich Heesch发表了一个用计算机解决此问题的方法。1976年，阿佩尔(Appel)和哈肯(Haken)借助计算机给出了一个证明，此方法按某些性质将所有地图分为1936类并利用计算机，运行了1200个小时，验正了它们可以用四种颜色染色。四色定理是第一个主要由电脑证明的理论，这一证明并不被所有的数学家接受，因为采用的方法不能由人工直接验证。最终，人们必须对电脑编译的正确性以及运行这一程序的硬件设备充分信任。主要是因为此证明缺乏数学应有的规范，以至于有人这样评论'一个好的数学证明应当像一首诗--而这纯粹是一本电话簿!'
虽然四色定理证明了任何地图可以只用四个颜色着色，但是这个结论对于现实上的应用却相当有限。现实中的地图常会出现飞地，即两个不连通的区域属于同一个国家的情况(例如美国的阿拉斯加州)，而制作地图时我们仍会要求这两个区域被涂上同样的颜色，在这种情况下，四个颜色将会是不够用的。
20世纪80-90年代曾邦哲的综合系统论(结构论)观将'四色猜想'命题转换等价为'互邻面最大的多面体是四面体'。每个地图可以导出一个图，其中国家都是点，当相应的两个国家相邻时这两个点用一条线来连接。所以四色猜想是图论中的一个问题。它对图的着色理论、平面图理论、代数拓扑图论等分支的发展起到推动作用。
(下图是在上下对折再左右对折以后形成一个轮胎形状，有7个区域两两相连，就是说在一个环面上作图，需要7种颜色，外国数学家构造林格证明:Np=[(7 radic;1 48p)/2]，p=1，N1=7。
图论的广泛应用，促进了它自身的发展。20世纪40-60年代，拟阵理论、超图理论 、极图理论，以及代数图论、拓扑图论等都有很大的发展。
在了解强正则图之前，我们先了解一下什么叫正则图。各顶点的度均相同的无向简单图称为正则图（regular graph）。各顶点度均为k的正则图称为k-正则图。
定义：对于图G，如果存在mgt;0，使得 A^m(i, j)gt;0,则称图G是正则的。 其中i , j 是任意给定的属于V（图G的顶点集）的两点，A为图G的邻接矩阵。
在图论中，强规则图定义如下。 设G =（V，E）是具有v个顶点和k度的规则图。 如果还存在整数lambda;和mu;，则称G是强有规律的：
