張振坤，葉希瓊，龐留勇

(1.黃淮學(xué)院 河南 駐馬店 463000；2.鄭州電子信息工程學(xué)校 河南 鄭州 450007)

0 引言

本文所考慮的圖均為簡(jiǎn)單有限的連通圖，文中圖論概念均來源于文獻(xiàn)[1]。自20世紀(jì)80年代圖的標(biāo)號(hào)(又稱圖的嵌入)問題提出以來，因?yàn)閳D的割寬與微電子芯片電路布線中一個(gè)稱為“擁塞度(congestion) ”的基本物理參數(shù)密切相關(guān)[2-4]，所以有學(xué)者對(duì)圖的割寬問題展開深入研究。簡(jiǎn)明地，設(shè)G=(V(G),E(G))是一個(gè)具有n=|V(G)|個(gè)頂點(diǎn)的圖,Pn=x1x2…xn是一個(gè)具有n個(gè)頂點(diǎn)的路，其中V(G)={vi:1≤i≤n}為G的頂點(diǎn)集，E(G) ={vivj:1≤i,j≤n}為G的邊集，xj(1≤j≤n)是Pn的頂點(diǎn)，將G的每個(gè)頂點(diǎn)vi分別嵌入到路Pn的相應(yīng)一個(gè)頂點(diǎn)xj上(簡(jiǎn)稱G到Pn的一個(gè)嵌入)，使得Pn上每一對(duì)連續(xù)的頂點(diǎn)xj,xj+1之間重疊的邊數(shù)達(dá)到最小，這個(gè)最小邊數(shù)就稱為圖G的割寬，表示為c(G)。這里的圖G可以看成是一個(gè)微電子芯片的電路布線示意圖，vi表示芯片電路板上的節(jié)點(diǎn)，邊vivj表示連接節(jié)點(diǎn)vi,vj的電線。當(dāng)這個(gè)電路安裝在Pn上時(shí)，Pn上所有連續(xù)的頂點(diǎn)xj,xj+1之間重疊的電線根數(shù)的最大值就稱為這個(gè)嵌入的擁塞度(congestion)，這是一個(gè)度量電路性能的基本物理參數(shù)，是圖論中割寬問題的主要物理背景。同時(shí)，圖的割寬問題與超大規(guī)模集成電路、網(wǎng)絡(luò)通信等實(shí)際問題也有關(guān)聯(lián)[2,3,5,6]。理論上，圖的割寬還與其他一些圖論參數(shù)，如圖的帶寬、路寬、樹寬等緊密相關(guān)[3, 7, 8]。

對(duì)一般圖G來說，割寬的計(jì)算問題是NP-困難的[9], 即使G是最大度為3的平面圖[10]。因此，自圖的嵌入問題提出以來，確定在多項(xiàng)式時(shí)間內(nèi)割寬可計(jì)算的圖類及其結(jié)構(gòu)特征一直是該問題的主要研究?jī)?nèi)容。然而，由于該問題的難度較大，所以取得的科研成果相對(duì)較少。目前，僅有的研究成果包含以下幾個(gè)方面。算法方面，Chung和Makedon等人于1982年首先得到了計(jì)算最大度為d≥ 1的樹的割寬的O(n(logn)d-2)算法[11]。1985年，Yannakakis在文獻(xiàn)[12]中改進(jìn)了這各個(gè)結(jié)果，并給出了計(jì)算任意樹的割寬的多項(xiàng)式O(nlogn) 算法。其他的割寬可在多項(xiàng)式時(shí)間內(nèi)計(jì)算的特殊圖類有超立方體[13]、d-層樹的r-維網(wǎng)格[14]、循環(huán)毛蟲樹[15]、完全二部圖Km,n、格子圖Pm×Pn,Pm×Cn,Cm×Cn和一些乘積圖Km×Pn,Km×Kn,Pm?Pn[16]，其中Km、Cm分別表示具有m個(gè)頂點(diǎn)的完全圖和圈。k-割寬圖的結(jié)構(gòu)研究方面，文獻(xiàn)[17]得到了4-割寬圖的所有5個(gè)禁用子圖，文獻(xiàn)[18]給出了5-割寬樹的所有18個(gè)禁用子圖以及一些特殊的k-割寬樹的禁用子圖(k≥ 5), 文獻(xiàn)[19]刻畫了一般的k-割寬樹的可分解性質(zhì)(k≥4)。另外，Chung和Makedon 等人[11]于1982年給出了k-割寬樹的特殊結(jié)構(gòu)。本文將Chung和Makedon 等人的結(jié)果推進(jìn)到了一般圖的情形，證明了如下結(jié)果：對(duì)圖G任意度數(shù)大于或等于3的點(diǎn)v∈D≥3(G), 假設(shè)Vi(1 ≤i≤m)為G-v的一個(gè)連通分支的一個(gè)點(diǎn)集，子圖Hi=G[Vi∪{v}]。那么，c(G) ≤k當(dāng)且僅當(dāng)c(G(v;NHi(v),NHj(v)))≤k-1 (1 ≤i,j≤m)且v的鄰點(diǎn)集NG(v)中至少存在兩個(gè)點(diǎn)v1,v2使得vv1,vv2是G的割邊。利用這個(gè)性質(zhì)，本文研究了一類割寬為k的臨界圖的結(jié)構(gòu)。

