| 随机扰动有向图的泛圈性（英文） |
| |
| 引用本文： | 任泽林,侯新民.随机扰动有向图的泛圈性（英文）[J].中国科学技术大学学报,2022(5):13-18+71. |
| |
| 作者姓名： | 任泽林 侯新民 |
| |
| 作者单位： | 1. 中国科学技术大学网络空间学院;2. 中国科学技术大学数学科学学院吴文俊数学重点实验室 |
| |
| 基金项目： | supported by National Natural Science Foundation of China (12071453)；;the National Key R&D Program of China (2020YFA0713100)； |
| |
| 摘 要： | Dirac定理指如果n个顶点的图G最小度至少为n/2，则G包含一个哈密尔顿圈. Bohman等引入了随机扰动图模型并证明了对任意正常数α和最小度至少为αn的图H，存在一个仅依赖于α的常数C使得对任意p≥C/n H∪Gn,p是几乎渐进肯定哈密尔顿的。本文考虑了随机扰动有向图模型，证明了对任意α=ω{(logn/n)1/4}和d∈{1, 2}，一个最小度至少αn的n点有向图和随机d正则有向图是几乎渐进肯定泛圈的。更进一步，给出了一个在这种随机扰动有向图中构造任意长度有向圈的算法。
|
| 关 键 词： | 随机扰动图 泛圈 吸收方法 算法 |
|
|
