广义θ-图和广义梅花图φ的奇异性

利用奇异图的邻接矩阵行列式等于零的方法讨论广义θ-图和广义梅花图φ的奇异性,分别给出广义θ-图θ(a_(1),a_(2),…,a_(k))和广义梅花图φ(a_(1),a_(2),…,a_(k))是奇异图的充分必要条件,并计算这两类图中奇异图发生的概率值.

单圈图的D(2)-点和可区别全染色

图G的D(2)-点和可区别全染色是指在图G的一个正常全染色φ下,G中任意两个距离不超过2的顶点u,v,其色集合中所有颜色数之和互不相同.使得G有一个k-D(2)-点和可区别全染色的最小整数k,称为图G的D(2)-点和可区别全色数.文中应用组合零点定理和权转移方法刻画了单圈图的D(2)-点和可区别全染色,并得到其D(2)-点和可区别全色数.

一类本原双色有向图的指数界

对一类相对特殊的双色本原有向图给出了本原条件,结合圈矩阵给出了本原指数的上下界,并刻画了取得指数上下界时所对应的极图。

稀疏图的r-动态染色

通过分析极小反例的结构性质,运用权转移的方法,研究了对于mad(G)<14/5的稀疏图G的r-动态染色数,证明了对于满足mad(G)<14/5的图G,若r≥9,则χr(G)≤r+2.研究结果推广了稀疏图r-动态染色的已知结果.

基于最省刻度尺构造极小优美图的图论方法

[目的]利用最省刻度尺的已有研究成果研究极小优美图的构造方法.[方法]对任意正整数n≥2,在长度是n的无刻度直尺上最少刻多少个刻度,就能度量1-n的所有长度,这就是最省刻度的尺子问题.给定正整数n,存在m个整数组成的集合{a_(i)},满足0=a_(1)<a_(2)<…<a_(m)=n,使得任意整数s(0≤s≤n)均可表示成该集合中两个元素的差a_(j)-a_(i),则称{a_(i)}为n上的受限差基.根据极小优美图和受限差基的定义,将极小优美图问题等效为最省刻度尺问题进而得到极小优美图的构造方法.[结果]由n≥5时K n不是优美图和n≥1时图K 4+K n,n是优美图的结论,得到了边数是6至82的极小优美图顶点数的上下界;用构造方法给出了图K_(3)∨K 1,3,n-3 e,K_(3,n)∨K_(3-e)和K_(2,3,n)∨K_(3)-7e的优美标号,从而证明了这三类图都是优美图,并且当0≤n≤9时,K_(3)∨K_(1,3,,n)-3 e和K_(2,3,n)∨K_(3)-7e都是极小优美图,当0≤n≤8时,K_(3,n)∨K_(3-e)都是极小优美图,由此给出了29组最省刻度尺的刻度值.[结论]最省刻度尺可以为构造极小优美图提供新的研究思路.

Peterson图和图D_(m,n)的边PI指数

利用分析法和分类讨论法,给出Peterson图和D_(m,n)图的边PI指数计算公式,丰富了图的PI指数理论.

一类图在3个参数下取得极值的图

研究了n阶k-梅花图在最大根M 1(G)下取得极值的图,讨论了n阶k-梅花图的补图在匹配能量ME(G)和Hosoya指标Z(G)下取得极值的图.

边加权有限图的Weil-Riemann-Roch定理

Riemann-Roch定理是数学中的一个重要结论,并有了广泛的应用。在有限图和边加权有限图等图中也有对应的Riemann-Roch定理以及应用,但所有这些工作都有一个共同点,那就是它们都聚焦于在除子或和除子线性等价的线丛的情况下,也就是秩为1的情况。为了得到高维秩的情形,可以借助多重除子的术语来描述。本文利用还原群GLn的root datum的概念给出了边加权有限图上主GLn-丛——向量丛的定义,并用多重除子的术语来描述向量丛,进而给出了边加权有限图的Weil-Riemann-Roch定理以及证明,推广了GROSS A.ULIRSCH M.和ZAKHAROV D的结果。

不含相邻短圈平面图的全染色

基于权转移方法,研究一类平面图的全染色问题。结果表明,如果对于平面图G的每一个顶点v,都存在{3,4,5,6,7}中的两个整数i_(v)和j_(v),使得v不与相邻的i_(v)-圈和j_(v)-圈关联,则全染色猜想对图G成立。

非平衡符号双圈图的拉普拉斯谱半径的排序

研究了非平衡符号双圈图的第一到第六大的拉普拉斯特征值的分布规律,完善了现有结论中一些不准确的情况,推广了现有的结果,并给出了取得极值情况的图例。

无爪图的支撑k-端点树的存在性

树T中度为1的点称为叶子,叶子数目不超过k的树称为k-端点树.图中存在一个哈密尔顿路,说明图中存在恰好含有两个叶子的支撑树.自然就有了关于哈密尔顿路问题的一个推广:考虑图中至多有k个叶子的支撑树即支撑k-端点树的存在性问题.通过控制集参数,确定了连通无爪图中存在支撑k-端点树条件.

完全3-一致超图K_(41)^((3))的5-圈分解

