图论是离散数学的一个重要分支,近二百多年来取得了迅猛发展,已经应用到各个领域,包括物理、化学、通讯科学、计算机技术、生物遗传学等等。本文对图论中的三个难题,即:图的交叉数问题、图的路径层矩阵问题、不含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）和具有相同路径层矩阵的不同构的无割点的图的最小顶点数f2的上界分别由44和31下降到18,即得到f（4）≤18,f2≤18。 极图问题是图论的核心问题之一,不含多边形的极图问题是极图问题中的一类经典问题。本文对不含3,4,5边形的极图问题进行研究,给出了顶点数为不大于42的整数时不含3,4,5边形的极图的边数,设计并实现了一个从n=2开始至n=42利用n-1个顶点的临界图构造n个顶点的临界图的算法,从而构造出所有顶点数为不大于42的整数的不含3,4,5边形的极图;对n>42,本文给出了极图边数的上界。