樹Tn與路Pm的笛卡爾積圖的交叉數(shù)

胡寧貝，魏首柳，白銀燕

(閩江學院 數(shù)學系，福建 福州 350121)

樹Tn與路Pm的笛卡爾積圖的交叉數(shù)

胡寧貝，魏首柳，白銀燕

(閩江學院 數(shù)學系，福建 福州 350121)

圖的交叉數(shù)是圖論中一個重要的研究課題.分別記含有n+1個頂點的樹和路為Tn與Pn，通過數(shù)學歸納法驗證并計算得到了笛卡爾積圖Tn×Pm的交叉數(shù)，其中n≤4.

笛卡爾積圖；好畫法；交叉數(shù)；樹；路

令G表示一個簡單連通圖.設V(G)和E(G)分別表示圖G的頂點集和邊集.G1×G2表示圖G1和G2的笛卡爾積圖，具體定義如下：V(G1×G2)=V(G1)×V(G2)，E(G1×G2)={(u1,u2)(v1,v2)|u1=v1且u2v2E(G2)或者u2=v2且u1v1E(G1)}.圖的交叉數(shù)問題是近代圖論中一個重要的研究課題.圖G的交叉數(shù)[1]指圖G在平面上所有好畫法中邊與邊之間相互交叉的最小頂點數(shù)，用cr(G)表示.其中，好畫法滿足：①相互交叉的任何兩條邊最多僅在頂點處交叉；②邊不能自身相交；③有相同端點的兩條邊不交叉；④任何3條邊都不可能交叉于同一頂點.最優(yōu)畫法指含最小交叉數(shù)的好畫法，用crD(G)表示圖G在好畫法時D的交叉數(shù).如果沒有特別說明，本研究涉及的一些概念和術語均來自文獻[2].

圖的交叉數(shù)的確定問題不僅在理論研究中具有非常重要的意義，而且在諸多實際問題中也有相應的研究背景，如超大規(guī)模集成電路VLSL中圈的布局[3-5]、離散幾何與計算幾何的研究及軟件開發(fā)過程中文檔的實體聯(lián)系圖(ER圖)的自動生成和工業(yè)上電子線路板設計中的布線問題等.

國內外學者對圖的交叉數(shù)的計算問題已經(jīng)做了大量的分析和研究,也得到了一些成果.1993年,Garey和Johnson[6]研究并證明了圖的交叉數(shù)問題是一個NP-完全問題.但是，由于其研究方法不統(tǒng)一，導致能夠被準確計算出交叉數(shù)的顯式表達式的圖類比較少，主要針對一些相對比較特殊的圖類(特別是笛卡爾積圖)的交叉數(shù)[7-12]，而對于樹與其他特殊圖類的笛卡爾積圖的交叉數(shù)的研究結果，目前集中在袁梓瀚[13]的博士論文和劉偉[14]的碩士論文中，柯小玲[15]也研究了不大于5個頂點的樹與圈的笛卡爾積圖的交叉數(shù)問題，本課題進一步研究不大于5個頂點的樹與路的笛卡爾積圖的結構并給出了其交叉數(shù)的顯式表達式.

1 預備知識

Tn表示含有n+1個頂點的樹;Sn表示含有n+1個頂點的星圖，即完全圖K1,n;Pn表示含有n+1個頂點的路; [x]表示不超過x的最大整數(shù)．

定義1 圖G和H為同構的，如果存在兩個一一映射θ∶V(G)→V(H)和φ∶E(G)→E(H)，使得ΦG(e)=uv當且僅當ΦH(φ(e))=θ(u)θ(v)，記為G≌H.

引理1 若H為圖G的子圖，則cr(H)≤cr(G).

引理2(Jordan曲線定理) 平面上的任一簡單閉曲線將平面唯一地分成3個彼此不相交的點集J， int(J)，ext(J)，則

(1)int(J)是一個有界區(qū)域，稱為J的內部；ext(J)是一個無界區(qū)域，稱為J的外部.

(2)int(J)和ext(J)都以J為邊界，如圖1所示．

引理3 cr(Pn×Pm)=0.

