无圈超图的性质

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

无圈超图的一个充分必要条件

引入植树超图的概念,利用植树超图给出了一个超图是无圈超图的充分必要条件.建立了无圈超图与树的对应关系,表明信息科学家提出的无圈超图与数学家建立的无圈图有着密切的联系,所得结果进一步刻画了无圈超图概念中"无圈"的本质.

无圈超图规模的进一步研究

本文在王建方给出的严格(d)-连通k-匀齐无圈超图的规模的基础上,进一步研究n阶(d)-连通k-匀齐无圈超图的规模和非严格(d)-连通k-匀齐无圈超图的规模,并分别得到它们规模的上下界.

(k+1)秩匀称线性无圈超图的计数公式

得到了(k + 1)秩匀称线性无圈超图的计数显式, 并应用Pólya计数定理, 得到了(k + 1)秩非标号匀称线性超树H和(k + 1)秩非标号匀称线性无圈超图的生成函数.

无圈反向超图中Min-Max不相交反向超路算法设计

超图与反向超图是计算机网络和通信网络采用的一类重要的网络拓扑结构,为提高网络以及传输路径容错性,不相交路径设计与优化成为重要的研究课题。本文在有向无圈的反向超图中,当每一条反向超弧的尾节点数不超过给定常数λ时,对构建源点与汇点间两条点不相交反向超路(B超路)的Min-Max优化问题进行研究,使得两条反向超路中权值较大者的值能够达到全局最小。为解决该问题,首先构造并设计了基于原图的辅助图,该辅助图也是有向无圈的反向超图,并将原问题转化为辅助图的多权值函数B超路优化问题。从而设计了伪多项式算法得到该问题的最优解。基于该算法,进一步给出了近似算法的设计方案得到(1+ε)近似解,从而有效降低了计算复杂性。

无圈超图的计数

研究了标号超图的计数 ,得到 2个公式 :一个是关于严格 (D)_连通无圈齐超图的显式计数公式 ,另一个是关于线性无圈超图数目的递推公式 .

关于完全二分3—超图的Hamilton圈分解

超图是离散数学中最一般的结构 ,无圈超图已被证明在数据库设计中非常有用 ,笔者在文〔4〕所建立的超图的公理系统基础上 ,用巧妙而构造性方法分别给出了完全二分 3—超图H3 ( p ,p) (p是素数 )的Hamilton圈分解和完全二分 3—超图H3 (p ,p) (2 |p)的Hamilton圈分解 ,并提出猜想 :当 p为素数且p≡ 1(mod4)时 ,H4 ( p ,p)

超图的无圈分解问题

引入了超图的无圈分解的荫度的概念,研究了n阶r-完全超图Knr的无圈分解问题,给出了n阶r-完全超图Krn的荫度的一个下界T(Knr)≥(n!/r!(n-r+1)!).并提出猜想这里[x]表示x的整数部分.

超图的圈结构

超图是离散数学中最具有一般性的结构. 主要评述新的超图与传统超图在圈结构方面的本质不同, 介绍新的超图的圈结构的一些结果, 并提出一些可供进一步研究的问题.