• 
    

    
    

      99热精品在线国产_美女午夜性视频免费_国产精品国产高清国产av_av欧美777_自拍偷自拍亚洲精品老妇_亚洲熟女精品中文字幕_www日本黄色视频网_国产精品野战在线观看

      ?

      具有最多與最少連通子圖的單圈圖

      2015-01-13 10:18:02洪雅麗
      宜春學院學報 2015年3期
      關(guān)鍵詞:子樹單圈子圖

      洪雅麗

      (晉江市南僑中學,福建 泉州 362200)

      設(shè)T 是一棵樹,它的一個連通的導(dǎo)出子圖稱為一個子樹。子樹的計數(shù)問題被廣泛研究,Székely與Wang[1]考慮了二元樹的子樹的計數(shù)問題,得到了具有最多子樹的二元樹,Yan 與Yeh[2]給出了兩個線性算法計算樹的子樹的數(shù)目,Li 與Wang[3]進一步分析研究了樹的子樹的計數(shù)問題。有關(guān)計算樹的子樹數(shù)目見相關(guān)文獻。[4-10]一個自然的問題是:考慮單圈圖的連通子圖的計數(shù)問題。袁新梅[11]給出了一個線性算法計算單圈圖的連通子圖的數(shù)目。在此基礎(chǔ)上,下文主要考慮連通單圈圖的連通子圖數(shù)目的極值問題。

      1 基本術(shù)語與基本結(jié)果

      為了描述方便,采用文[2,11]中的符號與基本術(shù)語。

      除特別說明外,假設(shè)G = {V(G),E(G);f,g}為一帶權(quán)單圈圖,其中V(G)= {v1,v2,…,vn}為頂點集合,E(G)= {e1,e2…,en}為邊集合,頂點的帶權(quán)函數(shù)為f:V(G)→R,邊的帶權(quán)函數(shù)為g:E(G)→R(其中R 表示非負實數(shù)集)。如果一帶權(quán)單圈圖G = {V(G),E(G);f,g}滿足f = g =1 ,稱G 為一簡單單圈圖。對于一個給定的帶權(quán)單圈圖G的連通子圖G1,定義G1的權(quán)是G1里所有頂點與邊的權(quán)的乘積,用ω(G1)來表示。帶權(quán)單圈圖G= (V(G),E(G);f,g)的所有連通子圖的權(quán)之和用F(G;f,g)表示。定義帶權(quán)單圈圖G = (V(G),E(G);f,g)包含一個固定頂點vi的連通子圖的權(quán)和為包含頂點vi的G 的連通子圖的權(quán)的和,用F(G;f,g;vi)表示。假設(shè)G 是一個n 個頂點的簡單單圈圖,用χ(G)= F(G;1,1)來表示G 的連通子圖的數(shù)目,G 的包含頂點vi的連通子圖的數(shù)目表示為χ(G;vi)= F(G;1,1;vi)。

      令G 是n(n >1)個頂點并且含一片葉子u 的單圈圖。假設(shè)G 的懸掛邊為e = (u,v)。定義頂點個數(shù)為n-1 的一個帶權(quán)單圈圖G' = (V(G'),E(G');f',g'),其中V(G')= V(G) {u},E(G')= E(G) {e},

      對于任意的vs∈V(G'),對于任意的e ∈E(G'),有g(shù)'(e)= g(e)。圖1 與圖2 說明了由G構(gòu)造G' 的過程。

      圖1 權(quán)單圈圖G = (V(G),E(G);f,g)及其一懸掛邊e = (u,v)

      圖2 對應(yīng)的權(quán)單圈圖G' = (V(G'),E(G');f',g')

      定理1.1[11]根據(jù)上面的記法,有F(G;f,g)= F(G';f',g')+ f(u)。

      利用此結(jié)果,袁[11]給出了計算連通的單圈圖的連通子圖的計數(shù)方法。

      定理1.2[11]令G = (V(G),E(G))是有n(n>1)個頂點的簡單單圈圖,其中圈上有l(wèi) 個頂點,記為v1,v2,…,vl,Ti(i = 1,2,…l)為附在圈上且包含頂點vi樹,則:

      2 主要結(jié)果

      在下文中,除特別說明外,單圈圖均為簡單圖。

      圖3 由單圈圖G'1 與樹T'1 構(gòu)造得到的單圈圖G1

      圖4 通過G'1 的頂點u

      附上r 個懸掛邊而得到的圖G2

      定理2.1 令G1和G2是如上定義的單圈圖,當r ≥1 即有:χ ( G2)= F ( G2;1,1 ),等號成立當且僅當T'1= K1,r且dT'1( )v = r。

      證明:令fi:V ( G'1)→R ( i = 1,2 )為兩個如下

      定義的函數(shù):

      其中F (T'1;1,1;V )是T'1中包含頂點v 的子樹數(shù)。

      由定理2.1 得:

      即:

      注意到:T'1是含有r +1 個頂點的樹,有2r+r-F(T'1;1,1)≥0 ,等號成立當且僅當T'1= K1,r。因為T'1至少有r 個含一個頂點vi(vi≠v)的子樹,則F(T'1;1,1)≥F(T'1;1,1;v)+ r。

      注 意 到,F(xiàn)(K1,r;1,1) = 2r+ r,即:0 ≤F(K1,r;1,1)- F(T'1;1,1)≤2r-F(T'1;1,1;v)。

      所以2r-F(T'1;1,1;v)≥0(等號成立當且僅當T'1= K1,r且dT'1(v)= r)。

      因此有χ(G1)= F(G1;1,1)≤χ(G2)= F(G2;1,1)。

      等號成立當且僅當T'1= K1,r且dT'1(v)= r。即定理得證。

      圖5 由單圈圖G'1 與樹T'1構(gòu)造得到的單圈圖G1

      圖6 通過G'1 的頂點u 附上一條長為r 的路而得到的圖G3

      定理2.2 令G1和G3是如上定義的單圈圖,且r ≥1 。則χ(G1)= F(G1;1,1)≥χ(G3) =F(G3;1,1)。

      當且僅當T'1= Pr+1且dT'1(v)= 1 時等號成立。

      令Gd是沒有葉子圈長為d 的單圈圖,G 是由Gd將ki個懸掛邊附于頂點vi而生成的,i = 1,2,... ,d(見圖7)。單圈圖G*是在沒有葉子的單圈圖Gd的頂點vh上附于個懸掛邊而生成的(如圖8)。

      圖7 由Gd 將ki(i = 1,2,... ,d)個懸掛邊附于vi 而生成的單圈圖G = Gd(k1,k2,…,kd)

      圖8 在沒有葉子的單圈圖Gd 的頂點vh 上附于個懸掛邊而生成的單圈圖G*

      定理2.3 令G 和G*為如上定義的兩個單圈圖,k1,k2,…,kd至少有兩個不為零。則F(G;1,1)<F(G*;1,1)。

      證明:根據(jù)定理2.2,有

      以此類推,可得

      又因為2k1+k2+…+kd>0 ,d ≥3 ,

      所以F(G*;1,1)- F(G;1,1)>0 。

      因此有F(G;1,1)<F(G*;1,1)。

      從而定理成立。

      令G0是沒有葉子的單圈圖,其圈上有d 個頂點,分別為v1,v2,…,vd?,F(xiàn)將每個頂點vi(1 ≤i ≤d)上附于一條有ki個頂點的路,生成G&(如圖9)。vh是G0的一個頂點,在G0的頂點vh上附于一條有個頂點的路,生成G#(如圖10)。

      圖9 單圈圖G&

      圖10 單圈圖G#

      定理2.4 令G&和G#為如上定義的單圈圖,且至少有兩個ki不為零,則χ(G&)= F(G&;1,1)<χ(G#)= F(G#;1,1)。

      成立當且僅當G = G*。

      [1]Székely LA,Wang H.On subtrees of trees[J].Adv.Appl.Math,2005,34(1):138-155.

      [2]Yan WG,Yeh YN.Enumeration of subtrees of trees[J].Theoretical Computer Science,2006,369:256-268.

      [3]Li SC,Wang SJ.Further Analysis on the Total Number of Subtrees of Trees[J].The Electronic Journal of Combinatorics,2012,(19):48.

      [4]Székely LA,Wang H.Binary trees with the largest number of subtrees with at least one leaf[J].Congr.Numer.,2005,177:147-169.

      [5]Wang H.Some results on trees[M].Ph.D.Thesis,Department of Mathematics,University of South Carolina,2005.

      [6] Wagon S.A bound on the chronmatic number of graphs without certain induced subgraphs[J].J.Combin.Theory.Ser.B,1980,29:245-246.

      [7]Walter JR.Representations of chordal graphs as subtrees of a tree[J].J.Graph Theory,1978,(2):265-267.

      [8]Wang DL,Kleitman DJ.On the existence of n-connected graphs with prescribed degrees(n ≥2)[J].Networks,1973,(3):225-239.

      [9]Bondy J.A,Murty U.S.R.Graph Theory with Applications[M].Macmillan Press LTD,1976.

      [10]袁新梅. 單圈圖的連通子圖的數(shù)目[J]. 南開大學學報(自然科學版),2011,44(3):23-27.

      猜你喜歡
      子樹單圈子圖
      黑莓子樹與烏鶇鳥
      一種新的快速挖掘頻繁子樹算法
      一類單圈圖的最大獨立集的交
      單圈圖關(guān)聯(lián)矩陣的特征值
      書本圖的BC-子樹計數(shù)及漸進密度特性分析?
      臨界完全圖Ramsey數(shù)
      基于覆蓋模式的頻繁子樹挖掘方法
      基于頻繁子圖挖掘的數(shù)據(jù)服務(wù)Mashup推薦
      不含2K1+K2和C4作為導(dǎo)出子圖的圖的色數(shù)
      剩余類環(huán)Z/(pn)上若干類單圈多項式構(gòu)造
      阿鲁科尔沁旗| 广元市| 都兰县| 阿克陶县| 龙胜| 寻甸| 林周县| 双辽市| 绥芬河市| 南雄市| 花莲县| 清苑县| 吐鲁番市| 东乡族自治县| 德令哈市| 娄底市| 平果县| 南漳县| 靖宇县| 连山| 金阳县| 耿马| 马山县| 高邮市| 酉阳| 卫辉市| 买车| 老河口市| 沁水县| 三河市| 凤翔县| 黄龙县| 保靖县| 肃宁县| 凤台县| 阿图什市| 保亭| 海淀区| 天长市| 望城县| 永宁县|