熊志坤，王廣富

（1.華東交通大學(xué)理學(xué)院，江西 南昌330013；2.東莞市第七高級(jí)中學(xué)，廣東 東莞523500；3.煙臺(tái)大學(xué)數(shù)學(xué)與信息科學(xué)學(xué)院，山東 煙臺(tái) 264005）

化學(xué)圖論早在18 世紀(jì)下半葉被引入[1]，在1758年Cullen 和Black 繪制的第一個(gè)化學(xué)分子的示例圖就代表了化學(xué)物質(zhì)之間的相互作用。 Cullen 用化學(xué)圖解釋分子之間的化學(xué)反應(yīng)，但可惜作為課堂筆記沒有發(fā)表[2]。 在接下來的19 世紀(jì)50 年代和60 年代，結(jié)構(gòu)理論[3]和化合價(jià)理論[4]逐漸成為化學(xué)圖論研究的主流。 在20 世紀(jì)30 年代，化學(xué)圖論發(fā)展還包括同分異構(gòu)體計(jì)數(shù)[5]、拓?fù)渲笜?biāo)[6-9]等關(guān)鍵領(lǐng)域。 在化學(xué)圖論中，常把原子看作一個(gè)頂點(diǎn)，原子之間的化學(xué)鍵看作一條邊。 只考慮分子圖中的碳原子，不考慮氫原子和復(fù)雜的化學(xué)鍵.拓?fù)渲笜?biāo)實(shí)際上就是考慮化學(xué)圖上頂點(diǎn)之間的距離，在化學(xué)圖上計(jì)算任意兩點(diǎn)之間的距離十分復(fù)雜。 而在超立方體中的兩點(diǎn)間距離就是Hamming 距離，可以極大地簡化拓?fù)渲笜?biāo)的計(jì)算[10]。Assouad 和Deza 證明了l1-圖是可以按距離成倍數(shù)嵌入某個(gè)超立方體的圖[11]。因此，研究圖的l1-嵌入具有重要意義。

能夠嵌入歐式平面使得不同邊只在頂點(diǎn)處相交的圖，稱為平面圖。 Deza 和Shtogrin[12]研究了平面上的若干化學(xué)分子圖的l1-嵌入性，例如：苯、萘、聯(lián)苯等可以l1-嵌入。 Deza 和Laurent[13]得到了一些可以l1-嵌入的圖類，例如：雞尾酒會(huì)圖，半立方體，皮特森圖等。 Deza 和Laurent[13]還得出2 個(gè)l1-圖通過1 個(gè)頂點(diǎn)相粘后得到的新圖也是l1-圖。 Deza 和Grishuklin[14]證明了每個(gè)平面上的l1-圖都可以2 規(guī)模地嵌入某個(gè)超立方體。 能夠等距離地嵌入某個(gè)超立方體的圖，稱為部分立方體。 Klavzar 和Gutman[15]證明了所有苯環(huán)系統(tǒng)都是部分立方體。 張和平和徐守軍[16]證明了帶冠狀的苯環(huán)系統(tǒng)都不是部分立方體。張和平和王廣富[17]研究了開口納米管的l1-嵌入性，在所有的開口納米管中只有三類退化的情況才是部分立方體。 王廣富和張和平[18]研究了莫比烏斯面上的六邊形堆砌圖中只有H2，2和H3，3是l1-圖，莫比烏斯面上的四邊形堆砌圖中只有Q1，2是l1-圖。王廣富和Shpectorov[19]證明了一般的莫比烏斯面上的四邊形堆砌圖包含唯一的非零倫圈，同時(shí)刻畫了可以l1-嵌入的莫比烏斯面上的四邊形堆砌圖的結(jié)構(gòu)特征。李晨陽和王廣富[20]證明了樹、單圈圖以及它們的線圖都是l1-圖。 王廣富、李晨陽和王鳳靈[21]得到了2 個(gè)l1-圖的門和圖還是l1-圖。

環(huán)己烷類圖上所有的點(diǎn)都是2 度或3 度，只有1 個(gè)4-邊形面， 其他面都是6-邊形。 Deza 和Shtogrin[12]證明了4-邊形上都是3 度點(diǎn)的環(huán)己烷類圖不是l1-圖。 本文對(duì)環(huán)己烷類圖4-邊形上點(diǎn)的度進(jìn)行分類：對(duì)于環(huán)己烷類圖4-邊形上只有2 個(gè)3 度點(diǎn)的情況，如果這2 個(gè)3 度點(diǎn)是相鄰的，則稱為第一型環(huán)己烷類圖； 如果這2 個(gè)3 度點(diǎn)是相對(duì)的，則稱為第二型環(huán)己烷類圖。如果環(huán)己烷類圖4-邊形上有3 個(gè)3 度點(diǎn)， 稱為第三型環(huán)己烷類圖.證明了第一型環(huán)己烷類圖是l1-圖，第二型和第三型環(huán)己烷類圖都不是l1-圖。

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

