超图思想方法探讨

本文通过边染色、匹配与覆盖等典型专题探讨超图思想方法,并提出超图与区组设计之间的内在联系。     

Boole函数的仿射分类与3-(λ,k,2~n)设计的构作

开关理论中关于Boole函数仿射分类的研究已有十余年历史。M.A.Harrison利用Polya计数定理,原则上已数出了仿射类的类数,剩下的问题是弄清每个仿射类中所含元素的个数;另一方面,作为平衡不完全区组设计(BIB)的推广,t-设计的构作近来已成为试验设计中引人注意的课题。 本文以超图为工具,讨论了二元域F_2上的n维向量空间F_2~n中子集的超图同构与子     

超图的路和圈

超图是离散数学中最一般最复杂的结构 .无圈超图已被证明在数据库设计中非常有用 .从关系数据的结构出发 ,建立了关于超图的路、连通性和圈的新的公理系统 .该系统与特殊情形———图是符合的 .引入了虚圈和实圈的概念 ,这是一对相关联的概念 .虚圈在特殊情形———图中不存在 ,退化掉了 .定义了超图圈的相关性和独立性 ,给出了超图中最大独立实圈数目的计数公式 ,对特殊情形———图 ,这个公式就是Euler公式 .     

区组大小不等的主效应设计

区组设计被广泛应用在人类的各种探索试验中.以往的研究中,区组大小通常被假定是相等的,但时常与实际情形相悖.本文讨论了区组大小不等时的正交主效应设计,该类设计的处理主效应可以通过区组因子达到正交;同时讨论了相关的设计性质.最后,本文给出了若干构造方法,包括如何添加新的区组,以及如何叠加不同区组大小的设计.结果表明相应设计具有较为灵活的区组数、区组大小和因子数.     

基于超图的超网络研究综述

超网络是一般网络的一类自然推广。超网络的研究将会有助于理解“复杂系统之所以复杂”这一极其重要的问题。现实世界中,很多复杂的系统都可以用超网络描述。超网络分为基于网络的超网络与基于超图的超网络。本文主要介绍的是基于超图的超网络,首先对超图理论进行描述,然后对基于超图的超网络进行分析,接着提出了基于超图的超网络和多层超网络的转换及实例并提出了基于超图的超网络演化模型。本文最后对超网络今后的研究方向进行了探讨,其中,超网络的指标构建、动力学研究、链路预测、应用等方面还有待于深入研究。     

可分解不完全区组设计的若干结果

考虑某类可分解不完全区组设计——PRIB设计的均匀性. 在一离散偏差度量意义下, 得到了PRIB设计是最均匀设计的一个充要条件；证明了均匀PRIB设计是关联的；提出了用某类U-型设计构造这类区组设计的方法, 并给出了该类设计的一个存在性结果, 这一方法建立起了PRIB设计和U-型设计之间的一重要桥梁.     

组间平衡区组设计的性质及应用

区组设计的平衡性是对区组设计研究的重要概念,而组间平衡是其中基于重复次数概念的一种平衡性.探讨了组间平衡性的相关哲学概念和数学性质,并且从理论上证明了组间平衡区组设计的数学判定条件,并给出了计算机验证组间平衡性的方法.作为应用,在一般象数学的试验设计模型的基础上,证明了具有组间平衡性质的广义正交表,不但使得试验因子效应的估计无偏和方差最小,而且可以使得对试验中心值或者总体均值的估计无偏和方差最小,并且在区组试验数据较大时,其估计和区组大小的分解式基本无关,保证试验的数据分析结论具有再现性.     

混合效应模型的最优区组设计

本文对将驻点个数等于参数个数的混合效应模型做D-最优设计.以两种误差分布的组合为例做近似区组设计,然后给出精确区组设计的设计点位置及区组的权数的解析方程组,给出精确设计比近似设计好的条件.最后,给出数值结果及效率比较.     

超图的最优标号与特征值

研究超图的标号性质,首先利用拉普拉斯张量的第二小和最大特征值给出4一致超图的带宽和与割宽的上下界;其次构造与超图对应的简单图,通过其拉普拉斯矩阵的特征值给出超图带宽的下界.     

完全3- 一致超图的一类填充问题和覆盖问题

