具有极小Hosoya指数的含圈共轭图

图G=(V(G),E(G))为简单连通共轭图,即含有完备匹配的图,其顶点集为V(G),边集为E(G).n,m表示含有n(n≥8)个顶点m(n≤m≤n+2n-2)条边的共轭图集合.用m(G,k)表示G中恰含k条边的匹配个数.z(G)表示图G的Hosoya指数,即G的所有匹配的总数.对于任何一个共F轭图G,都存在一个完备匹配.把G的边集分成两个子集,其中一个子集为图G的完备匹配所含的边,记为M(G),另一个子集为图G除完备匹配之外剩余的边,记为Q(G).对于G中任一个k-匹配,都可以从完备匹配M(G)中选j(0≤j≤k)条边,再从Q(G)中选择k-j条边,且保证所选的k条边互不相邻.如果对任意G1,G2∈n,m和k≤2n,都满足m(G1,k)≤m(G2,k),那么,就可以证明∑k2n=0m(G1,k)≤∑k2n=0m(G2,k),即z(G1)≤z(G2).本文用这种排列组合的方法研究并刻画了n,m中具有最小、次小Hosoya指数的极值图.     

基于生物网络的频繁Hamilton子图挖掘算法

【目的】在生物网络的功能模体发现问题中涉及到频繁子图的挖掘,而功能模体通常是一个非树型结构的子图,甚至具有Hamilton回路。为了减少挖掘出子图的结果集,提高频繁子图挖掘的效率,分析了在生物网络中挖掘频繁Hamilton子图的算法。【方法】对网络连接矩阵构造了一种运算,得到网络路径信息,通过对路径的合并,搜索出网络中所有的Hamilton子图。【结果】在理论分析和证明的基础上,给出了2-路径和3-路径的搜索算法,进而构造了Hamilton子图的搜索算法,并对算法的复杂度进行了分析,最后将算法应用于真实生物网络,找出了频繁Hamilton子图。【结论】与现有子图搜索算法相比,由于搜索的只是Hamilton子图,减少了搜索结果集,同时引入了代数运算并构造了矩阵的快速迭代算法,提高了挖掘效率,试验结果也验证了算法的高效性。     

双圈仙人掌图的零阶广义Randic指数的界

主要研究双圈仙人掌图零阶广义Randic指数的界.Ln表示连通的n阶双圈仙人掌图的集合.MnLn表示没有悬挂点且两圈由一条路相连的仙人掌图的集合,即n3=2,n2=n-2.Mn Ln表示两长为3的圈有唯一公共点,其余均为悬挂边,且所有悬挂边均与两圈公共点相连的仙人掌图集合,即nn-1=1,n2=4,n1=n-5.则当α0或α1时,图G在Mn中取得极小图,在Nn中取得极大图;当0α1时,图G在Nn中取得极小图,在Mn中取得极大图.     

冒泡排序图的条件容错哈密尔顿性

冒泡排序图是由凯莱图模型设计出来的重要的互连网络．容错性的研究对考察网络的可靠性是十分重要的．n维冒泡排序图Bn是正则对称图,若它有n!个顶点和（n-1）n!/2条边．设F是冒泡排序图Bn的失灵边集,且｜F｜≤2n-7,若冒泡排序图Bn的每个顶点都至少关联2条非失灵边,那么Bn-F中存在哈密尔顿圈．     

半群H_((n,m))的独立子半群

设T_n是有限集X_n={1, 2,…,n}上的全变换半群.对1≤m≤n-1,记X_m={1, 2,…,m}且X_(n-m)=X_n\X_m.令■则H_((n,m))和T_((n,m))都是全变换半群T_n的子半群,且H_((n,m))?T_((n,m)).设T是半群S的子半群,如果对任意α∈S,n∈N_+,由α~n∈T可推出α∈T,则称T为S的独立子半群.考虑半群H_((n,m))的独立子半群T,由于独立子半群T可表示为一些包含幂等元的子集的并集,通过分析T的幂等元集E(T)与半群H_((n,m))中元素的关系,根据其定义及半群的封闭性进行构造,对幂等元及幂等元的生成元作运算,发现:若T包含H_((n,m))(n-2)中的某些幂等元,则可推出奇异变换半群Sing_((n,m))必被包含于T的结论;若T包含H_((n,m))的顶端G_((n,m))的某些元素,可推出G_((n,m))必被包含于T的结论.由此,对E(T)分情况讨论,通过所得结论推出独立子半群的结构特征,进而获得H_((n,m))的独立子半群的完全分类.     

非负特征图的列表不完全染色的研究

