完美C-超图的一个充分条件

混合超图是含有两种超边的超图，一种称为D-超边，一种称为C-超边，它们的区别主要体现在着色要求上．在任一着色中，要求每一D-超边至少有两个点着不同的颜色，每一C-超边至少有两个点着相同的颜色．只含D-超边的超图称为D-超图，只含C-超边的超图称为C-超图．主要讨论了C-超图的完美性问题，给出了完美C-超图的一个充分条件．     

线性超树的边着色问题

文章主要讨论一类超图,使它具有边着色性质,即边色数等于最大度数△。通过对线性超树与其对偶超图、线图性质的分析,找出线性超树的边色数即,线性超树的边色数为q（H）=△。     

超图嵌入带权重圈的一个2-近似算法

超图嵌入带权圈(HEWC)问题就是把超图的超边以路的形式嵌入一个带权圈, 使得圈上任何带权连接边的最大阻塞最小。这个问题的一个简单形式是图嵌入带权圈(GEWC),即把普通图的边以路的形式嵌入 一个带权圈。HEWC问题第一次被归结为一个整数线性规划问题,并且利用LP的放松问题和有界启发得到一个近似解。 然后设计了一个非常简单有用的可以和LP近似算法得到一样好的近似解的线性时间近似算法。     

一种基于熵的超网络重叠社团检测算法

研究了超网络的社团划分问题。超网络是实际应用中的超图,而超图则是一种广义上的图,它的一条超边可以连接任意多个顶点。提出了一个基于熵的超网络社团检测算法,该算法是对Cha等人的算法的推广,能够检测出重叠社团。将这两种算法应用到了中国大陆图论科研合作超网络中,对结果进行了分析和比较,认为提出的算法是有效的。     

有限群的弱s-置换嵌入子群

群G的一个子群H称为在G中s-置换嵌入,如果对于任意的素数p||H|,H的Sylowp-子群也是G的某个s-置换子群的Sylowp p-子群.称群G的子群H在G中弱s-置换嵌入,如果存在群G的次正规子群T和包含在H中的G的一个s-置换嵌入子群Hse,使得G=HT且H∩T≤Hse.利用弱s-置换嵌入子群的概念,研究了超可解群的构造,获得了有限群为p-超可解的一些充分条件.     

一类限制树问题的复杂性及其近似算法

多层印刷线路板布线中如何减少金属导孔是一个重要问题。本文将这个问题化为在2—部超图G[S、V、E]中寻找一类限制树问题。证明了该问题为Np—Complete,并给出它的多项式时间heuristric算法。     

图的对偶带宽问题

图G的带宽问题是一般提法是：将图G嵌入于主图H，使得G的边的最大跨度达到最小，当图G表示一种冲突关系时，便提出如下的对偶问题；将图G嵌入于主图H，使得边的最小跨度达到最大，研究了对偶带宽问题的基本性质和计算复杂性。     

关于弱s-置换嵌入子群的几个定理

称群G的一个子群H在G中弱s-置换嵌入的,如果存在G的一个次正规子群T和包含在H中的G的一个s-置换嵌入子群Hse使得G=HT且H∩T≤Hse。利用弱s-置换嵌入子群的性质给出了p-幂零群和p-超可解的一些新刻画。     

关于有限群p超可解性的一些新判定

有限群G的一个子群H称为在G中是n嵌入的,如果存在G的一个正规子群T使得HT=HG且H∩T≤HsG,其中,HsG是包含在H中的G中的最大s拟正规子群.这里利用某些子群的n嵌入性质给出有限群为p超可解群的一些新的判定.     

关于K棵支撑树的2个问题

给定一个(有向)连通图G=(V，E)，寻找k棵支撑树(边可以重复)，满足树中的边在k棵树中出现的次数不超过其容量，考虑2个问题：①k棵支撑树的费用之和尽可能小；②k棵支撑树中费用最大的尽可能小,给出了问题①的一个最优算法，同时应用该算法，问题②是是近似的。     

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

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     

超密集6G 网络中的高效频谱资源共享方法

面对6G网络中用户密集化分布、频谱资源有限和分布式决策等挑战，提出了一种基于多维超图博弈的频谱资源共享方法。首先，根据6G网络太赫兹通信特点，设计了多维超图干扰模型，包括同频直接干扰、累计干扰和邻频干扰，通过降低多维干扰值以提升网络吞吐量。为实现分布式决策，将问题建模为超图博弈，并证明该博弈为势能博弈，至少存在一个纳什均衡点。然后，设计了基于同步最优响应的分布式频谱决策方法，求解频谱分配策略。仿真表明，所提的多维超图博弈实现了6G环境下分布式的频谱共享，与传统超图博弈方法相比，进一步降低了用户间的干扰水平，网络吞吐量大幅提升。     

Random Hypergraphs and Subset Systems

Suppose to toss an independent coin with equal probability of success and failure for each subset of [ n ] = { 1, 2 n }, and form the random hypergraph H（n） by taking as hyperedges the subsets with successful coin tosses. It is proved that H （n） is almost surely connected. By defining a graph G（S） according to a subset system S, it is shown that the intersecting problem is NP-complete.     

H.264视频压缩域水印嵌入位置的分析

视频水印技术按照水印与视频的结合形式,分为压缩域水印和原始视频水印。压缩域水印可以很好地利用视频序列在时间上的冗余,但嵌入水印信息量较小;原始视频水印技术没有充分利用视频序列时间冗余度,但嵌入水印的信息较多,耗费时间较多。HG算法可以不解码视频而快速嵌入水印信息,但嵌入容量有限。本文改进HG算法通过分析非关键帧运动矢量,选择关键帧嵌入位置,使得在压缩域嵌入水印时,水印嵌入速度和嵌入量有较大幅的改进。     

超图的奇圈横贯

1997年,C.Berge提出了图G奇圈横贯的定义,并用图G+K2研究了图G的奇圈横贯,最后得出结论,τ=n—-α(G+K2).将图G的奇圈横贯推广到超图H上,并引入新概念H+K2,得到超图H的两个顶点x和z之间有奇长链的充分条件.     

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

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

超图 的一种特殊类型的分解

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

极大欧拉生成子图边数的几个定理

利用收缩的方法研究了超欧拉图的欧拉生成子图的边数问题,得到了结果:若 1个超欧拉图的子图H最多差 1条边有 3棵边不交的生成树,如果把H收缩后的图满足Catlin猜想,则原图也满足Catlin猜想 .     

基于核方法的半监督超图顶点分类算法分析

分类学习算法的研究是计算机科学的研究热点,超图上顶点的分类问题作为一般图顶点分类问题的推广,被广泛应用于各种计算模型。对基于核方法的半监督超图顶点分类算法进行理论分析,给出算法的收敛性分析和广义界估计值。