證明 圖2是Pn×Pm的一個好畫法，記為D，所以Pn×Pm顯然是平面圖，故有cr(Pn×Pm)=0.

引理4 cr(S3×Pm)=m-1，m≥1.

引理5 cr(S4×Pm)=2(m-1)，m≥1.

圖1 Jordan曲線圖Fig.1 Graph for Jordan curve

圖2 Pn×Pm的一個好畫法Fig.2 A good drawing of Pn×Pm

2 主要結果及其證明

眾所周知，任何一棵樹Tn(n≥3)在同構意義下均存在2個或2個以上的非同構圖.下面，對含有不多于5個頂點的樹Tn(n≤4)與路Pm的笛卡爾積圖進行研究，得到它們的交叉數(shù)表達式.

令T1和T2分別表示2階和3階的兩棵樹(見圖3)，則樹T1與路P1顯然同構，樹T2與路P2顯然也同構，根據(jù)引理3可以得到以下兩個結果：

定理1cr(T1×Pm)=0，m≥1；

定理2cr(T2×Pm)=0，m≥1.

顯然，含有4個頂點的樹T3在同構意義下存在2個非同構圖，分別記為T31和T32(見圖4).由于樹T31和T32分別與路P3和星圖S3同構，則根據(jù)引理3和引理4可以得到如下結果：

定理3cr(T31×Pm)=0，m≥1；

定理4cr(T32×Pm)=m-1，m≥1.

含有5個頂點的樹T4的3個非同構圖可用T41,T42,T43表示(見圖5)，則由于樹T41與路P4同構，樹T42與星圖S4同構，所以根據(jù)引理3、引理5和引理6可得到如下結果：

定理5cr(T41×Pm)=0，m≥1；

定理6cr(T42×Pm)=2(m-1)，m≥1.

圖3 2階樹T1與3階樹T2Fig.3 Trees with order 2 and 3

圖4 4階樹的2個非同構圖T31與T32Fig.4 Two non-isomorphic graphs of tree with order 4

圖5 5階樹的3個非同構圖Fig.5 Three non-isomorphic graphs of tree with 5 order

用數(shù)學歸納法證明笛卡爾積圖T43×Pm的交叉數(shù).為了更好地研究和得到歸納基礎，先證明以下幾個重要結果.

引理7 cr(T43×P1)=0.

證明T43×P1是一個平面圖(見圖6)，故有cr(T43×P1)=0.

引理8 cr(T43×P2)=1.

證明 因為圖7是T43×P2的其中一個好畫法，從而有cr(T43×P2)≤1.另一方面，如果能夠證明cr(T43×P2)≥1，則結論成立.

圖6 T43×P1的一個好畫法Fig.6 A good drawing of T43×P1

圖7 T43×P2的一個好畫法Fig.7 A good drawing of T43×P2

引理9 cr(T43×P3)=2.

證明 由T43×P3的一個好畫法(見圖8)可知，cr(T43×P3)≤2，只需要證明cr(T43×P3)≥2成立即可.選取笛卡爾積圖T43×P3的一個子圖H(見圖9)，根據(jù)引理1可得cr(T43×P3)≥cr(H).顯然，T43×P3的子圖H與S3×P3同構,又根據(jù)引理4可以得到cr(H)=cr(S3×P3)=2，所以cr(T43×P3)≥2，故有cr(T43×P3)=2.

圖8 T43×P3的一個好畫法Fig.8 A good drawing of T43×P3

圖9 T43×P3的子圖H的一個好畫法Fig.9 A good drawing of subgraph H of T43×P3

引理10 cr(T43×P4)=3.

證明 由T43×P4的一個好畫法(見圖10)可知cr(T43×P4)≤3，如果可以證明cr(T43×P4)≥3成立，則結論成立.設G表示笛卡爾積圖T43×P4的其中一個子圖(見圖11)，由引理1可得cr(T43×P4)≥cr(G).顯然，子圖G與S3×P4同構，由引理4可知cr(G)=cr(S3×P4)=3，所以cr(T43×P4)≥3，故有cr(T43×P4)=3.

圖10 T43×P4的一個好畫法Fig.10 A good drawing of T43×P4