1 基本知識(shí)

對(duì)整數(shù)n>0，設(shè)集合Sn={1, 2, …,n}，圖G= (V(G),E(G))，其中V(G) = {vi: 1 ≤i≤n}為G的頂點(diǎn)集，E(G) = {vivj: 1 ≤i,j≤n}為G的邊集，|V(G)| =n。Pn是一條具有n個(gè)頂點(diǎn)的路。

定義1.1圖G的點(diǎn)集V(G)到Sn的一個(gè)映射f:V(G) →Sn稱為圖G的一個(gè)標(biāo)號(hào)，也稱為由f導(dǎo)出的G到路Pn的一個(gè)嵌入。

定義1.2如果

c(G,f)=max1≤j

(1)

則稱c(G,f)為圖G關(guān)于標(biāo)號(hào)f的割寬(或擁塞度)。

定義1.3圖G的割寬是

c(G)=minfc(G,f),

(2)

這里的最小值指的是取遍所有標(biāo)號(hào)f的最小值。如果k=c(G,f), 則f以及由f導(dǎo)出的G到路Pn的一個(gè)嵌入稱為G的k-割寬嵌入。在式(2)中取得最小值的標(biāo)號(hào)f稱為最優(yōu)標(biāo)號(hào)。例如，圖1(a)是一個(gè)3-割寬圖G，圖1(b)中的標(biāo)號(hào)是G的一個(gè)最優(yōu)標(biāo)號(hào), 而圖1(c)中的標(biāo)號(hào)就不是G的一個(gè)最優(yōu)標(biāo)號(hào)。

圖1 一個(gè)3-割寬圖G和它的兩個(gè)標(biāo)號(hào)

(3)

對(duì)圖G和整數(shù)i≥ 1，令Di(G) = {v∈V(G) :dG(v) =i}，其中dG(v)表示點(diǎn)v∈V(G)的度數(shù)，D1(G)的任意點(diǎn)v稱為G的懸掛點(diǎn)。設(shè)e是G的一條邊，如果G-e包含至少兩個(gè)連通分支，則稱e是G的一條割邊。對(duì)任意v∈V(G),NG(v) = {u∈V(G) :uv∈E(G)}稱為v的鄰點(diǎn)集。對(duì)V'?V(G)且V′≠?, 則G[V′]稱為V′的導(dǎo)出子圖，且G[V(G)V′]=G-V′。如果V′={v}，我們將用G-v代替G-{v}。相似地，G-E′表示從G中刪除邊集E′后所得到的圖，且如果E′={e}則G-{e}將表示為G-e。如果v∈D2(G)，NG(v) = {v1,v2}且v1v2?E(G)，則稱G-v+v1v2為圖G的一個(gè)序列縮減，該圖表示在圖G-v中添加一條新邊v1v2。如果一個(gè)圖不能進(jìn)行任意序列縮減，則稱G是同胚極小的。如果兩個(gè)不相交的圖G和G′都是同一個(gè)圖H的序列縮減，則稱G和G′是同胚的。

定義1.4設(shè)圖G的割寬是k, 如果G滿足(1) 對(duì)G的任意子圖G′,c(G′)

根據(jù)定義，引理1.5是顯然的。

引理1.5設(shè)G和G′是兩個(gè)圖, 則下列兩個(gè)結(jié)論成立。

(1) 如果G′是G的一個(gè)子圖，則c(G′)≤c(G);

(2) 如果G′和G是同胚的，則c(G′)=c(G)。

作為極圖理論的重要內(nèi)容之一，k-割寬臨界圖在刻畫割寬為k的圖的結(jié)構(gòu)特征方面具有重要的理論意義。在第三節(jié)，本文刻畫了一類k-割寬臨界圖。

