樹的邊帶寬與葉子數

杜先云,任秋道,文華燕

(1.成都信息工程學院 數學學院，四川 成都 610225;2.綿陽師范學院 數學與計算機科學學院,四川 綿陽 621000；3.西南科技大學 城市學院，四川 綿陽 621000)

?

樹的邊帶寬與葉子數

杜先云1,任秋道2,文華燕3

(1.成都信息工程學院 數學學院，四川 成都 610225;2.綿陽師范學院 數學與計算機科學學院,四川 綿陽 621000；3.西南科技大學 城市學院，四川 綿陽 621000)

摘要：圖G邊的一個標號f是指邊集E(G)到集合{1,2,…,m}之間的一個一一映射，即:?e∈E(G),?t,1≤t≤m，使得f(e)=t.圖G的邊帶寬B′(G)=minBf′(G)，其中Bf′(G)=max{|f(uv)-f(uw)|：uv,uw∈E(G)}.給出樹T的邊帶寬滿足「(m-1)/(d-1)?≤B′(T)≤l-s，0≤s≤l/2，其中d為樹T的直徑，l為樹T的葉子數.而且k(為偶數)元正則樹的邊帶寬B′(T*)≤l/2，廣義星圖T*的邊帶寬B′(T*)=l或l-1.

關鍵詞：獨立鄰邊集；邊帶寬；樹；葉子數

本文圖G是無向有限連通圖，頂點集與邊集分別是V(G)和E(G).圖G邊的一個標號f是指邊集E(G)到自然數的子集{1,2,…,m}(m表示G的邊數)之間的一個一一映射，即:?e∈E(G),?t∈N+,1≤t≤m，使得f(e)=t.圖G的邊帶寬B′(G)=minBf′(G)，其中Bf′(G)=max{|f(uv)-f(uw)|:uv,uw∈E(G)}.對于一個標號f，若B′(G)=Bf′(G)，稱這個標號為圖G的邊帶寬標號[1-6].可以類似定義圖G的點帶寬，它來源于研究數值矩陣的逆，尋找圖的帶寬是一個NP問題.D.Eichhorn等人已完成了θ圖的邊帶寬[2].給出兩類3—正則圖的邊帶寬[3].本文用樹的葉子數來刻畫樹T的邊帶寬的界.

我們容易知道：圖G帶寬B′(G)≥Δ-1，其中Δ是圖G的最大度.下面給出一個引理.

引理1存在uv∈E(G)，使得圖G的邊帶寬B′(G)≥d(u)+d(v)-2，其中d(u)，d(v)分別表示頂點u和v的度[6].

證明令Γ(uv)={uiv:uiv∈E(G),1≤i≤d(v)}∪{uvj:uvj∈E(G),1≤j≤d(u)}，則有|Γ(uv)|=d(u)+d(v)-1.若f(uv)≤min{f(e):e∈Γ(uv)}，存在e′∈Γ(uv)使得f(e′)≥f(uv)+|Γ(uv)|-1.因此，Bf′(G)≥f(e′)-f(uv)≥d(u)+d(v)-2.對于f(uv)≥max{f(e):e∈Γ(uv)}，有類似結論.對于xy∈E(G)，設在Γ(xy)中標號最小或最大標號邊記為uv，對于邊uv應用該結論可得：Bf′(G)≥d(u)+d(v)-2.由于標號f的任意性，則有：存在uv∈E(G)，使得B′(G)≥d(u)+d(v)-2.

推論1設圖G是k-正則圖，則有B′(G)≥2(k-1).

圖1　圖的獨立鄰邊集分解Fig.1　A decompositiom of independent edge set of a graph

引理2保證了圖G邊集的正交分解.可以這樣來形象理解：拿著圖G一些頂點一抖，就把G的頂點分成n+1層，從而把G的邊集分為n層.如圖1.

定理1連通圖G的邊帶寬B′(G)≥「(m-1)/(d-1)?，d為圖G的直徑.

證明標號f是圖G的邊集到集合{1,2,…,m}之間的一一映射.從標號最小的邊到標號最大的邊之間有一條路pn=u0u1…un，該路上點的鄰邊編號差的絕對值等于或小于B′(G).為了方便，令:

假設f(u1)=f(u2)=…=f(un-1)=B′(G)達到最大來估計圖G的邊帶寬.該路上的邊標號分別是:f(u0u1)=1,f(uiui+1)=1+iB′(G)(1≤i≤n-1).

現在來說明路pn是點u0和un之間的短程線.若點ui(0≤i≤n-2)和uj(j≥i+2)有邊uiuj，它的標號介于邊ui-1ui和uiui+1的標號之間，令:

f(uiuj)=1+(i-1)B′(G)+k (1≤k

則有:f(uj)=f(ujuj+1)-f(uiuj)=(j-i+1)B′(G)-k>B′(G).

矛盾.因此點u0和un之間的距離是n.根據f(un-1un)=1+(n-1)B′(G)≥m，可得B′(G)≥「(m-1)/(n-1)?.由于圖G的最長路的邊數是直徑d，因此，B′(G)≥「(m-1)/(d-1)?.證畢.

圖2　圖)的邊的關聯情況Fig.2　A decompositiom of The categories of the related edges of the tragh )

