王晶

(長沙學(xué)院 數(shù)學(xué)與計(jì)算機(jī)科學(xué)系,湖南 長沙，410022)

最優(yōu)畫法的一個(gè)充分條件

王晶

(長沙學(xué)院 數(shù)學(xué)與計(jì)算機(jī)科學(xué)系,湖南 長沙，410022)

設(shè)D是圖G的一個(gè)好畫法，將G在畫法D下的交叉點(diǎn)看成新的頂點(diǎn)，這樣得到的圖稱為G在畫法D下的導(dǎo)出平圖，記為GD。即GD的頂點(diǎn)集V(GD)=V(G)∪{交叉點(diǎn)}，邊e由DV(GD)的片段組成，并且頂點(diǎn)v和邊e關(guān)聯(lián)的充分必要條件是v在邊e的閉包里。本文證明了：如果畫法D的導(dǎo)出平圖的每個(gè)面的度數(shù)都是3，則D是最優(yōu)畫法。

交叉數(shù)；好畫法；最優(yōu)畫法；導(dǎo)出平圖

圖的交叉數(shù)是圖的一個(gè)重要參數(shù)，研究圖的交叉數(shù)不僅具有重要理論意義,而且有較強(qiáng)的現(xiàn)實(shí)意義,如VLSI中的布線問題等。然而,一般地,確定圖的交叉數(shù)又是十分困難的,Garey和Johnson在文獻(xiàn)[1]中證明了確定圖的交叉數(shù)問題是一個(gè)NP-完全問題。很多學(xué)者進(jìn)行了這方面的研究，確定了完全圖[2]、完全二部圖[3]、 完全多部圖[4,5]、笛卡爾積圖[6-13]等一些重要圖類的交叉數(shù)。與此同時(shí)，我們注意到，刻畫最優(yōu)畫法性質(zhì)方面的研究工作較少。眾所周知，一個(gè)最優(yōu)畫法必定是好畫法，但是反過來卻不成立。自然地，我們會(huì)想，當(dāng)一個(gè)好畫法附加怎樣的條件后，才能成為一個(gè)最優(yōu)畫法？在本文中，結(jié)合歐拉公式，我們得到了一個(gè)既簡單又實(shí)用的結(jié)論。

本文未說明的概念和術(shù)語均同文獻(xiàn)[14]；且無特別說明時(shí)，所涉及的圖均指連通簡單圖。

1 幾個(gè)定義

定義1 一個(gè)圖G畫在平面上,若滿足如下條件:

(1)任何兩條相交叉的邊最多交叉一次；

(2)邊不能自身相交；

(3)有相同端點(diǎn)的兩條邊不交叉；

(4)沒有三條邊交叉于同一個(gè)點(diǎn)；

則稱此畫法為G的一個(gè)好畫法。

對(duì)于圖G的任意一個(gè)好畫法D，根據(jù)上述定義，顯然有cr(G)≤crD(G)。

定義2 如果圖G的某個(gè)好畫法D滿足crD(G)=cr(G)，則稱D為圖G的最優(yōu)畫法。

設(shè)D是圖G的一個(gè)好畫法，將G在畫法D下的交叉點(diǎn)看成新的頂點(diǎn)，這樣得到的圖稱為G在畫法D下的導(dǎo)出平圖，記為GD。即GD的頂點(diǎn)集V(GD)=V(G)∪{交叉點(diǎn)}，邊e由DV(GD)的片段組成，并且頂點(diǎn)v和邊e關(guān)聯(lián)的充分必要條件是v在邊e的閉包里。 從定義可以看出，GD是一個(gè)平圖。

一個(gè)平圖G把平面分成若干個(gè)連通區(qū)域，這些區(qū)域的閉包稱為G的面，面f的度是指和f關(guān)聯(lián)的邊的條數(shù)。 更進(jìn)一步的，令D是平圖G的一個(gè)畫法，若在畫法D下，G的每個(gè)面的度都是3，則稱D是圖G的三角剖分。

2 主要結(jié)論

在本文中，利用歐拉公式，我們證明了如下結(jié)論：

定理1 設(shè)D是圖G的一個(gè)好畫法，如果D是導(dǎo)出平圖GD的三角剖分，則D是圖G的最優(yōu)畫法。

證明 分別用ν(G)和ε(G)表示圖G的頂點(diǎn)數(shù)和邊數(shù)，并且記導(dǎo)出平圖GD的面的個(gè)數(shù)為φ(GD)。根據(jù)GD的定義，有

ν(GD)=v(G)+crD(G),ε(GD)=ε(G)+2crD(G)。

(1)

一方面，由于GD是平圖，根據(jù)歐拉公式，有

φ(GD)=ε(GD)-ν(GD)+2，

(2)

同時(shí)，由于D是GD的三角剖分，可以得到

3φ(GD)=2ε(GD)，

(3)

聯(lián)立(1)、(2)和(3)，可以得到

