数据库模式的非圈扩张

人们希望找到一个非圈数据库模式，使其与给定的数据库模式等价，基于数据库模式扩张的概念，本文给出一个求给定数据库模式的非圈扩张的算法．进一步我们得到数据库模式等价非圈扩张存在性的判定方法。     

从基本割集矩阵综合有向图的分解法

引入了有向基本割集矩阵Ｑｆ的二分解和分解树的概念，导出了Ｑｆ可实现的充分必要条件和所实现图Ｇ在有向二同构意义上的唯一性，应用超图理论解决了如何求Ｑｆ的二分解问题，提出了用分解法直接实现Ｑｆ的原理和算法，该原理可计算复杂度为Ｏ，ｖ和ｌ为Ｑｆ的树路子阵Ｑｆｐ的行数列数。     

超图嵌入图的最小拥挤问题展望

We consider the problem of embedding hyperedges of a hypergraph as paths in a cycle such that the maximum congestion,the maximum number of paths that use any single edge in a cycle,is minimized. The Minimum Congestion Hypergraph Embedding in a Cycle problem is known to be NP-hard and its graph version,the Minimum Congestion Graph Embedding in a Cycle,is solvable in polynomial time. Furthermore,for the graph problem,a polynomial time approxima-tion scheme for the weighted version is known. For the hypergraphmodel, several approximation algorithms with a ratio of two have been previously published. A recent works on this problem reduced the approximation ratio to 1.5. We present a polynomial time approximation scheme in this paper,settling the debate regarding if the problem is polynomial time approximable     

半监督超图正则拉普拉斯降维条件下分类算法广义界分析

研究超图上半监督正则拉普拉斯降维框架下分类算法的统计特征,通过特征空间上的映射算子说明降维后得到的向量较好地逼近原目标向量.利用矩阵迹的特性给出降维条件下分类算法广义界估计值.     

一类弱惟一染色B-超图的构造及其最小点数

定义了弱惟一染色B-超图,给出了一种构造弱惟一染色B-超图的方法,称为直角三角形构造法,并讨论了由直角三角形构造法得到的弱惟一染色B-超图的最小点数.     

关于诱导度偏差的指数型上尾估计

对诱导度偏差的指数型上尾估计被给出,它改进了Friedgut, Rödl与Schacht的相关结果。     

On Size of Unicycle Hypergraphs

1　IntroductionHypergraphsaresetsystemsoffinitesets.Theyarethemostgeneralstructureandplayanimportantroleinthediscretemathematics.Inrecentyears,thecomputerscientistsin-troducedtheconceptofacyclicandcyclichypergraphsandhaveprovedthattheyareim-portantinthedesignofdatabases(see[1,2]).In[3,4],themeet-semilatticeandausefulparameternamedcyclomaticnumberwasintroducedinstudyingthecyclicityofhyper-graphs.Lately,newsystemsofaxiomsforpaths,connectivityandcyclesofhypergraphsareconstructed.Withtheaidofthes…     

一种基于有向超图的规则库冗余及环路检测方法

当规则库的规模随着知识的更新而不断增大,规则库的维护就变得日益重要.其中,规则库的冗余和环路是影响规则库效率的重要问题.针对含有复合规则的产生式规则库,提出了一种基于有向超图的规则库表达方法,定义了其邻接矩阵和可达矩阵并推导出可达矩阵的计算方法.在此基础上给出了基于可达矩阵的冗余和环路检测算法.与已有的基于有向超图的算法相比,新算法图更简洁,矩阵规模更小,从而检测效率得到提高.实例证明该算法是有效可行的.     

超图的分数着色和分数团

超图是最一般最复杂的离散结构,是图的自然推广,但是图中的一些定义和结论并不是都能轻而易举地推广到超图中.给出超图分数着色和分数团的定义,这与特殊情形下的图的分数着色和分数团的定义是相容的,并将图的分数着色和分数团的一些结论在超图中进行了推广.     

基于拉普拉斯度的k-均匀超图的图熵极值

基于一般图中图熵的定义,定义了超图基于拉普拉斯度的图熵.将简单图的图熵的一些结论推广到k-均匀超图.利用一种移边操作,分别确定了在k-均匀超树、单圈k-均匀超图、双圈k-均匀超图和k-均匀化学超树中基于拉普拉斯度的图熵最大值和最小值,并确定了相应的极值图.