山西大学学报（自然科学版）
山西大學學報（自然科學版）
산서대학학보（자연과학판）
JOURNAL OF SHANXI UNIVERSITY
2011年
1期
26-28
,共3页
路收缩%最小半度%度和%最少弧数%强(p,q)哈密尔顿
路收縮%最小半度%度和%最少弧數%彊(p,q)哈密爾頓
로수축%최소반도%도화%최소호수%강(p,q)합밀이돈
利用路收缩技术,证明了,如果有向图D满足下列条件中的任何一个,
(1)最小半度δ0(D)≥(n+p+q)/2;
(2)D.(p+q+1)强连通有向图,且d+(x)+d+(y)+d-(u)+d-(v)≥2(n+p+q)-1,这里,x,y是任意控制顶点对,u,v,口是任意被控制顶点对;
(3)D的孤数超过(n-1)1+q2+p;
那么D是强(p,q)哈密尔顿的.
利用路收縮技術,證明瞭,如果有嚮圖D滿足下列條件中的任何一箇,
(1)最小半度δ0(D)≥(n+p+q)/2;
(2)D.(p+q+1)彊連通有嚮圖,且d+(x)+d+(y)+d-(u)+d-(v)≥2(n+p+q)-1,這裏,x,y是任意控製頂點對,u,v,口是任意被控製頂點對;
(3)D的孤數超過(n-1)1+q2+p;
那麽D是彊(p,q)哈密爾頓的.
이용로수축기술,증명료,여과유향도D만족하렬조건중적임하일개,
(1)최소반도δ0(D)≥(n+p+q)/2;
(2)D.(p+q+1)강련통유향도,차d+(x)+d+(y)+d-(u)+d-(v)≥2(n+p+q)-1,저리,x,y시임의공제정점대,u,v,구시임의피공제정점대;
(3)D적고수초과(n-1)1+q2+p;
나요D시강(p,q)합밀이돈적.