ε(G)-3ν(G)+6=crD(G)

(4)

對(duì)于圖G，有cr(G)≥ε(G)-3ν(G)+6，結(jié)合式(4)，有cr(G)≥crD(G)。

另一方面，我們知道cr(G)≤crD(G)，所以cr(G)=crD(G)，即D是圖G的最優(yōu)畫法。證畢。

圖1 圖G′及它的一個(gè)好畫法DFig.1 A graph G′ with its good drawing D

定理1給出了圖G的好畫法D為最優(yōu)畫法的充分條件,即要求其導(dǎo)出平圖的每個(gè)面的度為3。很自然地,我們會(huì)問,這個(gè)條件能不能放寬? 例如,在畫法D下,其導(dǎo)出平圖中只有一個(gè)面的度不是3,其余面的度均為3,畫法D是否還是最優(yōu)畫法? 答案是否定的! 我們舉例來說明：

圖2 圖G″Fig.2 A graph G″

圖2上圖所示的是圖G″及它的一個(gè)好畫法D,可以看到在導(dǎo)出平圖G″D中，有一個(gè)面的度為h(h≥4)，其余面的度都是3,且crD(G″)=2。圖2下圖所示的是圖G″及它的另一個(gè)畫法D′，而crD′(G″)=1。顯然crD(G″)>crD′(G″)，即D不是圖G″的最優(yōu)畫法!

盡管定理1中導(dǎo)出平圖GD有關(guān)面的度的條件不能放寬,但是我們可以用類似于定理1中的方法，得到圖G的交叉數(shù)cr(G)的下界。

定理2 設(shè)D是圖G的一個(gè)好畫法，如果其導(dǎo)出平圖GD中一個(gè)面的度為h(h≥4)，其余面的度都是3,則有cr(G)≥crD(G)+3-h。

[1]Garey M R,Johnson D S.Crossing number is NP-complete[J].SIAM J.Algebraic Discrete Methods,1983,4:312-316.

[2]Shengjun Pan,R.Bruce Richter.The crossing number of K11is 100[J]. J.Graph Theory,2007,56:128-134.

[3]Kleitman D J.The crossing number of K5,n[J].J.Comb.Theory,1970,9:315-323.

[4]Asano K.The crossing number of K1,3,nand K2,3,n[J].J.Graph Theory,1980,10: 1-8.

[5]Yuanqiu Huang,Tinglei Zhao.The crossing number of K1,4,n[J]. Discrete Mathematics,2008,308:1634-1638.

[6]Beineke L W,Ringeisen R D.On the crossing numbers of products of cycles and graphs of order four[J]. J.Graph Theory,1980,4:145-155.

[7]Klesc M.The crossing number of K2,3×C3[J]. Discrete Mathematics,2002,251: 109-117.

[8]Peng Y H, Yiew Y C.The crossing number of P(3,1)×Pn[J].Discrete Mathematics,2006,306(16):1941-1946.

[9]Zihan Yuan,Ling Tang,Yuanqiu Huang,et al.The Crossing Number of C(8,2)□Pn[J].Graphs and Combinatorics,2008,24(06):597-604.

[10]Tang Ling,Lv Shengxiang,Huang Yuanqiu.The crossing number of Cartesian products of complete bipartite graphs K2,mwith paths Pn[J]. Graphs and Combinatorics,2007,23:659-666.

[11]Lv Shengxiang,Huang Yuanqiu.On the crossing number of K5×Sn[J].Journal of Mathematical Research & Exposition,2008,28(03):445-459.

[12]Zhangdong Ouyang,Jing Wang,Yuanqiu Huang.The crossing number of the Cartesian product of paths with complete graphs[J]. Discrete Mathematics,2014,328:71-78.

[13]周志東，李龍.一類聯(lián)圖的交叉數(shù)[J].邵陽學(xué)院學(xué)報(bào)(自然科學(xué)版)，2016，13(3)：16-24.

[14]Bondy J A.Murty U S R. Graph Theory with Applications [M],London：the macmillan press Ltd,1976.

A sufficient condition of optimal drawing

WANG Jing

(Department of Mathematic and Computer Science,Changsha College,Changsha 410022,China)

LetDbe a good drawing of the graphG,the induced plane graph ofD,denoted byGD,is the graph with verticesV(GD)=V(G)∪{crossings},where the edges are the components ofDV(GD) andvis incident toeif and only ifvis in the closure ofe.In this paper,we prove that if each face of the induced plane graphGDofDis triangle,thenDis optimal.

crossing number;good drawing;optimal drawing;induced plane graph.

1672-7010(2016)04-0022-04

2016-06-02

湖南省自然科學(xué)基金資助項(xiàng)目(14JJ3138)

王晶(1981-)，女，湖南邵陽人，副教授，博士，從事圖論及其應(yīng)用研究;E-mail:wangjing1001@hotmail.com

O157.5

A