文献类型：期刊文章

作　　者：任泽林[1] 侯新民[1,2]

Zelin Ren;Xinmin Hou(School of Cyber Science and Technology,University of Science and Technology of China,Hefei 230022,China;Wu Wen-Tsun Key Laboratory of Mathematics,School of Mathematical Sciences,University of Science and Technology of China,Hefei 230026,China)

机构地区：[1]中国科学技术大学网络空间学院,安徽合肥230022 [2]中国科学技术大学数学科学学院吴文俊数学重点实验室,安徽合肥230026

出　　处：《中国科学技术大学学报》

基　　金：supported by National Natural Science Foundation of China (12071453);the National Key R&D Program of China (2020YFA0713100)。

年　　份：2022

卷　　号：52

期　　号：5

起止页码：11-16

语　　种：中文

收录情况：BDHX、BDHX2020、CAS、CSCD、CSCD_E2021_2022、IC、JST、RCCSE、SCOPUS、ZGKJHX、ZMATH、核心刊

摘　　要：Dirac定理指如果n个顶点的图G最小度至少为n/2,则G包含一个哈密尔顿圈. Bohman等引入了随机扰动图模型并证明了对任意正常数α和最小度至少为αn的图H,存在一个仅依赖于α的常数C使得对任意p≥C/n H∪G_(n,p)是几乎渐进肯定哈密尔顿的。本文考虑了随机扰动有向图模型,证明了对任意α=ω{(logn/n)^(1/4)}和d∈{1, 2},一个最小度至少αn的n点有向图和随机d正则有向图是几乎渐进肯定泛圈的。更进一步,给出了一个在这种随机扰动有向图中构造任意长度有向圈的算法。

关 键 词：随机扰动图  泛圈 吸收方法  算法  

分 类 号：O157.5[数学类]