设Γ 是一些单t- 一致超图的集合. 填充设计P_λ(t, Γ, v) (或覆盖设计C_λ(t, Γ, v)) 是一个二元有序组(X, B), 其中X 是完全t- 一致超图λK_v^(t) 的顶点集, B 是λK_v^(t) 的一些子超图的集合, 要求每个子超图都同构于Γ 中的某一个超图, 每个子超图称为是一个区组, 并且满足λK_v^(t) 中的每一条边至多(或至少) 含在B 的λ 个区组中. 给定参数t, v, λ, Γ, 填充设计P_λ(t, Γ, v) 的最大可能的区组数称为填充数, 记为d_λ(t, Γ, v); 覆盖设计C_λ(t, Γ, v) 的最小可能的区组数称为覆盖数, 记为C_λ(t, Γ, v). 本文将确定Γ 中仅含超图K₄⁽³⁾ + e 时的d_λ(t, Γ, v) 和C_λ(t, Γ, v) 的精确值.     

一致超图谱半径界的改进结果

利用张量理论研究一致超图的谱半径.首先,利用对角相似张量与原张量同谱的性质,结合张量特征值的圆盘定理,给出谱半径的上界,这一上界严格小于最大度;其次,通过超图的度向量给出谱半径的下界.改进了超图谱半径上下界的原有结果.     

区组设计的矩阵象的计算及其应用北大核心

平衡区组设计是对传统平衡不完全区组设计(BIBD)、部分平衡不完全区组设计(PBIBD)和拉丁矩阵(或拉丁方)设计等区组设计的一种推广,这种区组设计比传统区组设计的多种平衡条件更弱,满足新平衡条件的平衡区组设计更多,也更容易构造,并且新构造出的区组设计仍然保持着原有各种形式的区组设计的各种平衡性,因而保持着在统计分析中的优良性质,从而可以和原来各种形式平衡区组设计一样用于试验设计和统计分析.研究新的一般区组设计的性质的一个重要工具是它们的矩阵象性质.首先对一般区组设计的矩阵象的定义和计算进行研究,这些矩阵象的运算性质和正交表的矩阵象运算性质基本类似,可以和正交表的矩阵象一样进行应用.正交表矩阵象的主要应用有两方面:正交表构造和数据分析研究.先把平衡区组设计的矩阵象应用于简单构造平衡区组设计.     

区组设计的矩阵象的计算及其应用

平衡区组设计是对传统平衡不完全区组设计(BIBD)、部分平衡不完全区组设计(PBIBD)和拉丁矩阵(或拉丁方)设计等区组设计的一种推广,这种区组设计比传统区组设计的多种平衡条件更弱,满足新平衡条件的平衡区组设计更多,也更容易构造,并且新构造出的区组设计仍然保持着原有各种形式的区组设计的各种平衡性,因而保持着在统计分析中的优良性质,从而可以和原来各种形式平衡区组设计一样用于试验设计和统计分析.研究新的一般区组设计的性质的一个重要工具是它们的矩阵象性质.首先对一般区组设计的矩阵象的定义和计算进行研究,这些矩阵象的运算性质和正交表的矩阵象运算性质基本类似,可以和正交表的矩阵象一样进行应用.正交表矩阵象的主要应用有两方面:正交表构造和数据分析研究.先把平衡区组设计的矩阵象应用于简单构造平衡区组设计.     

双因素裂区试验主区双向区组的设计与分析

本文给出了双因素裂区试验主区双向区组的设计与分析。这种设计在主区的两个方向上均采用随机区组设计或在主区的一个方向上采用随机区组设计，而在另一个方向上采用平衡不完全区组设计，用较少试验小区来控制主区两个方向上环境差异，减少主区的试验误差。     

超图对策的组内和组间位置值

本文研究超图对策位置值的分解问题。1988年,Meessen考虑到以图为合作结构的对策中边在合作中的作用,提出了一个重要的分配规则,这个规则被称为位置值(Position value)。本文通过考虑超图的每条超边不仅对关联于它的联盟中的参与者的收益产生影响,同时作为中介也对不关联于它的联盟中的参与者的收益产生间接影响,引入超图对策的组内Position值和组间Position值,以区分参与者收益的成分。本文首先给出这两类值的公理化刻画。其次,通过案例对超图对策的组内Position值和组间Position值进行了分析,并讨论了中介费用不合理情况下的改进分配方案。     

