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

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

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

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

7人参与的一类超图存取结构的最优信息率

运用存取结构与连通超图之间的关系,将7人参与的一类存取结构转化为连通超图中顶点数为7的一类共94种超图存取结构,研究了最优信息率及其所对应的完善秘密共享方案的构造.运用超图理论及方法对其中80种超图存取结构最优信息率的精确值进行了计算,并给出达到此信息率的秘密共享方案的具体构造方法;对其余的14种超图存取结构运用λ-分解等方法给出最优信息率的上下界.证明了具有n个顶点且秩为r的超图,其超边数至少为(n-r)/(r-1)+1条,至多为Cr n条;并从理论上证明了满足一定条件的顶点数为n(4≤n≤9),超边数为4且秩为3的非理想超图的最优信息率为2/3.     

模糊超图的分解定理和表现定理

定义了模糊超图、模糊子超图、λ-截超图和超图套等概念,证明了模糊超图的分解定理和表现定理.     

线性超图的边着色问题

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

伪超图开关类的若干性质

本文首先给出了伪超图开关运算的定义,导出了 F(n)的等价开关类划分,然后研究了开关类的性质,主要有:两伪超图属于同一开关类的充要条件;任一开关类含有 K—致伪超图的必要条件;任一开关类含有 K—正则伪超图的充要条件;Aut(H)与 Aut(S(H))的群性质;两开关类的同构性;两同构开关类的对偶类的同构性;两同构开关类的补类的同构性等。     

关于超图圈分解的研究

现代科学技术的进步和计算机以及信息等相关学科的快速发展,使得离散数学中的组合设计、图论、超图、网络理论以及编码设计等领域的研究内容越来越丰富、充实,同时,提出了许多具有重要理论意义和应用前景的新问题.本文中我们用组合数学与数论的方法构造超图Kn^3所有边的一种划分方法,在此划分的基础上根据边与边之间连接的需要,定义超图的圈模型,进而给出n≠3k时超图Kn^3的不同长度的圈的分解,和n=3k时超图Kn^3-H（k,k）的不同长度的圈的分解,并用此方法进一步研究超图Kq^3（q为素数）的Hamilton圈分解.     

3-(v,K_4~((3))-e,λ)最小覆盖问题

考虑一种特殊类型的超图分解.证明了对任意的正整数v≥4和λ,存在具有[λv(v-1)(v-2)/18]个区组的MCλ(3,K_4~((3))-e,v),其边超越中至多含有两条边.     

超图的控制集

研究超图的控制集和完美控制集并给出超图的控制集和完美控制集存在的充分必要条件．     

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

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

具有固定匹配数的极值k-部k-一致超图的结构

设V1,V2,…,Vk为k个有限集,i∈{1,2,…,k},ni△=|Vi|,n△=min{n1,n2,…,nk}.H为一个以V1,V2,…,Vk为顶点类的k-部k-一致超图,v(H)表示H的匹配数,|H|表示H的边数.设t为一个给定的整数.首先证明:如果v(H)≤t,则|H|≤tn1n2…nk/n.当v(H)=t,|H|=tn1n2…nk/n时,确定了H的结构.     

一致超图与其补超图的全独立数间的关系

本文讨论一致超图H与其补超图H的全独立数间的关系，得到的主要结果是：DT(H) DT(H)≤[(r 1)n/r] 1。     

初探超图的遍历性

本文给出了超图的点连通度、边连通度的概念。定义了Ｅｕｌｅｒ超图、ｉ－型（ｉ＝１，２，３）Ｈａｍｉｌｔｏｎ超图及超图的Ｅｕｌｅｒ问题和Ｈａｍｉｌｔｏｎ问题。证明了超图的Ｅｕｌｅｒ问题，ｉ－型（ｉ＝１，２，３）Ｈａｍｉｌｔｏｎ问题均是ＮＰ－完备问题，类似于图的结果，分别给出了超图是Ｅｕｌｅｒ超图及Ｈａｍｉｔｌｏｎ超图的一个必要条件     

关于3部3一致超图的Ramsey数

利用Chernoff界给出完全3部3一致超图和3一致完全超图的Ramsey数r（Ka,r.n^（3）≥cn^2r＋1（log n）^-st。     

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

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

关于完备超图的C度h—超星（HS）分解

本文论证了超图可c度h-HS分解的存在性条件,同时,给出了超图K_n~3可4度3-HS分解存在的充要条件,部分地解决了文献〔3〕中遗留的问题。     

超图K(3)v的一种特殊类型的分解

超图H是一个二元组(V,E), 其中V是有限集, V中的元素称为顶点, E是V的有限非空子集族,E中的元素称为超边.在过去的四十多年里, 图论已被广泛认为是解决几何、数论、运筹学和优化等领域中各种组合问题非常有用的工具. 为了解决更多的组合问题, 把图的概念推广到超图是非常自然的事情.从组合设计的角度, 用组合设计的方法来研究超图. 本文考虑一种特殊类型的超图分解. 通过引入辅助设计, 建立递推构造的方法.证明了当且仅当v≡1,2,6(mod 8)并且v≥6时存在S(3,W(3)4,v).     

超图的最短路径算法

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

完全二部多重图λKm,n的K1,k^—因子分解

讨论了完全二部多重图λKm,n的K1,k-因子分解,给出λKm,n存在K1,pq^-因子分解的必要条件以及当λ＝p或q时,λKm,n存在K1,pq－因子分解的充分条件,其中p,q均是质数。     

4-一致超图Ramsey数的渐近下界

本文利用Lovász局部引理的Spencer形式和对称形式给出4-一致超图Ram-sey函数的渐近估计.证明了:对于任意取定的正整数l0,使得当n→∞时,有 R(4)(m1,nk-1)≥(c-o(1))(n3/logn)((m4)-1)/(m-4)特别地,Rk (4) (n)≥(1-oD(1)) (n →∞).对于任意取定的正整数s≥5和常数δ>0,α≥0,如果4-一致超图F和G的阶分别为s和t,且G的边数m(G)≥(δ-o(1))t4/(logt)α (t→∞),则存在c=c(s,δ, α)>0,使得R (4) (F,G)≥(c-o(1))(t3/(logt) 3α+1) (m(F)-1)/(s-4).