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

熊志坤，王廣富

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

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

能夠嵌入歐式平面使得不同邊只在頂點處相交的圖，稱為平面圖。 Deza 和Shtogrin[12]研究了平面上的若干化學(xué)分子圖的l1-嵌入性，例如：苯、萘、聯(lián)苯等可以l1-嵌入。 Deza 和Laurent[13]得到了一些可以l1-嵌入的圖類，例如：雞尾酒會圖，半立方體，皮特森圖等。 Deza 和Laurent[13]還得出2 個l1-圖通過1 個頂點相粘后得到的新圖也是l1-圖。 Deza 和Grishuklin[14]證明了每個平面上的l1-圖都可以2 規(guī)模地嵌入某個超立方體。 能夠等距離地嵌入某個超立方體的圖，稱為部分立方體。 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]證明了一般的莫比烏斯面上的四邊形堆砌圖包含唯一的非零倫圈，同時刻畫了可以l1-嵌入的莫比烏斯面上的四邊形堆砌圖的結(jié)構(gòu)特征。李晨陽和王廣富[20]證明了樹、單圈圖以及它們的線圖都是l1-圖。 王廣富、李晨陽和王鳳靈[21]得到了2 個l1-圖的門和圖還是l1-圖。

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

1 預(yù)備知識

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

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

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

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

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

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

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

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

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

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

對于l1-圖，有一個非常重要的必要條件是：定理1.4[22]對于1 個連通圖G，如果它是l1-圖，對于圖G 上任意5 個點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 個頂點，它們違反了5-邊形不等式，則說明這個圖不是l1-嵌入的。

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

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

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

證明

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

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

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

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

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

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

證明 設(shè)第一型環(huán)己烷類圖G 的4-邊形上任意2 個相鄰的3 度點為u 和v，如圖2 所示，4-邊形上與u 和v 相關(guān)聯(lián)的點分別記為a 和b。 通過u 和v分別向外發(fā)出1 條邊， 產(chǎn)生2 個點分別記為u1和v1，再把u1和v1連邊。得到由V′=（a，b，u，v，u1，v1）導(dǎo)出的子圖，記為G[V′]。 此時G[V′]上除了uv 以外的邊都被6-邊形auu1v1vba 所覆蓋一次。 通過u1和v1分別向外發(fā)出1 條邊，產(chǎn)生的2 個點分別記為u2和v2，再把u2和v2連邊。 如圖3 所示，得到由V（G0）={a，b，u，v，u1，v1，u2，v2}導(dǎo)出的子圖，記為G0。 此時圖G0上所有的邊可以被6-邊形auu1v1vba 和uu1u2v2v1vu 覆蓋1 次或2 次。在基圖G0上通過u2和v2分別向外發(fā)出1 條邊，產(chǎn)生2 個點分別記為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

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

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

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

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

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

證明：設(shè)第三型環(huán)己烷類圖N 的4-邊形上唯一的2 度點為w，如圖8 所示，4-邊形上與w 相對的3 度點為y，4-邊形上剩下的兩個3 度點不妨設(shè)為u和v。 由u，v，y 3 個點分別向外發(fā)出1 條邊，產(chǎn)生的3 個點分別記為u1，v1和y1， 再由u1，v1和y1分別向外發(fā)出2 條邊， 產(chǎn)生同時與u1和v1相關(guān)聯(lián)的點記為z，與u1相關(guān)聯(lián)的點記為a，同時與y1和a 相關(guān)聯(lián)的點記為b，與v1相關(guān)聯(lián)的點記為d，同時與y1和d相關(guān)聯(lián)的點記為c。 此時，由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，不難驗證在圖H 中任取2 個點m 和n, 都有dN（m，n）=dH（m，n）。 因此，圖H 是圖N 的等距離子圖。 如圖10 所示，取圖H 上的5 個頂點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 個點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 個相鄰的3 度點時， 那么該圖是l1-圖；其4-邊形上有2 個相對的3 度點時，不是l1-圖；其4-邊形上有3 個3 度點時，也不是l1-圖。 即單一4-邊形環(huán)己烷類分子圖中，除了第一型環(huán)己烷類圖是l1-圖，其他的都不是l1-圖。