2 主要結(jié)果

首先,對(duì)于整數(shù)n≥ 1，令P是一條路，其點(diǎn)集V(P) =Sn，且對(duì)任意1 ≤i

如果e∈E(G), 則c(G-e) ≤c(G)。

(4)

定義2.1(i) 對(duì)整數(shù)r≥ 1，設(shè)v0是G的度數(shù)dG(v0) >r的一個(gè)頂點(diǎn)，v1,v2, …,vr∈NG(v0)， 則稱G(v0;v1,v2, …,vr)為G-{v1,v2, …,vr}的一個(gè)包含v0但不包含點(diǎn)v1,v2, …,vr的連通分支(見例子圖2(a))。

圖2 定義2.1(i)的例子和定義3.1(ii)的示例圖

(ii) 設(shè)|E(G)| ≥ 2, 則稱M(G) = {G-e:e是G的一條懸掛邊，或e∈E(Ct)}為G的所有不包含孤立點(diǎn)的極大真子圖的集合,其中Ct表示G的長(zhǎng)度為t(t≥3)的一個(gè)圈(見公式(4))。

引理2.2設(shè)f是G的一個(gè)最優(yōu)標(biāo)號(hào),f(x) = 1,f(y) = |V(G)|,Px,y是在f下連接x,y的一條路。如果存在某個(gè)i0,c(Hi0)=β,且對(duì)任意v∈Vi0,v?V(Px,y)和f(v)≠1,|V(G)|，則c(G)≥β+1。

證明:因?yàn)閷?duì)任意點(diǎn)v?Vi0,v∈/V(Px,y)，所以x,y?Vi0。同樣地，由Hi0是G的一個(gè)連通分支知，對(duì)任意點(diǎn)u∈V(Px,y) {x,y},u?Vi0。 這樣，V(Px,y) ∩Vi0= ?, 并且無論v0是否屬于V(Px,y),Px,y在f下完全越過Hi0。因此，c(G)≥c(Hi0)+1=β+1。

引理2.3設(shè)v1,v2∈NG(v0),v0v1和v0v2是G的割邊，c(G[V1]) ≤k-1,c(G[V2]) ≤k-1，c(G(v0;v1,v2))≤k-1,則c(G)≤k。

定理2.4對(duì)任意v∈D≥3(G), 設(shè)Vi(1 ≤i≤m)是G-v的一個(gè)連通分支的頂點(diǎn)集，Hi=G[Vi∪ {v}]，則下列論斷是等價(jià)的。

(i)c(G) ≤k；

(ii) 對(duì)任意1 ≤i,j≤m，c(G(v;NHi(v),NHj(v)))≤k-1, 并且NG(v)中至少存在兩個(gè)點(diǎn)v1,v2使得vv1,vv2是G的割邊。

證明:(?) 反證法。假設(shè)(i)成立但是G中存在至少一個(gè)點(diǎn)v′∈D≥3(G)使得(ii)不成立，也即是說,對(duì)任意H′i=G[V′i∪{v′}],H′j=G[V′j∪{v′}],c(G(v′;NHi′(v′),NHj′(v′)))>k-1,其中V′i,V′j分別為G-v′的兩個(gè)連通分支的頂點(diǎn)集。設(shè)f:V(G)→{1,2,…,n}是G的一個(gè)標(biāo)號(hào)，c(G,f) =k，并令x,y∈V(G)，f(x) = 1,f(y) =n,P是在標(biāo)號(hào)f下連接x和y的一條路。我們考慮兩種情形。

情形1：v′∈V(P)。

