一个五阶图与路及圈的联图的交叉数

确定图的交叉数是NP-complete问题,现有的关于联图的交叉数的结果比较少,为此,讨论了五阶图4G分别与nK1,Pn及Cn的联图的交叉数.     

一个六阶图与路联图的交叉数

探讨一个六阶图与路的联图的交叉数．利用完全二部图k6,n的交叉数结果,证明了该六阶图与路的联图的交叉数为：Z（6,n）＋n＋1,n≥2．     

P6d=2与特殊图联图的交叉数

图的交叉数是图的一个重要参数,由于确定一般图类的交叉数已被证明是一个NP-完全问题,并且目前能够确定交叉数的图类甚少,因此关于图的交叉数问题仍值得研究。基于Kleitman关于完全二部图交叉数cr(K_{6, n})=Z(6,n)的基础上,文章运用数学归纳与反证的方法,研究并确定六阶图P₆^d=2与n个孤立点、路P_n和圈C_n联图的交叉数分别为cr(P₆^d=2+D_n)=Z(6,n)+n,cr(P₆^d=2+P_n)=Z(6,n)+n+1和cr(P₆^d=2+C_n)=Z(6,n)+n+3。     

笛卡尔积图Tn×Cm的交叉数

两个图G1和G2的笛卡尔积图G1×G2定义为如下的图：V（G1×G2）=V（G1）×V（G2）,E（G1×G2）={（u1,u2）（v1,v2）｜u1=v1且u2v2∈E（G2）,或者u2=v2且u1v1∈E（G1）}．图的交叉数是图论中的一个重要拓扑参数,而确定图的交叉数是一个完全胛一问题．本文确定了若干树Tn（n≤4）与圈Cm的笛卡尔积图的交叉数．     

完全二部图k_(4,n)去掉两条边的交叉数

用km,n表示完全二部图,用k4,m\e1,e2表示完全二部图k4,n去掉两条边e1、e2.本文确定了K4,n\e1,e2的交叉数为州z(4,n)-2[n/2]+2.K4,n\e1,e2.     

笛卡尔积图Tn×Cm的交叉数

两个图G1和G2的笛卡尔积图G1×G2定义为如下的图:V(G1×G2)=V(G1)×V(G2),E(G1×G2)={(u1,u2)(v1,v2)|u1=v1且u2v2∈E(G2),或者u2=v2且u1v1∈E(G1).图的交叉数是图论中的一个重要拓扑参数,而确定图的交叉数是一个完全NP-问题.本文确定了若干树Tn(n≤4)与圈Cm的笛卡尔积图的交叉数.     

含有Hamilton路的图的联图

Hamilton图是图论中重要的一类特殊图.主要证明了两个图的联图是Hamilton图,从而进一步证明了n个图的联图也是Hamilton图.     

联图CnVKn的全色数

研究了联图CnVKn=2n的全色数，证明了当n〉5时，金色数XT（CnVKn）=2n，从而证明了CnVKn．满足全着色猜想.     

图及联图的点分割数的计数研究

图划分具有广泛的应用,主要应用于VLSI（大规模集成电路）设计,并行计算,数据挖掘和图像分割等领域,因此得到了国内外学者的普遍关注和大量研究。由于图划分是NP-完全问题,因此本文在一般图划分问题基础上提出了特殊点割集及点分割数的概念,主要应用图的连通性原理分析,给出路、圈、扇图、轮图及完全二部图及联图P n,C n,F1n,W n,K m,n,m i=1ΣK n i等的点分割数,并分析讨论了完全图Kn删除一个独立边集后,其点分割数的变化情况。     

关于路和路的联图的邻点可区别的均匀全染色

一个图G的全染色被称为邻点可区别的,如果满足图G中任意两个相邻点所关联的元素所染的色的集合不同.一个图的邻点可区别的全染色被称为均匀的,如果满足任意两色所染元素的数目之差的绝对值不超过1.本文研究了联图P_n■P_n的邻点可区别的均匀全染色并证明它满足邻点可区别的均匀全染色猜想.     

以行人为中心的十字路口行人过街模型研究

此文根据元胞自动机论分析道路交通流,以行人利益为中心,方便行人为第一前提,从双向行人需求、车辆需求、行人车辆交互三方面建立行人过街方式模型,研究设计同时满足行人和车辆需求的交通管制方案的可行性,并给出了特例分析。模型考虑了行人产生概率、违规概率、群聚违规概率对车流和行人流的影响。提出了在保证行人安全便捷的前提下提高道路交通效率的意见方法。     

完全图的循环图分解和4个Ramsey数的下界

研究素数阶完全图分解为循环图的方法,给出了计算它的子图的团数的一种算法,得到２个三色,２个四色Ｒａｍｓｅｙ数的新的下界：Ｒ（３,４,１７）≥４４４,Ｒ（３,６,１７）≥８１２,Ｒ（３,３,４,１４）≥６９２,Ｒ（３,３,５,１５）≥１０２２。