超图是有限集合的子集系统,它与数据库有密切关系。从数据库理论来看,圈结构是超图理论中最本质、最基本的结构。超图的圈分解是超图理论中重要的研究内容之一。有研究者对超图的哈密尔顿圈、非哈密尔顿圈分解做了研究。利用超图的圈分解序列与其边划分序列二者之间的关联,对n阶完全3-一致超图存在5-圈分解的公开问题进行了研究,验证了n=41时公开问题成立。

双层耦合振子电网的弹性能力分析

基于简化的二阶耦合振子模型,考虑网络的权重特征,构建了双层耦合振子电网的物理模型,并从能量流的角度分析了电网面向不同属性的输电线失效时的网络弹性能力.以一个2层电网为研究对象进行数值模拟,结果表明,异质传输线失效时,网络弹性能力较弱;同质传输线失效时,网络弹性能力较强.

几类特殊树的无矛盾连通数与最小深度

在一个边着色图G中,如果一条路径上有一种颜色只出现一次,则称这条路为无矛盾的。如果图G的任意两点间都存在一条路径是无矛盾连通的,则称图G为无矛盾连通图。图的无矛盾连通数cfc(G)是指使G为无矛盾连通图所需的最小颜色数。树的深度是研究树的无矛盾连通数行之有效的研究方法。研究了几类特殊树的无矛盾连通数与最小深度,刻画了最小深度与无矛盾连通数相等的树。首先,证明了如果n阶树T满足Δ(T)≥n/2,则cfc(T)=D(T)=Δ(T);其次,研究几类特殊树的最小深度与无矛盾连通数并给出了它们的界;最后,在树的最大度和阶已知的情形下,利用最小深度与阶的关系给出最小深度与无矛盾连通数的值。

一类仙人掌图的星边染色

图G的星边染色是指G的一个正常边染色,使得G中任一长为4的路和长为4的圈均不是2-边染色的.图G的星边色数χ’_(st)(G)表示图G有星边染色的最小颜色数.仙人掌图是一个连通图使得每个块是圈或者边.利用数学归纳法得到了一类仙人掌图C_(n)·C_(m)(n≥3,m≥3)的星边色数,从而推广已知结果.

参照零模型的加权网络链路预测因素研究

基于零模型,文章研究了如何量化分析加权复杂网络中链路预测的影响因素。通过对1阶零模型、权重置乱零模型,结构置乱零模型在拓扑结构和权重相关性两个方面分别进行研究。以美国航空网络为实证网络,针对加权网络中的权重特性,分析不同权重连边的可预测性和对于链路预测的影响。结果表明,美国航空网中存在拓扑权重相关性,并且破环拓扑结构比破坏权重相关性对于链路预测的影响更大。

双蛛网周期双重三角格图链环分支数的计数

通过对平图实施不改变其链环分支数的无符号平图的三类Reidemeister变换,以及对平图实施粘合同一个面上不相邻的两个顶点的图变换,化大图为小图,从而获得双蛛网周期双重三角格图链环分支数的计数。

基于集合学习的超链接预测

超图链接预测作为图预测的重要研究方向之一,能够通过预测节点间的高阶相互作用解决许多实际问题。目前大多数链接预测研究多集中于成对关联关系的预测,而实际应用中链接关系的对象往往大于两个。因此,本文提出一种基于集合表示和transformer的链接预测模型。该模型通过对集合表示实现链接预测的无序性,并将传统的语言模型拓展应用于链接预测问题。模型首先将数据嵌入编码层对数据特征进行提取,然后使用池化机制对解码层进行解码,并引入评分函数对模型预测结果进行评估。实验表明,本文提出的模型可以有效利用网络结构特征,在6个不同规模的代谢网络数据集上的表现优于多个基准算法。

基于节点相似性的二阶链路预测方法

复杂网络中基于节点相似性的链路预测算法通常根据两个节点之间的相似度,预测节点对之间是否存在链路。提出基于节点相似性的二阶链路预测方法,判别节点对之间是否存在未连接的节点,并补全节点对之间的二阶链路。同时,提出二阶链路预测指标,计算已知节点与其他并不存在链路的节点之间的相似性,并构建二阶可达网络保留原始网络中的二阶链路信息。实验结果表明,该方法能够在真实的网络数据中找到节点对之间的缺失节点,并补全可能存在的二阶链路。不同的链路预测指标在4个不同网络中的性能表现有所不同,所有实验中的最佳精确率达83.7%。

识别高阶网络传播中最有影响力的节点

识别网络传播中最有影响力的节点是控制传播速度和范围的重要步骤,有助于加速有益信息扩散,抑制流行病、谣言和虚假信息的传播等.已有研究主要基于描述点对交互的低阶复杂网络.然而,现实中个体间的交互不仅发生在点对之间,也发生在3个及以上节点形成的群体中.群体交互可利用高阶网络来刻画,如单纯复形与超图.本文研究单纯复形上最有影响力的传播者识别方法.首先,提出单纯复形上易感-感染-恢复(SIR)微观马尔可夫链方程组,定量刻画单纯复形上的疾病传播动力学.接下来利用微观马尔可夫链方程组计算传播动力学中节点被感染的概率.基于网络结构与传播过程,定义节点的传播中心性,用于排序节点传播影响力.在两类合成单纯复形与4个真实单纯复形上的仿真结果表明,相比于现有高阶网络中心性和复杂网络中最优的中心性指标,本文提出的传播中心性能更准确地识别高阶网络中最有影响力的传播者.