定義2設T是一棵樹，懸掛點的集合為V′={v|d(v)=1}.如果存在點x，使得x和任意懸掛點v之間的距離都相等，即d(x,u)=d(x,v),u,v∈V′，稱樹T為理想樹，點x為樹根[5].

引理3理想樹T的邊帶寬不超過葉子數.

給點u2的未編號的邊排序如下：

給點us的關聯邊中還未編號的邊排序如下：

對于1≤k≤s-1，

定理3樹的邊帶寬不超過葉子數.

把k條路xiyi…zi(1≤i≤k)的全部始點xi粘合在一起構成的圖，稱為廣義星圖，記為T*.我們知道：星圖的邊帶寬比葉子數少1.

推論2廣義星圖T*的邊帶寬比葉子數少1或等于葉子數.

(ii)如果圖T*是由k條長度大于1的不同路構成，其中最長路的長度為r.把長度小于r的所有路增加邊變成長度為r的路，類似(i)可得，B(T*)=k.

圖3　構造樹T′=T1′+T2′Fig.3　The comtructeal

定理4樹T的邊帶寬滿足B′(T)≤l-s，0≤s≤l/2，其中l(wèi)為樹T的葉子數.

由定理2可得:樹T的邊帶寬滿足:B′(T)≤B′(T′)≤max{Δ(T),s,l-s}.

發(fā)現有很多樹的邊帶寬不超過葉子數的一半.如：路和k(為偶數)元正則樹的邊帶寬.

推論3k元正則樹T的邊帶寬滿足：當k為偶數時，B′(T)≤kr/2；當k為奇數時，B′(T)≤(kr+kr-1)/2，其中r(≥2)為樹T的半徑.

證明半徑為r的k元正則樹T的葉子數為kr，樹根為v.現在把T分解成兩顆半徑為r，樹根均為v的理想樹T1和T2.當k為偶數時，T1和T2的葉子數均為kr/2，當k為奇數時，T1的葉子數為(kr-kr-1)/2，T2的葉子數為(kr+kr-1)/2.根據定理4可得結論.證畢.

對于復雜的圖，由于與度為2的點相鄰的邊對圖的邊帶寬沒有貢獻，可將這樣的邊收縮掉.例如：將長度大于2的路收縮為長度為2的路，將長度大于3的圈收縮為長度為3的圈.經過邊收縮后的圖可以更好地研究圖的邊帶寬.

參考文獻:

[1]EICHHORN D,MUBAYI D,WEST D B.The edge-bandwidth of theta graphs[J].Graph Theory,2000(35): 89-98.

[2]PESK G W,SHASTRI A.Bandwidth of theta graphs with short paths[J].Discrete Mathematics,1992(103):177-187.

[3]Papadimitriou.The NP-completeness of the bandwidth minimization problem[J].Computing,1976(16):263-270.

[4]GAREY M R,GRAHAM R L,JOHNSON D S,et al.Complexity results for bandwidth minimization[J].SIAM J Applmath,1978,34:477-495.

[5]SMITHLINE L.Bandwidth of the compkletek-ary tree[J].Discrete Mathematics,1995,142:203-212.

[6]任秋道,黃瓊湘.完全圖的邊帶寬的另一證明[J].綿陽師范學院學報,2005(2):12-17.

[7]陳玲,任秋道,岳華.兩類3-正則圖的邊帶寬[J].新疆師范學大學院學報,2008(1):23-26.

[8]杜先云,任秋道.圖Cmk(P2,…，P2,Pl)的最大特征值[J].四川師范大學學報(自然科學版),2009,32(1):64-67.

[9]任秋道,何繼標,黃瓊湘.圈的定向距離圖的性質[J].四川師范大學學報(自然科學版),2007,30(2):185-187.

[10]任秋道,汪元倫.圈的定向距離圖的階[J].四川師范大學學報(自然科學版),2005,28(2):63-65.

責任編輯：時凌

The Edge-bandwidth of a Tree and its Number of Leaves

DU Xianyun1,REN Qiudao2,WEN Huayan3

(1.College of Mathematics of Chengdu University of Information Technology,Chengdu 610225,China;2.Department of Mathematics and Information Science of Mianyang Normal University,Mianyang 621000,China;3.City College,Southwest University of Science and Technology,Mianyang 621000,China)

Abstract：A label f of an edge in a graph G refers to one-mapping from the edge set E(G)to the set {1,2,…,m},namely:?e∈E(G),?t,1≤t≤m,satisying f(e)=t.The edge-bandwidth of a graph B′(G)=minBf′(G),wherein Bf′(G)=max{|f(uv)-f(uw)|:uv,uw∈E(G)}.The paper obtains that the inequalities 「(m-1)/(d-1)?≤B′(T)≤l-s，0≤s≤l/2，wherein d is the diameter of a tree and l is the number of its leaves.Moreover the edge-bandwidth of a k(even)-regular tree T satisfies the inequalities B′(T)≤l/2,and the edge-bandwidth of a generalized star graph T* does B′(T*)=l or l-1.

Key words：independent adjacent edge- set;edge bandwidth；tree;number of leaves

收稿日期：2016-03-21.

基金項目：四川省教育廳自然科學基金項目(15114931).

作者簡介：杜先云(1964-)，男，教授，主要從事應用數學的研究.

文章編號：1008-8423(2016)01-0001-04

DOI:10.13501/j.cnki.42-1569/n.2016.03.001

中圖分類號：O175

文獻標志碼：A