系统科学与数学
繫統科學與數學
계통과학여수학
JOURNAL OF SYSTEMS SCIENCE AND MATHEMATICAL SCIENCES
2010年
7期
929-935
,共7页
交叉数%完全二部图%笛卡尔积图
交扠數%完全二部圖%笛卡爾積圖
교차수%완전이부도%적잡이적도
Garey和Johnson证明了确定图的交叉数是一个NP-完全问题.确定了笛卡尔积图K2,4×Sn的交叉数是Z(6,n)+4n.当m≥5,猜想cr(K2,m×Sn)=cr(K2,m,n)+n[m/2][m-1/2].
Garey和Johnson證明瞭確定圖的交扠數是一箇NP-完全問題.確定瞭笛卡爾積圖K2,4×Sn的交扠數是Z(6,n)+4n.噹m≥5,猜想cr(K2,m×Sn)=cr(K2,m,n)+n[m/2][m-1/2].
Garey화Johnson증명료학정도적교차수시일개NP-완전문제.학정료적잡이적도K2,4×Sn적교차수시Z(6,n)+4n.당m≥5,시상cr(K2,m×Sn)=cr(K2,m,n)+n[m/2][m-1/2].
