任给两个无(有)向图G、H。判断这两个图是否同构是图论中的一个基本问题。为了判断二者是否同构,可以先分别将两个图标准化,通过判断两个标准化的图是否同构,从而最终达到判别最初的两个图是否同构的目的。要实现图的标准化就要计算图的规范标号,其是与图对应的唯一一个字符串。由于图的结构常常非常复杂,其内部会隐含着许多纵横交织的对称结构,这使得要标准化一个图有时变得异常的困难。由于图的对称结构在本质上反映了图的自同构结构。因而要彻底地剖析图的同构问题,可以在对图做标准化的过程中,一块结合图来认真地研究自同构问题。为了计算自同构可以采用代数法,其首先计算一个图的特征根、特征向量,然后利用自同构和特征根、特征向量之间的代数关系来求解图的自同构群。本文有两条主线:一条是围绕如何计算无(有)向图的规范标号来展开的,其所涉及到的图既可以是连通的也可以是非连通的。另外一条是围绕如何利用图的特征根、特征向量来计算图的自同构群来展开的。本文尤其围绕第一条主线展示了大量的研究工作,不仅包括理论,而且包括软件开发和系统实现。本文的创新点如下:1.首次按照本文给出的规范标号定义,建立了一套计算无向图G的规范标号Cmax(G)的新理论和通用的方法。利用该方法可以准确地计算许多类型无向图的最大元图,包括树、格图、轮图、超立方图、国王图、三角图等等。为此,它考察了无向图的规范标号与其补图规范标号之间存在的相互关系。它系统地检查了计算无向图的规范标号和k-邻域子图之间的联系。它首次引入了几个概念,包括扩散度序列、完整扩散度序列等等;2个定理揭示了如何计算最大节点序列MaxQ(G)中的首先节点。另外的1个定理显示了如何计算最大节点序列MaxQ(G)中的第2个节点。当计算规范标号Cmax(G)时,如果最大节点序列MaxQ(G)已经含有i个节点u1,u2,…,ui,扩散定理和最近节点定理指明了如何计算最大节点序列MaxQ(G)中的后续节点。它也提供了两个定理来计算非连通无向图G的规范标号Cmax(G)。它提供了 4个算法来计算无向图G的最大节点序列MaxQ(G)。本文还猜测,如果存在1个节点 v ∈ S(G) = {u|u∈V(G)) ∧d(u)=△(G)}满足条件|S(G)|>1和Cmax(G-v)≤Cmax(G-w),则最大节点序列 Max(G)中的 u1 =v。2.为了对图进行分类和降低计算无向图G的最大元图Lmax(G)的计算复杂性,首次定义了一系列新的概念并建立了一套完整的理论框架,这些概念包括划分树、最大划分树、中央子图、标准正则序列和标准最大正则序列等等。5个算法的实施展示了如何相应地计算它们。利用中央子图可以计算加入到图G的最大节点序列MaxQ(G)中的首先节点。全部5个算法的时间复杂性均为O(n2),并通过实验得到了验证。定理的证明表明划分树、最大划分树的叶子顶点是正则子图,图G中仅仅存在一个中央子图。正则划分定理表明,给定一个图,各自存在唯一一个划分树、最大划分树、标准正则序列和标准最大正则序列与其相对应。可以使用分类定理来对图集进行分类。2个定理揭示了中央子图和加入到图G的最大节点序列MaxQ(G)中的首先节点之间的联系。所给出的定理可以被辅助用来计算无向图的规范标号Cmax(G)。所提出的方法可以被扩展,使其能够处理有向图和加权图。3.本文首次提出了一套计算有向图G的规范标号Cmax(G)的新理论和通用的方法。使用该方法,能精确计算出许多类有向图的最大元有向图。为此,它考察了有向图的规范标号与其补图规范标号之间存在的相互关系。它系统地检查了计算有向图的规范标号和k-邻域以及k-混合邻域子图之间的联系。它首次引入了几个概念,包括混合扩散出度序列、完整混合扩散出度序列等等;为了提高计算规范标号的准确性,它对于有向图G中的每个节点分配一个属性m_NearestNode。4个定理揭示了如何计算最大节点序列MaxQ(G)中的首先节点。另外的两个定理显示了如何计算最大节点序列MaxQ(G)中的第2个节点。当计算规范标号Cmax(G)时,如果最大节点序列MaxQ(G)已经含有i个节点u1,u2,…,ui,扩散定理揭示了如何计算最大节点序列MaxQ(G)中的随后节点。混合扩散定理进一步指明了最大节点序列MaxQ(G)中的第i + 1个节点应该来自于节点集合Q= {u1,u ,…,ui}的开混合邻域有向子图N++(Q)。它也提供了两个定理来计算非连通有向图G的规范标号Cmax(G)。它提供了 4个算法来计算有向图G的最大节点序列MaxQ(G)。本文还猜测,如果存在1个节点 v ∈S+(G)={u|u∈V(G)∧d+(u)=△+(G)}满足条件|S+(G)|>1和Cmax(G -v)≤Cmax(G -w),则最大节点序列 MaxQ(G) 中的 u1=v。4.本文首次提出了用于计算一个加权图的自同构群的代数方法。如果一个图没有重复的特征值和所提的猜想是真的,它可以在多项式时间内计算出图的自同构群。为了计算加权图的自同构群,首次引入了特征值划分的概念。第二,使用代数方法,考察了不仅邻接矩阵的对角形与它的特征值、特征向量之间的关系,也考察了特征值、特征向量和自同构群之间的关系。更进一步,证明了7个定理。它也显示了在正交矩阵和置换矩阵之间,也在正交矩阵和自同构之间存在的密切关系。虽然这种方法具有一定的局限性和需要改进,从理论上而言,它是求解自同构群的一个必要的补充。