情形1.1：v′?{x,y}。根據(jù)假設(shè)，令v′1,v′2∈NG(v′)∩V(P)，NH′i(v′)={v′1},和NH′j(v′)={v′2}。也即是說，i=1,j=2且v′v′1,v′v′2是G的割邊。則由已知，G(v′;NH′1(v′),NH′2(v′))=G(v′;v′1,v′2)，G(v′;NH′1(v′))=G(v′;v′1),G(v′;NH′2(v′))=G(v′;v′2),且c(G(v′;v′1,v′2))>k-1。由于v′是P的內(nèi)點(diǎn)，且v′1,v′2∈NG(v′),我們可設(shè)f(v′1)=min{f(v):v∈V(G(v′;v′1,v′2))}-1和f(v′2)=max{f(v):v∈V(G(v′;v′1,v′2))}+1。這樣，如圖3(a)所示，P=x…v′1v′v′2…y,且在f下P完全越過圖G(v′;v′1,v′2)。 因此，由引理2.2，k=c(G,f)≥c(G)≥c(G(v′;v′1,v′2))+1,矛盾。同樣地，如果v′1,v′2有一個(gè)屬于V(P)或者v′1,v′2均不屬于V(P)，我們?nèi)匀豢梢缘玫酵瑯拥拿?。事?shí)上，如果v′1∈V(P),v′2?V(P), 則P完全越過子圖G(v′;v′2),進(jìn)而由于G(v′;v′1,v′2)?G(v′;v′2),P完全越過圖G(v′;v′1,v′2)(見圖3(a))中的路P=x…v′1v′…y′)。對(duì)于v′1?V(P),v′2?V(P)的情形，令x∈V(Gi)和y∈V(Gj),這里i,j?{1,2}。則我們可以看到P完全越過G(v′;NH′i(v′),NH′j(v′)),也是一個(gè)矛盾。

圖3 定理2.4的圖示

情形1.2v′∈{x,y}, 比如，v′=y。與情形1.1相似，令v′1∈NG(v′)∩V(P),f(v′1)=min{f(v):v∈V(G(v′;v′1))}-1。則由f(v′)=f(y)=n, 路P在標(biāo)號(hào)f下也完全越過G(v′;v′1),見圖3(b)。這樣，根據(jù)G(v′;v′1,v′2)?G(v′;v′1),c(G(v′;v′1))>k-1。進(jìn)而可得k=c(G,f)≥c(G)≥c(G(v′;v′1))+1>k,與c(G)≤k矛盾。

情形1.3：v′1?V(P),v′2?V(P)。驗(yàn)證過程與情形1.1相似，這里省略。

情形2：v′?V(P)。驗(yàn)證過程和情形1一樣，我們?nèi)匀豢梢缘玫胶蚦(G) ≤k不一致的矛盾,這里省略。因此，結(jié)論(ii)成立。

(?) 假設(shè)(ii)成立。在G中固定一個(gè)點(diǎn)v0，其鄰點(diǎn)集NG(v0) = {v1,v2, … ,vp}，并且假設(shè)v0v1,v0v2是G的割邊, 即NH1(v0) = {v1},NH2(v0) = {v2},G(v0;NH1(v0),NH2(v0))=G(v0;v1,v2)。 由已知，c(G(v0;v1,v2))≤k-1。 令H′1=G(v0;v2,v3,…,vp)-v0,H′2=G(v0;v1,v2),H′3=G(v0;v1,v3,…,vp)-v0。

(5)

證明完成。

推論2.5[3]設(shè)T是一個(gè)樹，c(T)≤k當(dāng)且僅當(dāng)對(duì)T的任意度數(shù)大于或等于2的點(diǎn)v,總存在兩個(gè)點(diǎn)v1,v2∈NT(v)使得c(T(v;v1,v2))≤k-1。

式(5)中的標(biāo)號(hào)f稱為f是由順序(f1,f2,f3)或(V(H′1),V(H′2),V(H′3))定義的。

推論2.6設(shè)v是G的一個(gè)點(diǎn)，v∈D≥3(G)，如果對(duì)任意1 ≤i,j≤m，c(G(v;NHi(v),NHj(v)))≥k-1成立，則c(G) ≥k，即使NG(v)包含兩個(gè)點(diǎn)vi,vj使得vvi,vvj是G的割邊。

3 應(yīng)用

由定理2.4, 我們可得到一類k-割寬臨界圖。根據(jù)文獻(xiàn)[18]，由于K1,2k-1是k-割寬臨界的，在本節(jié)中我們約定對(duì)任意v∈V(G)，其度數(shù)dG(v)≤2k-2。

定義3.1(i) 設(shè)G,H是兩個(gè)不相交的圖，u∈V(G)，v∈V(H)。把u和v粘合成一個(gè)點(diǎn)z就是用一個(gè)新點(diǎn)z代u和v(即u=v=z), 且z分別和G中u的所有鄰點(diǎn)、H中v的所有鄰點(diǎn)均相連。這種運(yùn)算得到的圖表示為G⊙u,vH,即G⊙u,vH=(G-u)∪(H-v)∪{zw:w∈NG(u)∪NH(v)}, 其中z稱為粘合點(diǎn)。