圖11 T43×P4的子圖G的一個好畫法Fig.11 A good drawing of subgraph G of T43×P4

類似于引理9和引理10的證明方法和過程可得下面兩個結果，同時可以給出關于T43×Pm的交叉數(shù)的顯式表達式，即定理7.

引理11 cr(T43×P5)=4.

引理12 cr(T43×P6)=5.

證明 因為在笛卡爾積圖T43×Pm的好畫法D中，樹T43的每個拷貝T43i(1≤i≤m)自身都沒有交叉，所以可以得到以下2個斷言：

斷言1 樹T43的2個不同的拷貝T43i和T43j的邊顯然不能相互交叉.

定理7 cr(T43×Pm)=m-1，m≥1.

證明 (1)由引理7至引理12可得，當1≤m≤6時，cr(T43×Pm)=m-1顯然成立.

圖12 引理13的證明圖示Fig.12 An illustration of lemma 13

圖13 T43×Pk+1的一個好畫法Fig.13 A good drawing of T43×Pk+1

故命題得證,即對于m≥1均有cr(T43×Pm)=m-1成立．

[1] BONDY J A，MURTY U S R.Graph Theory with Applications[M].New York：Elsevier,1981.

[2] BENEKE L W，RINGEISEN R D.On the crossing numbers of products of cycles and graphs of order four[J].Journal of Graph Theory,1980(4):145-155.

[3] LEIGHTON F T.Complexity Issues in VLSL [M].Cambridge: The MIT Press,1983.

[4] LEIGHTON F T.New lower bound techniques for VLSL[J].Mathematical Systems Theory,1984(17):47-70.

[5] BHATT S N,LEIGHTON F T.A framework for solving VLSL graph layout problems [J].Journal of Computation for System Science，1984(28):300-343.

[6] GAREY M R，JOHSON D S.Crossing number is NP-complete[J].SIAM Journal on Algebraic and Discrete Methods，1983(4):312-316.

[7] 袁梓瀚，黃元秋，劉金旺.7階循環(huán)圖C(7,2)與Pn的笛卡爾積的交叉數(shù)[J].數(shù)學進展，2008，37(2)：245-253.

[9] 袁梓瀚，黃元秋.一個六階3-連通圖與P3的笛卡爾積的交叉數(shù)[J].數(shù)學理論與應用，2007，27(2)：49-51.

[10]周智勇，黃元秋.笛卡爾積圖K3.3×Pn的交叉數(shù)[J].湖南師范大學學報(自然科學版)，2007，30(1)：31-34.

[12]BOKAL D.On the crossing numbers of Cartesian products with paths[J].Journal of Combinatorial Theory(Series B),2007(87):381-384.

[13]袁梓瀚.關于循環(huán)圖及一些特殊圖與路、星、樹、圈的笛卡爾積的交叉數(shù)研究[D].長沙:湖南師范大學，2009.

[14]劉偉.部分聯(lián)圖及笛卡爾積交叉數(shù)的研究[D].長沙:湖南師范大學，2013.

[15]柯小玲.笛卡爾積圖Tn×Cm的交叉數(shù)[J].閩江學院學報，2010，31(2)：5-8.

On the crossing numbers of Cartesian products of treeTnwith pathPm

HU Ningbei, WEI Shouliu, BAI Yinyan

(DepartmentofMathematics,MinjiangUniversity,Fuzhou350121,China)

The enumeration problem of the crossing number in graphs is an important research subject. LetTmandPmbe a tree and a path withn+1 vertices, respectively. In this paper, we determine the crossing numbers of Cartesian product of circle graphPmwith some tree graphsTn(n≤4) by mathematical induction.

Cartesian product; good drawing; crossing number; tree; path

2017-02-20

福建省自然科學基金(2015J01589)；福建省大學生創(chuàng)新創(chuàng)業(yè)訓練項目(201510395050)

胡寧貝(1994-)，女，河南滑縣人，本科生，主要研究圖論及其應用.

魏首柳(1978-)，男，福建大田人，副教授，博士，主要研究圖論及其應用.E-mail:wslwillow@126.com.

O157.5

A

1674-330X(2017)02-0078-05