超图的圈性

来源 :上海交通大学 | 被引量 : 0次 | 上传用户:eric900300
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
超图是在自然科学与数学中出现的一种重要数学结构。它在数据库结构、人工智能、生物数学、社会科学等领域都有广泛的应用。超图的圈性,或者非圈性是描述超图与树状结构的相似程度的一个重要的方法,而不同的衡量超图的树状相似程度的参数是控制大多数组合优化问题的复杂度的关键所在,并且已经引发了大量研究。  超图对应的相交图是研究超图的非圈性的重要工具。超图对应的相交图是以超图的超边集合为节点的普通图G=(E(H),L),满足:1.?e1,e2,∈E(H),e1, e2都由一条包含e1∩e2的路连接;2.|L|最小。超图对应的相交图的非圈性与超图的非圈性是相互对应的,并且简单超图对应的相交图的圈性值与超图的圈性值是相等的,所以研究超图对应的相交图的非圈性是研究超图的非圈性的一种有效途径。超图对应的相交图并不唯一,不同的相交图能反映超图的部分邻接关系,但如果我们能找到所有的相交图,那么我们就能找到超图H中所有超边的邻接关系。  本文首先介绍了Philippe在[17]中提到的α-圈的概念以及α-非圈的判别方法。研究了α-圈的基本性质,在Philippe的工作基础上,进一步得到:若简单超图是α-非圈的,则它对应的最小intergraph的边数为E(H)1,其中E(H)是该超图的超边数。接着,我们讨论了France Dacar在[10]中提出的非圈的定义,介绍了超图中的相交不变量和超图的圈性值以及相关的一些定理、性质,并且对超图的圈性值与超图的圈数做了一个比较,进一步得到:若超图不是α-非圈的,则它的圈性值大于等于1。之后,我们指出,Philippe提出的α-非圈与France Dacar提出的非圈的概念是等价的,以及最小intergraph和相交图也是等价的,并且利用相交图的构造定理,设计了一种构造任何超图的相交图的算法,最后通过Cayley公式,计算了任意简单超图对应的不同相交图的总数。
其他文献
论文研究了多极边界元法中GMRES(m)算法的并行设计,并且提出Householder约化法的QR分解,给出机群系统下Householder变换的QR分解并行设计,同时研究了规划-迭代型多极边界元法的
学位
随着计算机和通信网络的非常广泛应用,信息的安全越来越受到人们的重视。由于密码技术是保证信息安全性的关键技术,因此随着社会的进一步发展,密码技术将得到越来越广泛的应