参与者人数为9的一类连通超图存取结构的信息率

基于存取结构与连通超图之间的关系,给出了顶点数为9,秩为3,超边数为4和5的一共226种不同构的连通超图存取结构,进而估算了它们的最优信息率。本文首先证明了具有4条超边的一类超星可以用理想的秘密共享方案来实现,并证明了满足一定条件的顶点数为n(5≤n≤11),超边数为5且秩为3的连通超图其最优信息率的下界为2/3。运用超图的相关理论对其中的16种超图存取结构最优信息率的精确值进行了计算,对余下的210种超图存取结构进行了分类,并估算了这些超图存取结构最优信息率的界。     

对3条超边的超圈存取结构最优信息率的一点注记

将含有3条超边的超圈存取结构分为两类:一类是任意一条超边都没有属于自己的独立点集;另一类是至少存在一条超边有属于自己的独立点集。对第一类超圈存取结构,用Shamir方案构造了一个理想的秘密共享方案,从而证明了其最优信息率等于1;对第二类超圈存取结构用信息论和λ-分解方法证明了其最优信息率等于2/3。给出了参与者人数为6、7且含有3条超边共86种互不同构的超圈存取结构,并计算了其最优信息率。     

一种新型的可改进的量子秘密共享方案

一种新型的可改进的量子秘密共享方案是在A.C.A.Nascimento等人提出的一种改进的量子秘密共享方案(简称IQSS方案)的基础上提出的,新方案较IQSS方案可实现更多的量子存取结构。进一步地,在理论上证明了所有的超星量子存取结构均可由这一新型的量子秘密共享方案实现。作为应用,给出了参与者人数至多为4的所有最优限制量子存取结构共10个,其中9个可以用新方案实现。     

一类具有最佳连通性的超图

在产生一组跳变序列的基础上，构造了一类具有ｎ个顶点、ｎ条的ｒ－均匀超图。再通过分析基二截的连通度，证明了此超图具有最佳连通性。这类超图可直接应用于设计最佳容错的多总线计算机系统。     

具有最小连通点对图的C-超图的染色讨论

主要讨论C-超图的染色与点的点对图的连通性之间的关系,证明了对任意给定的不小于3的正整数n,都存在上色数为n且具有最小连通点对图的3一致C-超图.     

线性超图的边着色问题

设S是由边秩大于等于3的边导出的部分超图,q表示超图的边色数。本文给出了满足Δs=2,qs=3,这类线性无环超图边色数的上界。进一步得到了n个顶点的无环线性超图H,如果满足Δs≤3,qs≤3,则q(H)≤n。此外,还讨论了r阶射影平面的边色数q(H)=r2-r+1。     

可实现全部超星量子存取结构的量子秘密共享方案

为了实现更多的量子存取结构,通过对超星量子存取结构上部分授权子集分发非目标秘密量子态,提出了一种新型的量子秘密共享方案。与其他同类方案相比,该方案理论上可实现全部的超星量子存取结构,方案中各成员都获得量子备份,具备无条件安全性。     

C-完全一致混合超图不可着色的充要条件

混合超图H′=(X,Xl,mX-D0)(其中D0表示若干恰由X中m个元素组成的D-超边的集合)的着色与其顶点个数有着必然的联系,当顶点个数超过一定数量时,H′便不可着色.本论文给出并证明了这类超图不可正常着色的一个充要条件.这一结论也揭示了这类混合超图可正常着色时,其可拥有的最大顶点个数与它的恰由X中m个元素形成的D-超边的个数之间的关系.     

无圈超图的性质

根据无圈超图的定义,给出了严格-连通-匀齐无圈超图的一个判定条件以及它的顶点数和边数的关系式.     

超级边连通r一致超图的充分条件

若一个连通图的任一最小边割一定是某个顶点的关联边集,那么称该图是超级边连通的.对超级边连通图的研究,不仅有理论意义,而且在网络可靠性的分析中也有广泛应用.超图是图的一个自然推广.论文将超级边连通性的概念推广到超图,给出超级边连通一致超图的最小度条件,并用例子说明所给的条件是紧的.所得结果是无向图相关结果的推广.     

