关于超图圈分解的研究

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

关于完全二分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圈分解。     

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

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

超图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).     

均衡的完全3-部3-一致超图的单色放松路划分

目前对于k-一致超图的2-边染色的单色放松路、放松圈的划分问题的相关结论很少,并且已有的结论主要是对完全的k-一致超图进行了研究.本文首次研究了关于均衡的完全3-部3-一致超图的2-边染色的单色放松路的划分问题,为今后进一步研究一般的k-部k-一致超图的单色划分问题打下基础.     

圈区间超图相关性质的讨论

文章对圈区间超图的交簇、边着色、Helly性质、保形性质进行讨论,主要得出在k-一致圈区间超图中圈区间簇的一些结果。     

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

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

超图在树环中的嵌入问题

H为定义在树环G上的一个超图,将H的每条超边映射为G中不同的树,称为超边在G中的嵌入问题．超图在树环中的嵌入问题即为寻找H在G中的最优嵌入使得G中任一边被H所有超边的嵌入经过的最大次数最小．将超图嵌入圈(MCHEC)问题的算法简化可得EHTR问题的一个PTAS算法,且可证明EHTR问题为NP-完全的．     

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

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

具有最小连通点对图的C-超图的染色讨论

主要讨论C-超图的染色与点的点对图的连通性之间的关系,证明了对任意给定的不小于3的正整数n,都存在上色数为n且具有最小连通点对图的3一致C-超图.     

关于匹配数为1的极大2-均衡3-部3-图的结构

描述具有给定匹配数的极大k-一致超图的结构是一个尚未解决的问题.本研究充分利用完全2-均衡3-部3-图中所有互不相交的完美匹配,得到极图的边数,进而确定所有极图的结构.     

最大权匹配问题的闭环DNA算法

给出并证明了在DNA计算中处理实数问题的策略,即首先在误差限范围内用有理数集合代替实数集合;再取出与有理数集合一一对应的最小的整数集合.针对赋权匹配问题,给出了基于闭环DNA计算模型的赋权匹配问题算法.该算法首先按边进行三组编码并合成初始闭环DNA;再以相邻两条边为约束条件用删除实验获得所有匹配,并用电泳实验得到所有最大权匹配,最后用检测实验输出最优解.证明了算法的正确性,讨论了算法复杂度,并以一个例子说明了算法的有效性.     

对偶超图的保形性

给出超图H的对偶超图是保形的充要条件,对它的性质进行了探讨,同时对具有保形性的超图的边数进行了研究。     

基于改进经验模态分解的三维重建

针对传统经验模态分解(Empirical mode decomposition,EMD)在边缘易出现分解错误的问题,本文提出一种改进的经验模态分解方法.分别对条纹进行镜像延拓和Gerchberg外插迭代来实现边沿的拓展,有效抑制条纹边沿引起的模态分解错误,提高分解准确度.将改进的EMD分解方式应用于变形结构光条纹图的分析,能有效消除条纹中的背景分布,得到更好的三维面形重建效果.     

陈氏基本互补划分法的改进和发展

应用有向超图理论引入超边的分解与收缩概念，把解决二个无源网络级联问题的陈氏基本互补划分（ECP）法改进为更有效的分解－收缩对（DCP）法，发展为有向（正根）分解－收缩对（PDCP）法，用于解决二个有源网络级联问题，在此基础上，进一步发展为一般分解一收缩（GDC）法，用于解决多个有源网络互联网时求符号网络函数的问题。     

超图的可平面性算法

随着超图理论在实际问题中的深入应用,其平面性研究也更加具有意义.回顾了超图的一般理论,给出了超图的二部图概念,并在此基础上给出了超图的可平面性算法.该算法是多项式时间算法,是有效算法.     

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

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

中国建筑师问题与对偶问题的4着色

提出了中国建筑师问题,阐明了求解中国建筑师问题的基本思路。介绍了25个顶点、69个边、45个面的对偶图的顶点4着色的全过程。将对偶图分解成含2棵可以2着色的对偶树的森林,在以r、b两色为对偶树得到的顶点实施2着色,以y、g两色为对偶树得到的顶点实施2着色,从而实施对偶图顶点的4着色。阐述了对偶图的4着色关键是将对偶图分解出森林,提出了3个森林的分解方法,讨论了H路径的个数、森林的个数、对偶图的A区和B区划分方案、对偶图的顶点4着色方案数。解决了对偶图顶点的4着色问题,利用对偶图顶点4着色方法使Kempe四色猜想"证明"中的漏洞得到了弥补。将此种方法用于12面体、20面体、22面体、32面体的对偶图的4色问题,并取得了成功。