闽江学院学报
閩江學院學報
민강학원학보
JOURNAL OF MINJIANG UNIVERSITY
2010年
2期
5-8
,共4页
笛卡尔积图%好画法%交叉数
笛卡爾積圖%好畫法%交扠數
적잡이적도%호화법%교차수
两个图G1和G2的笛卡尔积图G1 ×G2定义为如下的图:V(G1×G2)=V(G1)×V(G2),E(G×G2)={(u1,u2)(v1,v2)|u1=v1且u2v2 ∈E(G2),或者u2=v2且u1v1∈E(G1).图的交叉数是图论中的一个重要拓扑参数,而确定图的交叉数是一个完全NP-问题.本文确定了若干树Tn(n≤4)与圈Cm的笛卡尔积图的交叉数.
兩箇圖G1和G2的笛卡爾積圖G1 ×G2定義為如下的圖:V(G1×G2)=V(G1)×V(G2),E(G×G2)={(u1,u2)(v1,v2)|u1=v1且u2v2 ∈E(G2),或者u2=v2且u1v1∈E(G1).圖的交扠數是圖論中的一箇重要拓撲參數,而確定圖的交扠數是一箇完全NP-問題.本文確定瞭若榦樹Tn(n≤4)與圈Cm的笛卡爾積圖的交扠數.
량개도G1화G2적적잡이적도G1 ×G2정의위여하적도:V(G1×G2)=V(G1)×V(G2),E(G×G2)={(u1,u2)(v1,v2)|u1=v1차u2v2 ∈E(G2),혹자u2=v2차u1v1∈E(G1).도적교차수시도론중적일개중요탁복삼수,이학정도적교차수시일개완전NP-문제.본문학정료약간수Tn(n≤4)여권Cm적적잡이적도적교차수.