文中涉及的所有圖都是有限的、簡單的、沒有自環(huán)的連通圖。對(duì)于1 個(gè)圖G，用V（G）和V（G）分別表示圖G的頂點(diǎn)集和邊集。 2 個(gè)點(diǎn)u 和v 之間連邊，也稱u 和v 相鄰。 對(duì)于2 個(gè)圖H 和G，如果V（E）?V（G）且E（H）?E（G），那么稱圖H 是圖G 的子圖。如果V′?V（G）且E′是由圖G 上兩端點(diǎn)都在V′中邊所組成的邊集， 稱其為圖G 的由V′導(dǎo)出的子圖，記為G[V′]。 路是指1 個(gè)點(diǎn)不重復(fù)的點(diǎn)邊交錯(cuò)序列，通常用P 表示。 起點(diǎn)和終點(diǎn)重合的路稱為閉路，也叫做圈，通常用C 表示。設(shè)u 是圖G 上的任一頂點(diǎn)，所有與u 相關(guān)聯(lián)的點(diǎn)組成的集合稱為點(diǎn)u 的鄰域，記為N（u）。在N（u）中包含的頂點(diǎn)數(shù)稱為點(diǎn)u 的度。設(shè)u 和v 是V（G）中的2 個(gè)點(diǎn)，u 和v 之間最短路的長度稱為u 和v 之間的距離，用dG（u，v）表示。 在不引起歧義時(shí)，簡記為d（u，v）。 則（V（G），d）構(gòu)成1 個(gè)度量空間，稱為圖G 的伴隨度量空間。 如果圖G 的任意2 個(gè)點(diǎn)之間都存在1 條路，那么G 為連通圖。 對(duì)于H 圖上的任意2 個(gè)點(diǎn)u 和v 都有dG（u，v）=dH（u，v），那么圖H 是圖G 的等距離子圖。

n 維超立方體Qn的點(diǎn)集是由所有n 元有序數(shù)組a1a2…an組成，其中ai∈{1，0}，（1≤i≤n）。 于是Qn有2n個(gè)頂點(diǎn)，2 個(gè)頂點(diǎn)相鄰當(dāng)且僅當(dāng)它們對(duì)應(yīng)的n元有序數(shù)組恰有1 個(gè)位置的元素不同。

1 個(gè)圖G 稱為l1-圖（或l1-嵌入的），如果它的伴隨度量空間與l1-空間的某個(gè)子空間同構(gòu)。也就是說存在從（V（G），dG）到（X，d1）的1 個(gè)距離保持映射φ，對(duì)G 的任意2 個(gè)頂點(diǎn)x 和y，滿足dG（x，y）=d1（φ（x），φ（y））。 Assouad 和Deza[11]證明了1 個(gè)圖G 是l1-圖當(dāng)且僅當(dāng)存在2 個(gè)正整數(shù)λ 和n，圖G 可以λ倍地嵌入到某個(gè)超立方體Qn中。 即對(duì)任意的頂點(diǎn)x，y∈V（G），存在1 個(gè)映射φ：V（G）→V（Qn），滿足λdG（x，y）=dQn（φ（x），φ（y））。

2 個(gè)簡單圖G 和H 同構(gòu)，也就是說，它們的頂點(diǎn)集之間存在1 個(gè)雙射，使得對(duì)于圖G 的任意2 個(gè)點(diǎn)u 和v，存在圖H 中的2 個(gè)點(diǎn)x 和y 與之對(duì)應(yīng)，滿足u 和v 在圖G 中相鄰當(dāng)且僅當(dāng)x 和y 在圖H 中相鄰，記作G?H。

2 個(gè)圖G 和H 的卡式積圖G□H 的點(diǎn)集是V（G）×V（H），2 個(gè)頂點(diǎn)（u1，u2）和（v1，v2）相鄰要么u1=v1且u2和v2在圖H 中相鄰， 要么u2=v2且u1和v1在圖G 中相鄰。

1 個(gè)具有k 條邊的面，稱為k-邊形。至少包含1個(gè)邊界頂點(diǎn)的面，稱為邊界面。 反之，所有點(diǎn)都是內(nèi)點(diǎn)的面，稱為內(nèi)面。