每一个顶点u∈V(G),若任意给定k种颜色的列表,G都存在一个L-染色,使得G的每个顶点至多有d个邻接点与其染相同的颜色,则称图G为(k,彩*-可选的.文章证明了每个可以嵌入到非负特征曲面的图,若不包含4-圈和7-圈,G是(3,1)*-可选的.     

一个重构定理的推广

本文提出如下猜想:“给出P阶图G的P个主子图G_(19)G_2,…,G_(n-1),G_n,…,G_p,其中G_1,G_2,…,G_(n-1)中的V_1,V_2,…,V_n未标出,V_(n 1),V_(n 2),…,V_p标定,G_n,…,G_p中的点全不标号,则G可由G_1,G_2,…,G_(n-1),G_n…,G_p唯一地重构。”并且证明了:当n=3,4时,猜想为真。     

单圈图最小特征值的上界

设G 为n 阶简单图, n(G)为G 的最小特征值。本文证明了:若G 为n 阶单圈图, G＊ 为C3 的每个顶点分别与P k -1 , P k1-1 , P k2-1 的一个一度点相连而得的单圈图, 其中k k1 k 2 1 , k -k 2 1 , k +k 1 +k 2 = n , 则 n(G) n(G＊)等号成立当且仅当G≌G＊ 。     

关于特殊[a,b]-因子的度条件

设G=(V(G),E(G))是一个图,1≤a≤6是整数.G的一个支撑子图F称为G的一个[a,b]-因子,若对G中任意的点v∈V(G),有a≤dF(v)≤b.图G称为是[a,b]-覆盖图,若对G的每一条边,存在G的一个[a,b]-因子包含它.本文给出了一个图是[a,b]-覆盖图的度条件,推广了T.Nishimura等人得到的结果.     

联图p_m∨p_(2k+1)中保Wiener指数的树

Wiener指数是指一个连通图中所有顶点之间的距离之和.给定一个连通图G,若存在G中一棵子树T,使得W(G)=W(T),则称T为G的一棵保Wiener指数的树.给出了对于满足下列条件下的某类m+2k+1阶联图pm∨p2k+1中均有保Wiener指数的子树:m=t2+4t+8/3k3-k2+4/3k+1(t≥k2-1/2k)此结果蕴含了先前的一个结论.     

关于无爪图中哈密尔顿圈的一个注记

证明了具有Hourglass和Dumbbell性质的3-连通的无爪图是哈密尔顿圈.     

单圈图的关联能量

设单圈图G的顶点数和围长分别是n和g,Ugn表示由围长是g的连通单圈图构成的集合.通过比较系数的方法,在Ugn中找到关联能量最大（最小）时对应图的结构,同时也得到了一些关于类拉普拉斯能量的结果.     

准强边着色图的分类

如果图G已有一个合理边着色,使得图G中所有相邻顶点间的关联边着色集合相互不同,则这种边着色称为图G的准强边着色。具有准强边着色的图称为准强边着色图,并对准强边着色图给出一个分类。     

图K2n\E(K1,m)(n≥2)的点可区别边染色

图的一个正常边染色被称为点可区别边染色若任意两点的色集合不相等,其所得的最少颜色数称为点可区别边色数.应用平行线法研究了图K2n\E(K1,m)(n≥2)的点可区别边染色,并得到了其点可区别边色数,进一步验证了图的点可区别边染色猜想.     

P_m×P_n和P_m×C_n的邻强边染色

设G是阶数不小于3的简单连通图,G的κ-正常边染色称为是邻强的,如果对G任意相邻两顶点关联边的颜色构成的颜色集合不同,则κ中最小者称为是G的邻强边色数。本文研究了Pm×Pn和Pm×Cn的邻强边色数。     

判定超欧拉图的一个新方法

引入图的顶点的一种变换,使变换后的图顶点数不变,但边数减少;同时给出变换后的图与原图的超欧拉性的关系,从而得到判定超欧拉图的一个方法.该方法不仅可用于一般图的超欧拉性的判定,也可用于简化图的超欧拉性的判定.     

有r个悬挂点仙人掌图的零阶广义Randic指数的界

设G为一简单连通图,则G的零阶广义Randic指数定义为Rα0(G)=∑ν∈V(G)dα(ν),其中d(v)为顶点ν的度数,α为非0和1的实数.图G称之为仙人掌图,如果G的每一块要么是一条边,要么是一个圈.本文研究有r个悬挂点仙人掌图的零阶广义Randic指数的界.L(n,r)、G(n,r)、H(n,r)、M(n,r)、N(n,r)分别表示一类图.当α<0时,Rα0G)取得极大值当且仅当G∈M(n,r),Rα0取得极小值当且仅当G∈N(n,r);当0<α<1时,Rα0取得极大值当且仅当G∈N(n,r),Rα0取得极小值当且仅当G∈M(n,r);当α>1时,Rα0取得极大值当且仅当G∈G(n,r),Rα0取得极小值当且仅当G∈H(n,r).     

网络图在频率分配中的应用

如果图G有一个合理边着色,使得图G中任意两个相邻顶点间的关联边着色集合相互不同,则这种边着色称为图G的准强边着色.有一个准强边着色的图称为网络图(或准强边着色图).使图G有一个准强边着色的最小色数称为网络图(或准强边着色图)的准强边色数,它被记为χ′qs(G).讨论了网络图的分类问题和网络完全图的计数问题,提出并证明了下述网络图猜想(或准强边着色猜想):如果连通网络图有△(G)≥2,则网络图G的准强边色数有△(G)≤χ′qs(G)≤△(G)+3.     

关于曲面的列表点荫度定义与探讨

设为一图,用最少的颜色去着图,使得每种颜色的导出图是森林的所需色数,称为点荫度,记为。在这篇文章中,定义了列表点荫度,利用欧拉公式、面度和与点度和相等及亏格与顶点数的关系得到了亏格为的图的列表点荫度的上界及无三圈的亏格为的图的列表点荫度的上界。     

Chernoff脸谱图的计算程序设计

本文设计了一套脸谱图分析的BASIC应用程序。程序可以进行复杂的脸谱图计算、绘图和多种脸谱图试画选择,为多变量样本的脸谱图分析提供一种计算机辅助工具。