胡寧貝，魏首柳，白銀燕

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

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

胡寧貝，魏首柳，白銀燕

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

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

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

令G表示一個(gè)簡(jiǎn)單連通圖.設(shè)V(G)和E(G)分別表示圖G的頂點(diǎn)集和邊集.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ù)問(wèn)題是近代圖論中一個(gè)重要的研究課題.圖G的交叉數(shù)[1]指圖G在平面上所有好畫法中邊與邊之間相互交叉的最小頂點(diǎn)數(shù)，用cr(G)表示.其中，好畫法滿足：①相互交叉的任何兩條邊最多僅在頂點(diǎn)處交叉；②邊不能自身相交；③有相同端點(diǎn)的兩條邊不交叉；④任何3條邊都不可能交叉于同一頂點(diǎn).最優(yōu)畫法指含最小交叉數(shù)的好畫法，用crD(G)表示圖G在好畫法時(shí)D的交叉數(shù).如果沒有特別說(shuō)明，本研究涉及的一些概念和術(shù)語(yǔ)均來(lái)自文獻(xiàn)[2].

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

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

1 預(yù)備知識(shí)

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

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

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

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

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

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

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

證明 圖2是Pn×Pm的一個(gè)好畫法，記為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的一個(gè)好畫法Fig.2 A good drawing of Pn×Pm

2 主要結(jié)果及其證明

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

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

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

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

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

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

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

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

定理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個(gè)非同構(gòu)圖T31與T32Fig.4 Two non-isomorphic graphs of tree with order 4

圖5 5階樹的3個(gè)非同構(gòu)圖Fig.5 Three non-isomorphic graphs of tree with 5 order

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

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

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

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

證明 因?yàn)閳D7是T43×P2的其中一個(gè)好畫法，從而有cr(T43×P2)≤1.另一方面，如果能夠證明cr(T43×P2)≥1，則結(jié)論成立.

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

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

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

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

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

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

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

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

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

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

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

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

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

證明 因?yàn)樵诘芽柗e圖T43×Pm的好畫法D中，樹T43的每個(gè)拷貝T43i(1≤i≤m)自身都沒有交叉，所以可以得到以下2個(gè)斷言：

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

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

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

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

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

故命題得證,即對(duì)于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ù)學(xué)進(jìn)展，2008，37(2)：245-253.

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

[10]周智勇，黃元秋.笛卡爾積圖K3.3×Pn的交叉數(shù)[J].湖南師范大學(xué)學(xué)報(bào)(自然科學(xué)版)，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]袁梓瀚.關(guān)于循環(huán)圖及一些特殊圖與路、星、樹、圈的笛卡爾積的交叉數(shù)研究[D].長(zhǎng)沙:湖南師范大學(xué)，2009.

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

[15]柯小玲.笛卡爾積圖Tn×Cm的交叉數(shù)[J].閩江學(xué)院學(xué)報(bào)，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

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

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

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

O157.5

A

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