陈志强[1]2003年在《具有相同路径层矩阵的无割点四正则图》文中指出图论是应用数学的一个重要分支，它有着广泛的应用背景。图论是一门既古老又年轻的学科，它已经有二百多年的历史了，但随着计算机技术的出现和进步，图论的理论有了飞速的发展，焕发出青春的活力。 本文所研究的具有相同路径层矩阵的图的问题是在药品分析的实际应用领域中提出来的。一个图G的路径层矩阵τ(G)(the path layer matrix)包含关于图G中的所有路径的定量信息。矩阵元素τ_(i,j)表示图G中起点为i，路径长度为j的路径数。图的路径层矩阵与图的同构问题密切相关。对于顶点数较少的图，路径层矩阵相等是图的同构的充要条件，已经验证当图G的顶点数p(G)≤11时，本结论成立。目前已知的具有相同路径层矩阵的不同构的图的最小顶点数为14。 已知的具有相同路径层矩阵的不同构的四正则图的最小顶点数为44，具有相同路径层矩阵的不同构的五正则图的最小顶点数为48，具有相同路径层矩阵的不同构的六正则图的最小顶点数为51(杨元生，J.Graph Theory 39(2002)219-221)。 早期所构造出的具有相同路径层矩阵的不同构图对都是有割点的，1999年，Dobrynin构造出了一对的具有相同路径层矩阵的不同构的36个顶点的无割点叁正则图和一对具有相同路径层矩阵的不同构的31个顶点的无割点图(A.A.Dobrynin,J.Graph Theory 38(2001)177-182)。 本文对Dobrynin的构造具有相同路径层矩阵的图对的基本图的特性进行了更深入的探讨，明确了基本图的特性，给出了一种新基本图，并从理论上证明了这种利用新基本图通过交叉连接的方法构造具有相同路径层矩阵的图对的方法的正确性。 针对新基本图的构造过程中的关键问题，在生成具有相同顶点度序列的图，计算路径向量，查找无割点图等方面，本文设计和实现了一系列较好的算法，成功地解决了构造新基本图的问题。 利用上述算法，本文构造出了一对顶点数为18的具有相同路径层矩阵的不同构的无割点的四正则图，从而把具有相同路径层矩阵的四正则图的最小顶点数与无割点图的最小顶点数的上界均降到18。相关的论文已经投往美国SCI刊源J.Graph Theory。
林晓惠[2]2004年在《图的交叉数等图论难题的研究》文中进行了进一步梳理图论是离散数学的一个重要分支,近二百多年来取得了迅猛发展,已经应用到各个领域,包括物理、化学、通讯科学、计算机技术、生物遗传学等等。本文对图论中的叁个难题,即:图的交叉数问题、图的路径层矩阵问题、不含3,4,5边形的极图问题的计算机算法进行研究,将计算机构造性证明和数学证明相结合,取得了较好的结果。 图的交叉数问题是在实际应用中提出来的,在CAD领域有广阔的应用。已经证明图的交叉数是NP困难问题。本文对图的交叉数进行研究,对已有的计算图的交叉数的算法CNN的限界条件进行了改进,利用改进后的算法计算了顶点数不超过18的循环图和顶点数不超过16的广义Petersen图的交叉数,根据算法所构造的相应的好的画法,得到了众不小于3时P(4k+2,2K)、P(4k+2,4)和K,m均不小于4时P(mk,K)的交叉数的上界;以及众不小于4,m不小于3时C(mk;{1,k})和当n为不小于13的奇数时C(n;{1,[n/2-1]})的交叉数的上界。同时对图的交叉数采用分组计数的方式进行计算。通过对不同的循环图类设计相应的不同的分组方式和交叉点计数函数,成功确定了当n为不小于8的整数时循环图C(n;{1,3})、当K为不小于3的整数时循环图C(3k;{1,k})和当n为不小于8的偶数时循环图C(n;{1,n/2-1})的交叉数的下界,并最终确定了它们的值。 具有相同路径层矩阵的图的问题是在药品分析的实际应用领域中提出来的,与图的同构问题紧密联系。本文设计出了一种新的研究路径层矩阵的方法,用计算机构造具有一定特征的基本图,将4个相同的基本图分别通过不同的方式两两连接,从而构造一对具有相同路径层矩阵的不同构的图,并对该方法的正确性进行了数学证明。设计并实现了较好的构造γ-正则基本图的算法,利用该算法构造出一个9个顶点的4-正则基本图,并以此构造出了一对18个顶点的没有割点的具有相同路径层矩阵的不同构的4-正则图,将具有相同路径层矩阵的不同构的4-正则图的最小顶点数f(4)和具有相同路径层矩阵的不同构的无割点的图的最小顶点数f_2的上界分别由44和31下降到18,即得到f(4)≤18,f_2≤18。 极图问题是图论的核心问题之一,不含多边形的极图问题是极图问题中的一类经典问题。本文对不含3,4,5边形的极图问题进行研究,给出了顶点数为不大于42的整数时不含3,4,5边形的极图的边数,设计并实现了一个从n=2开始至n=42利用n-1个顶点的临界图构造n个顶点的临界图的算法,从而构造出所有顶点数为不大于42的整数的不含3,4,5边形的极图;对n>42,本文给出了极图边数的上界。
参考文献：
[1]. 具有相同路径层矩阵的无割点四正则图[D]. 陈志强. 大连理工大学. 2003
[2]. 图的交叉数等图论难题的研究[D]. 林晓惠. 大连理工大学. 2004