超图的圈性

来源 :上海交通大学 | 被引量 : 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分解并行设计,同时研究了规划-迭代型多极边界元法的
学位
该文研究R中变分不等式与非线性互补问题的数值.变分不等式与非线性互补问题长期以来一直用于阐述和研究经济学、控制论、交通运输等领域中出现的各种平衡模型.近二十年来,已
黄骅港是国家跨世纪重点工程,是国家西煤东运的第2条大通道出海口。黄骅港自投产以来,已经累计运行8a,每年下水的煤炭达到8000万t。近年来,随着黄骅港设备的老化,逐渐出现了
系统族的研究是鲁棒控制问题的深入和发展,也是解决实际问题的需要.系统族的线性状态约束问题为研究系统族的动态行为提供了一条新的途径,它反映了系统内部状态的具体性质,在
该文主要研究密度函数,回归函数和方差函数小波估计的构造方法及其理论性质.主 要包含以下几部分:(1)给出了密度函数线性小波估计以及两个密度函数线性皮估计差的渐近正态性.
有效性的评价一直是管理科学研究的热点问题之一.通过对企业生产管理的有效性评价和分析,可以发现管理上存在的问题,找到管理效率损失的症结,使决策者能对企业的发展状况作出
随着计算机和通信网络的非常广泛应用,信息的安全越来越受到人们的重视。由于密码技术是保证信息安全性的关键技术,因此随着社会的进一步发展,密码技术将得到越来越广泛的应
史宁中,高巍(1998)首次研究了分组数据参数的单边估计与检验问题,他们在分组数 据的参数是两个并且有约束情况下,利用间接方法(参数约束轩化成概率约束)给出了参数的最大似然
该文在综述城市交通规划管理的基本过程的基础上,利用用户量优与系统最优的关系,探讨了系统最优分配算法及实际调控机制,提出了以路段惩罚通过用户费用最省出行达到系统时间