摘要
应用随机过程理论——马尔柯夫链,我们得到有向图存在Hamilton圈的必要条件。一个不可约有向图(?)=(V,E)具有周期d,|V|=n,V能分解成V=C_1+C_2+…+C_d且C_k,K=1,2,…,d,是不相交的非空循环类。如果|C_k|不等于n/d,那么有向图不是一个有向的Hamilton图。
Applying the stochastic processes theory-Markov Chain,We get a necessary con- dition about the existence of Hamilton circle in a directed graph.An irreducible di- rected graph =(V,E)has a period and|V|=n.V can be decomposed into V=C_1 +C_2+…+C_d,while C_k,k=1,2,…,d,are disjoint nonempty cyclic classes.If|C_k|is not equal to n/d,then directed graph is not a directed Hamilton graph.
出处
《天津理工学院学报》
1991年第1期38-40,共3页
Journal of Tianjin Institute of Technology
关键词
有向图
HAMILTON圈
马氏链
Hamilton circle of a directed graph
period
one-step transition probability of the Markov Chain