超图的最短路径算法

从超图的强同构引出保持超图顶点间超邻接性的点同构,定义超图的邻接矩阵和赋权超图的权矩阵,并在此基础上得到了求解超图任意顶点间最短路径和求解超图直径的推广Floyd算法.最后通过实例验证了算法的可行性,并与李春明在1994年得到的结果进行比较,得出算法的复杂度为O(n3),该算法是一个有效算法.     

三循环集生成交错群的一个充要条件

An表示n阶交错群,α是由An的某些三循环构成的集合,Hα是由α生成的一个3-均匀超图.证明了α是An的生成集当且仅当Hα是n阶连通超图.     

利用(k,n)-门限方案实现任意访问结构的新方法

使用整数规划，提出了一种利用(k，n)-门限方案实现任意访问结构的新方法．该方法具有如下优点：使用同一个(k，n)-门限方案分享秘密，每个秘密分享的参与者得到子秘密集合的一个子集；秘密分享方案的设计不依赖于特定的(k，n)-门限方案，可以使用任何(k，n)-门限方案实现任意的访问结构；对访问结构没有任何要求(如要求访问结构为图等)；对任意给定的访问结构Γ，该方法所得到的秘密分享方案的(平均)信息率是所有可以使用同一个(k，n)-门限方案实现Γ的秘密分享方案中(平均)信息率最大的．     

给定悬挂点数和谱半径最大的连通k一致超图的结构

设?是n阶且悬挂点数为r的连通k一致超图的集合,其中n-r=k-4.利用特征方程的方法,刻画了图类?中谱半径最大的k一致超图的结构.     

一类二次型的秩分布

摘要 设n为奇素数,F3n表示含有3n个元素的有限域.利用线性码和指数和的有关理论,确定了二次型Q(x)=Trn1(Υx10+δx6),Υ,δ∈F3n 的秩分布.作为一个附带结果,构造了一类线性码并证明了该线性码适宜于构造秘密共享方案.     

3一致超图中线性哈密顿圈的Ore条件（英文）

1960年,Ore证明了如下结果:如果一个n点图的任意两个独立点的度和不小于n,那么它包含一个哈密顿圈.将这个结果推广到3一致超图上,并得到一个近似最优的结果.     

四元超图的模型及其性质

提出了一种基于复杂网络理论的四元超图的模型。定义了基本的网络衡量值,研究了四元超图中顶点的度分布及额外度的分布,构建了随机四元超图的模型,并且探讨了巨大分支在四元超图中存在的条件。本研究可用于分析研究社会网络中一些大规模的复杂超网络的结构及其拓扑性质。     

一类极小k-连通图及一类正则连通图的构造

连通性问题是图论基本问题之一.关于2-连通图和3-连通图的构造已经令人满意地搞清楚了.但当 k≥4时,有关最小 k-连通图的结构,人们还知之甚少.本文给出了当 k≥4时的 k-连通图的构造,证明了所构图形为极小 k-连通图;另外还给出了一类 k-正则 k-连通图的构造,它是在顶点数相同时的最小 k-连通图.     

可并行存取的共享RAM设计方案

给出一种有广泛适应性的可并行存取的共享RAM设计方案.该方案由数据的无冲突存取存放方法及处理机(或处理单元)与共享RAM之间的互联网络结构两部分组成.详细分析和论证了该方法和该网络的主要特点和性能.并说明了该方案的实现方法与其他方案相比较的优点.     

冒泡排序图的超带性

图G的k-路集C(u,v)是连接G中顶点u和v的k条内点不交的路的集合.图G的k-路集C(u,v)是一个k*-路集如果连接顶点u和v的k条内点不交的路包含G中所有的顶点.一个二部图G是k*-带的若G中任意两个属于不同二划分集的顶点之间存在k*-路集.设κ(G)是图G的连通度.一个二部图是超带的若G是i*-带的,1≤i≤κ(G).n维冒泡排序图Bn是二部图,是n-1正则的,有n!个顶点.在本文中,首先证明了Bn是(n-1)*-带的,n≥5,然后得到n维冒泡排序图Bn(n≠3)是超带的.