定義1.1 單一4-邊形環(huán)己烷類分子圖是指嵌入到平面上的2 連通圖，其中恰有1 個(gè)四邊形面，其他都是六邊形面，四邊形面上的頂點(diǎn)度為2 或3，其余內(nèi)點(diǎn)度為3，邊界點(diǎn)度為2 或3。

下面引入幾個(gè)常用的定理來判斷圖的l1-嵌入性。定理1.2[13]如果2 個(gè)簡單連通圖G 和H 都是l1-圖，那么它們的卡式積圖G□H 也是l1-圖。

外可平面圖G 是指其存在一種嵌入歐式平面的方式，使得所有邊只在頂點(diǎn)處相交且所有頂點(diǎn)都在外平面上.常見的外可平面圖有：路，圈等。

定理1.3[14]任意一個(gè)外可平面圖都是可以l1-嵌入的。

對(duì)于l1-圖，有一個(gè)非常重要的必要條件是：定理1.4[22]對(duì)于1 個(gè)連通圖G，如果它是l1-圖，對(duì)于圖G 上任意5 個(gè)點(diǎn)x，y，a，b，c，那么dG一定滿足下面的5-邊形不等式：d（x，y）＋d（a，b）＋d（b，c）＋d（a，c）≤d（x，a）＋d（x，b）＋d（x，c）＋d（y，a）+d（y，b）＋d（y，c）。

從定理1.4 可以容易看出，若能夠在圖G 中找出5 個(gè)頂點(diǎn)，它們違反了5-邊形不等式，則說明這個(gè)圖不是l1-嵌入的。

2 單一4-邊形環(huán)己烷類分子圖的l1-嵌入性

單一4-邊形環(huán)己烷類分子圖上恰有1 個(gè)4-邊形，其上的頂點(diǎn)度為2 或3，本小節(jié)研究單一4-邊形環(huán)己烷類分子圖的l1-嵌入性， 下面對(duì)其4-邊形上頂點(diǎn)的度進(jìn)行分析。

定理2.1 單一4-邊形環(huán)己烷類分子圖的4-邊形上至少有2 個(gè)3 度點(diǎn)。

證明

1） 如果單一4-邊形環(huán)己烷類分子圖的4-邊形上都是2 度點(diǎn)，則該4-邊形是孤立的，單一4-邊形環(huán)己烷類分子圖上不存在從4-邊形到6-邊形的路，與圖的連通性相矛盾，故環(huán)己烷類圖的4-邊形上至少有1 個(gè)3 度點(diǎn)。

2） 如果單一4-邊形環(huán)己烷類分子圖的4-邊形上只有1 個(gè)3 度點(diǎn)，不妨記為u，如圖1 所示，則4-邊形上另外3 個(gè)頂點(diǎn)都是2 度點(diǎn)。 通過u 向外發(fā)出一條邊記為uu1， 要使得4-邊形上的邊被6-邊形覆蓋， 則由頂點(diǎn)u 出發(fā)的路經(jīng)過若干個(gè)點(diǎn)后必須回到4-邊形上異于u 的頂點(diǎn)。則與單一4-邊形環(huán)己烷類分子圖的4-邊形上只有1 個(gè)3 度點(diǎn)相矛盾，故單一4-邊形環(huán)己烷類分子圖的4-邊形上至少有2 個(gè)3 度點(diǎn)。

圖1 環(huán)己烷類圖的4-邊形上只有一個(gè)3 度點(diǎn)Fig.1 Only one 3-degree vertex on the 4-cycles of the cyclohexane graph

單一4-邊形環(huán)己烷類分子圖的4-邊形上至少有2 個(gè)3 度點(diǎn)， 那么其4-邊形有可能是2 個(gè)3 度點(diǎn)，這2 個(gè)3 度點(diǎn)有兩種位置關(guān)系，當(dāng)這2 個(gè)3 度點(diǎn)相鄰時(shí)，則稱其為第一型環(huán)己烷類圖，當(dāng)這2 個(gè)3度點(diǎn)相對(duì)時(shí)， 則稱其為第二型環(huán)己烷類圖；4-邊形上也可能有3 個(gè)3 度點(diǎn)， 當(dāng)4-邊形上有3 個(gè)3 度點(diǎn)， 稱其為第三型環(huán)己烷類圖；4-邊形上也可能4個(gè)都是3 度點(diǎn)。 下面開始證明當(dāng)4-邊形上有2 個(gè)相鄰3 度點(diǎn)的情況下，單一4-邊形環(huán)己烷類分子圖的l1-嵌入性。

引理2.2[12]如果單一4-邊形環(huán)己烷類分子圖的4-邊形上都是3 度點(diǎn)，那么該圖不是l1-圖。