(ii) 設(shè)G1、G2、G3是3個(gè)不相交的圖，D3(K1,3) = {u0}，D1(K1,3) = {u1,u2,u3}。 對(duì)每一 個(gè)1≤j≤3，令vj∈V(Gj)。定義K1,3? (G1,G2,G3)為分別將每一對(duì)uj和vj粘合在一起所得到的圖(見圖2(b)中的示例)。

引理3. 2設(shè)G是一個(gè)圖，D1(G)≠?,Pl=x0x1…xl是一個(gè)長(zhǎng)度為l的路。則對(duì)意v0∈V(G)，c(G⊙v0,x0Pl)=k。

(6)

定理3.3根據(jù)定義3.1(ii), 如果{G1,G2,G3}有至少一個(gè)圖, 比如說G2， 是(k-1)-割寬臨界的，且D1(G2)≠?, 那么c(K1,3?(G1,G2,G3))=k。

證明:令G=K1,3? (G1,G2,G3)。對(duì)任意1≤j≤3，如果dG(vj) = 2, 即dGj(vj)=1，則根據(jù)引理1.5先對(duì)圖G進(jìn)行序列縮減。因?yàn)閡0v2是子圖G2⊙u2,v2u0v2的一條懸掛邊且G2是(k-1)-割寬臨界的，所以，根據(jù)引理3.2，c(G2⊙u2,v2u0v2)=k-1。

因?yàn)镚-{u0v1,u0v3}包含3個(gè)割寬為k-1的連通分枝G1,G2⊙u2,v2u0v2,G3, 所以，相似于式(5)，我們可以得到一個(gè)由(V(G1),G2⊙u2,v2u0v2,V(G3))確定的最優(yōu)標(biāo)號(hào)，f:V(G)→{1,2,…,n}且c(G,f) ≤ (k-1) + 1 =k。 因此，由式(2),c(G) ≤k。 另一方面， 由推論2.6，c(G) ≥k。 這是因?yàn)閷?duì)任意vi,vj∈NG(u0)，c(G(u0;vi,vj))=k-1。這樣，c(G)=k。

推論3.4根據(jù)定義3.1(ii), 對(duì)每一個(gè)1≤j≤3, 如果Gj是(k-1)-割寬臨界的，vj∈D1(Gj), 則K1,3? (G1,G2,G3)是k-割寬臨界的。

證明:令G=K1,3? (G1,G2,G3)。對(duì)每一個(gè)1≤j≤3，因?yàn)閐G(vj)=2，所以我們首先對(duì)G進(jìn)行至少3次序列縮減。為方便，我們?nèi)匀涣頝G(u0) = {v1,v2,v3}。 這樣G(u0;v1,v2) =G3,G(u0;v2,v3) =G1，G(u0;v1,v3) =G2, 并且由假設(shè)和定理3.3可得c(G)=k。

其次, 我們驗(yàn)證G的k-割寬臨界性，即對(duì)任意G′∈M(G),c(G′)≤k-1。由定義2.1(ii)，任意G′都可以通過刪除G的一條邊xy得到，這里的xy即可以是G的懸掛邊，也可以是G的圈Ct(t≥ 3)中的非懸掛邊，即xy∈E(Ct), 但xy∈/{u0v1,u0v2,u0v3}。不失一般性, 不妨令xy∈E(G2)。對(duì)每一個(gè)1≤j≤3，因?yàn)镚j是(k-1)-割寬臨界的，所以,c(G1-u0v1) ≤k-2,c(G2-xy) ≤k-2和c(G3-u0v3)≤k-2。這樣, 相似于式(5), 我們可以得到G′的一個(gè)由(V(G1-u0v1),V(G2-xy),V(G3-u0v3))定義的標(biāo)號(hào)f′:V(G′)→{1,2,…,|V(G′)|}，并且c(G′,f′)=k-1。因此，根據(jù)式(2)，c(G′)≤k-1。所以,G是k-割寬臨界的。

對(duì)整數(shù)k≥ 1，本文首先刻畫了k-割寬圖的一個(gè)結(jié)構(gòu)，改進(jìn)和推廣了己有結(jié)果。 其次，建立了一類k-割寬臨界圖，其中包含于推論3.4的方法可以構(gòu)造更多的k-割寬臨界圖。對(duì)一個(gè)較大的整數(shù)k0≥4, 盡管找到所有的k0-割寬臨界圖是困難的，然而其中大部分圖的結(jié)構(gòu)是有規(guī)律可循的。因此,刻畫它們的結(jié)構(gòu)特征將是進(jìn)一步研究的任務(wù)。