贵州大学学报(自然科学版)
貴州大學學報(自然科學版)
귀주대학학보(자연과학판)
JOURNAL OF GUIZHOU UNIVERSITY(NATURAL SCIENCE)
2014年
1期
69-74
,共6页
随机图%k-匹配%相变
隨機圖%k-匹配%相變
수궤도%k-필배%상변
random graphs%k-matching%phase transition
随机图G(n,p)模型中有两个参数n和p,n表示图中的结点数,p表示图中任意两个不同结点之间独立生成边的概率.证明了随机图G(2n,p)中存在k-匹配的临界值为p=kn-2.实验分析了随机图G(2n,p)实例中10-匹配和25-匹配以及k=n-1匹配的相变.最后总结出临界函数与匹配的边数和结点数有关系.实验表明,理论与实验一致.
隨機圖G(n,p)模型中有兩箇參數n和p,n錶示圖中的結點數,p錶示圖中任意兩箇不同結點之間獨立生成邊的概率.證明瞭隨機圖G(2n,p)中存在k-匹配的臨界值為p=kn-2.實驗分析瞭隨機圖G(2n,p)實例中10-匹配和25-匹配以及k=n-1匹配的相變.最後總結齣臨界函數與匹配的邊數和結點數有關繫.實驗錶明,理論與實驗一緻.
수궤도G(n,p)모형중유량개삼수n화p,n표시도중적결점수,p표시도중임의량개불동결점지간독립생성변적개솔.증명료수궤도G(2n,p)중존재k-필배적림계치위p=kn-2.실험분석료수궤도G(2n,p)실례중10-필배화25-필배이급k=n-1필배적상변.최후총결출림계함수여필배적변수화결점수유관계.실험표명,이론여실험일치.