定理2.3 第一型環(huán)己烷類圖是可以l1-嵌入的。

證明 設(shè)第一型環(huán)己烷類圖G 的4-邊形上任意2 個(gè)相鄰的3 度點(diǎn)為u 和v，如圖2 所示，4-邊形上與u 和v 相關(guān)聯(lián)的點(diǎn)分別記為a 和b。 通過u 和v分別向外發(fā)出1 條邊， 產(chǎn)生2 個(gè)點(diǎn)分別記為u1和v1，再把u1和v1連邊。得到由V′=（a，b，u，v，u1，v1）導(dǎo)出的子圖，記為G[V′]。 此時(shí)G[V′]上除了uv 以外的邊都被6-邊形auu1v1vba 所覆蓋一次。 通過u1和v1分別向外發(fā)出1 條邊，產(chǎn)生的2 個(gè)點(diǎn)分別記為u2和v2，再把u2和v2連邊。 如圖3 所示，得到由V（G0）={a，b，u，v，u1，v1，u2，v2}導(dǎo)出的子圖，記為G0。 此時(shí)圖G0上所有的邊可以被6-邊形auu1v1vba 和uu1u2v2v1vu 覆蓋1 次或2 次。在基圖G0上通過u2和v2分別向外發(fā)出1 條邊，產(chǎn)生2 個(gè)點(diǎn)分別記為u3和v3，再把u3和v3連邊，依次類推把un和vn連邊，得到第一型環(huán)己烷類圖G。 不難看出第一型環(huán)己烷類圖G 與梯子圖（如圖4 所示）同構(gòu)。 而梯子圖H=Pn+1□P2且由定理1.3 知任意路都是l1-圖，通過定理1.2知梯子圖H 是l1-圖， 故第一型環(huán)己烷類圖G 是可以l1-嵌入的。

圖2 第一型環(huán)己烷類圖GFig.2 The type I cyclohexane graph G

圖3 G 圖的導(dǎo)出子圖G0Fig.3 The induced subgraph G0 of the graph G

圖4 梯子圖HFig.4 The ladder graph H

此時(shí)，證明了當(dāng)單一4-邊形環(huán)己烷類分子圖的4-邊形上有2 個(gè)相鄰的3 度點(diǎn)時(shí)， 那么該圖是l1-圖。 下面證明4-邊形上有2 個(gè)相對(duì)的3 度點(diǎn)時(shí)，單一4-邊形環(huán)己烷類分子圖的l1-嵌入性。

定理2.4 第二型環(huán)己烷類圖不是l1-圖。

證明：設(shè)第二型環(huán)己烷類圖M 的4-邊形上任意2 個(gè)相對(duì)的3 度點(diǎn)為x 和y， 如圖5 所示4-邊形上剩下的2 個(gè)2 度點(diǎn)不妨記為a 和b。 通過x 和y 分別向外發(fā)出1 條邊， 產(chǎn)生的2 個(gè)點(diǎn)分別記為x1和y1，再由x1和y1分別向外發(fā)出兩條邊，產(chǎn)生2 個(gè)點(diǎn)記為c 和d。 如圖6 所示，得到由V（M0）＝{a，b，c，d，x，y，x1，y1}導(dǎo)出的子圖，記為M0。 此時(shí)，圖M0上所有的邊可以被6-邊形xx1cy1ybx 和xx1dy2yax 覆蓋1 次或2 次。 在圖M0上通過c 和d 分別向外發(fā)出1 條邊，產(chǎn)生的2 個(gè)點(diǎn)分別記為x2和y2，再由x2和y2分別向外發(fā)出2 條邊， 產(chǎn)生2 個(gè)點(diǎn)記為x3和y3，依次類推，得到第二型環(huán)己烷類圖M。 接下來考慮由V（H）＝{a，b，c，x，y，x1，y1}產(chǎn)生的導(dǎo)出子圖H，不難驗(yàn)證在圖H 中任取2 個(gè)點(diǎn)u 和v，都有dM（u，v）=dH（u，v）。 因此，圖H 是圖M 的等距離子圖。 如圖7所示，取圖H 上的5 個(gè)頂點(diǎn)x，y，a，b，c，易得d（x，y）＝2，d（a，b）＝2；d（a，c）=3，d（b，c）=3；而d（x，a）=1，d（x，b）=1，d（x，c）=2，d（y，a）=1，d（y，b）=1，d（y，c）=2。 則d（x，y）+d（a，b）+d（a，c）+d（b，c）=10，而d（x，a）+d（x，b）+d（x，c）+d（y，a）+d（y，b）+d（y，c）=8。

圖5 第二型環(huán)己烷類圖MFig.5 The type Ⅱcyclohexane graph M