偶一致超图划分问题的若干结果

划分问题因其在多个领域的重要应用一直是图论的研究热点.利用张量的特征值研究超图的划分与奇划分,并结合边割的界给出最大奇割、平均最小割、等周数等超图拓扑指标的界.当k取2时,这些结果与对应的图谱理论中的经典结论一致,因此可视为这些结论在超图的推广.     

完全3-一致超图K_n~((3))的哈密顿圈分解

基于王建方和李东给出的超图哈密顿圈的定义和Katona-Kierstead给出的超图哈密顿链的定义,近年来,国内外学者对一致超图的哈密顿圈分解的研究有一系列结果.特别是Bailey-Stevens和Meszka-Rosa研究了完全3-一致超图K_n~((3))的哈密顿圈分解,得到了n=6k+1,6k+2(k=1,2,3,4,5)的哈密顿圈分解.本文在吉日木图提出的边划分方法的基础上继续研究,得到了完全3-一致超图K_n~((3))的哈密顿圈分解的算法,由此得到了n=6k+2,6k+4(k=1,2,3,4,5,6,7),n=6k+5(k=1,2,3,4,5,6)时的圈分解.这一结果将Meszka-Rosa关于K_n~((3))的哈密顿圈分解结果从n≤32提高到了n≤46(n≠43).     

稀疏超图:从理论到应用

给定正整数r、e和v,如果某个r-一致超图的任意e条不同边的并都包含至少v+1个顶点,则称其是(v, e)-自由(free)或者(v, e)-稀疏的.稀疏超图的概念由Brown、Erd?s和Sós在20世纪70年代提出.目前,研究给定顶点数的稀疏超图所能包含最大边数的上下界已成为极值组合学研究领域内的核心问题之一.该问题的研究方法丰富多变,涉及组合、概率、代数和数论等多个领域.本文介绍Brown、Erd?os和S′os关于稀疏超图的两个重要猜想的最新研究进展以及稀疏超图在极值组合与信息科学中的若干应用,包括朱烈曾作出突出贡献的完美哈希(Hash)矩阵、可分哈希矩阵等几类信息安全中的研究问题.此外,本文在某些参数下给出完美哈希矩阵与求并-自由(union-free)超图的新构造.本文的构造改进了相应问题的已知最优下界.     

超图的Alcuin数与其横贯数的关系

1000多年前, 英国著名学者Alcuin曾提出过一个古老的渡河问题, 即狼、羊和卷心菜的渡河问题. 最近, Prisner和Csorba等考虑了一般``冲突图"上的渡河问题. 将这一问题推广到超图$H=(V,\mathcal{E})$\,上, 考虑一类情况更一般的运输计划问题. 现在监管者 欲运输超图中的所有点\,(代表``items")\,渡河, 这里$V$的点子 形成超边 当且仅当这些点代表的``items"在无人监管的情况下不能留在一起. 超图$H$的Alcuin数是指超图$H$具有可行运输方案\,(即把$V$的点代表的``items" 全部运到河对岸)\,时船的最小容量. 给出了 $r$-一致完全二部超图和它的伴随超图, 以及$r$-一致超图的Alcuin数, 同时证明了判断$r$-一致超图是否为小船图是NP 困难的.     

平衡区组正交表的Kronecker积替换构造

平衡区组正交表是一种有别于传统正交表的新设计,这种设计保持了正交表对应区组设计的相遇平衡性、组间平衡性和正交平衡性,因此也具备了传统平衡不完全区组(BIB)设计、拉丁方设计、拉丁矩阵设计等数据分析的优良性质和相应的组合分析性质.性质保证了平衡区组正交表与正交表一样具有试验数据分析结论的再现性和试验中心的稳定性,是比广义正交表更加接近于正交表的一种试验设计表.通过对平衡区组正交表的构造方法进行研究,发现在已知平衡区组正交表的基础上,利用矩阵象理论,经过Kronecker积替换构造,可以构造许多新的平衡区组正交表.