圖6 圖M 的導(dǎo)出子圖M0Fig.6 The induced subgraph M0 of the graph M

圖7 圖M0 的導(dǎo)出子圖HFig.7 The induced subgraph H of the graph M0

即在第二型環(huán)己烷類圖M 上找到了5 個(gè)點(diǎn)x，y，a，b，c 違反5-邊形不等式，使得：d（x，y）+d（a，b）+d（a，c）+d（b，c）＞d（x，a）+d（x，b）+d（x，c）+d（y，a）+d（y，b）+d（y，c）。 由定理1.4 知第二型環(huán)己烷類圖M不是l1-圖。

此時(shí)，證明了當(dāng)單一4-邊形環(huán)己烷類分子圖的4-邊形上有2 個(gè)相對(duì)的3 度點(diǎn)時(shí)，那么該圖不是l1-圖，下面證明當(dāng)4-邊形上有3 個(gè)3 度點(diǎn)時(shí)，單一4-邊形環(huán)己烷類分子圖的l1-嵌入性。

定理2.5 第三型環(huán)己烷類圖不是l1-圖。

證明：設(shè)第三型環(huán)己烷類圖N 的4-邊形上唯一的2 度點(diǎn)為w，如圖8 所示，4-邊形上與w 相對(duì)的3 度點(diǎn)為y，4-邊形上剩下的兩個(gè)3 度點(diǎn)不妨設(shè)為u和v。 由u，v，y 3 個(gè)點(diǎn)分別向外發(fā)出1 條邊，產(chǎn)生的3 個(gè)點(diǎn)分別記為u1，v1和y1， 再由u1，v1和y1分別向外發(fā)出2 條邊， 產(chǎn)生同時(shí)與u1和v1相關(guān)聯(lián)的點(diǎn)記為z，與u1相關(guān)聯(lián)的點(diǎn)記為a，同時(shí)與y1和a 相關(guān)聯(lián)的點(diǎn)記為b，與v1相關(guān)聯(lián)的點(diǎn)記為d，同時(shí)與y1和d相關(guān)聯(lián)的點(diǎn)記為c。 此時(shí)，由V（N0）＝{a，b，c，d，u，v，w，y，z，u1，v1，y1}導(dǎo)出的子圖，記為N0。 如圖9 所示，圖N0上所有的邊可以被6- 邊形aby1yuu1a，cdv1vyy1c 和vv1zu1uwv 覆蓋1 次或2 次。接下來考慮由V（H）＝{u，v，w，y，z，u1，v1}產(chǎn)生導(dǎo)出的子圖H，不難驗(yàn)證在圖H 中任取2 個(gè)點(diǎn)m 和n, 都有dN（m，n）=dH（m，n）。 因此，圖H 是圖N 的等距離子圖。 如圖10 所示，取圖H 上的5 個(gè)頂點(diǎn)u，v，w，y，z，不難得到d（u，v）=2，d（w，y）＝2，d（w，z）＝3；d（y，z）=3，而d（u，y）=1，d（u，w）=1，d（u，z）=2，d（v，y）=1，d（v，w）=1，d（v，z）=2。 則d（u，v）+d（w，y）+d（w，c）+d（y，z）=10，而d（u，y）+d（u，w）+d（u，z）+d（v，y）+d（v，w）+d（v，z）=8。

圖8 第三型環(huán)己烷類圖NFig.8 The type Ⅲcyclohexane graph N

圖9 圖N 的導(dǎo)出子圖N0Fig.9 The induced subgraph N0 of the graph N

圖10 圖N0 的導(dǎo)出子圖HFig.10 The induced subgraph H of the graph N0

即在第三型環(huán)己烷類圖N 上找到了5 個(gè)點(diǎn)u，v，w，y，z 違反5-邊形不等式，使得：d（u，v）+d（w，y）+d（w，z）+d（y，z）＞d（u，y）+d（u，w）+d（u，z）+d（v，y）+d（v，w）+d（v，z）。由定理1.4 知第三型環(huán)己烷類圖N不是l1-圖。

到此，本文證明了單一4-邊形環(huán)己烷類分子圖的4-邊形上有2 個(gè)相鄰的3 度點(diǎn)時(shí)， 那么該圖是l1-圖；其4-邊形上有2 個(gè)相對(duì)的3 度點(diǎn)時(shí)，不是l1-圖；其4-邊形上有3 個(gè)3 度點(diǎn)時(shí)，也不是l1-圖。 即單一4-邊形環(huán)己烷類分子圖中，除了第一型環(huán)己烷類圖是l1-圖，其他的都不是l1-圖。