• 
    

    
    

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

      ?

      基于字典序乘積下廣義和連通度指標(biāo)的上下界

      2022-07-06 08:09:24李志豪
      關(guān)鍵詞:圖記下界乘積

      李志豪, 朱 焱

      ( 華東理工大學(xué)數(shù)學(xué)學(xué)院,上海 200237)

      拓?fù)渲笜?biāo)是與圖的化學(xué)結(jié)構(gòu)相關(guān)聯(lián)的一種數(shù)學(xué)方法,分子圖的拓?fù)渲笜?biāo)值不僅可以定量地表達(dá)分子的結(jié)構(gòu),也能用來分析分子的結(jié)構(gòu)與活性之間的關(guān)系,并且這些拓?fù)渲笜?biāo)值在圖的自同構(gòu)下是不變的,所以它已成功地與有機(jī)分子的物理和化學(xué)性質(zhì)相關(guān)聯(lián),因此對于拓?fù)渲笜?biāo)的研究至關(guān)重要。但研究難點(diǎn)在于有些化合物分子比較復(fù)雜,拓?fù)渲笜?biāo)的計算量比較大。

      Onagh[6]研究了關(guān)于字典序乘積圖的F-和的調(diào)和指標(biāo)。Akhter 等[7]研究了關(guān)于笛卡爾乘積圖的F-和的廣義和連通度指標(biāo)。Du等[8]研究了當(dāng)非零實(shí)數(shù)大于或等于?1時,具有n個頂點(diǎn)的單圈圖的廣義和連通度指標(biāo)的最小值和次最小值,并且確定了相對應(yīng)的極圖。Tomescua 等[9]確定了不同樹的廣義和連通度指標(biāo)的最小值。

      本文把基于笛卡爾乘積下運(yùn)算圖的廣義和連通度指標(biāo)上下界推廣到基于字典序乘積下運(yùn)算圖的廣義和連通度指標(biāo)的上下界,然后計算了基于字典序乘積下運(yùn)算圖的廣義和連通度指標(biāo)的上下界,并對于每一個定理都分別給出了一個運(yùn)算圖的例子,計算了其廣義和連通度指標(biāo),同時與定理中的上下界進(jìn)行比較,從而驗(yàn)證了定理。

      1 基本概念

      令G是一個有限、簡單、連通的無向圖,其點(diǎn)集和邊集分別為V=V(G) ,E=E(G) 。對于任意頂點(diǎn)v∈V,dG(v)表示v的度。Pn表示有n個頂點(diǎn)的路。對于給定的連通圖G,4種相關(guān)圖[10]定義如下:

      (1) 在圖G的每條邊上嵌入一個新的頂點(diǎn),將新頂點(diǎn)與所對應(yīng)邊的兩個端點(diǎn)連接,這樣圖G中的每條邊就變成了長為2的路,由此得到的圖記為S(G) 。

      (2) 在圖G的每條邊外,都加一個與之相對應(yīng)的新的頂點(diǎn),然后再把每個新的頂點(diǎn)與其相對應(yīng)邊的兩個端點(diǎn)連接,由此得到的圖記為R(G) 。

      (3) 在圖G的每條邊上嵌入一個新頂點(diǎn),將新頂點(diǎn)與所對應(yīng)邊的兩個端點(diǎn)連接,然后再把圖G中相鄰兩條邊所對應(yīng)的新頂點(diǎn)連接起來,由此得到的圖記為Q(G) 。

      (4) 在圖G的每條邊外,都加一個與之相對應(yīng)的新的頂點(diǎn),再把每個新的頂點(diǎn)與其相對應(yīng)邊的兩個端點(diǎn)連接,然后再把圖G中相鄰兩條邊所對應(yīng)的新的頂點(diǎn)連接起來,由此得到的圖記為T(G) 。

      如果G為P6,則S(P6) ,R(P6) ,Q(P6) 和T(P6)分別如圖1所示。

      圖1 F∈{S,R,Q,T} 時F(P6)的4種運(yùn)算Fig. 1Fouroperations ofF(P6)atF∈{S,R,Q,T}

      兩個連通圖G0和G1的字典序乘積G0[G1] 定義為:其點(diǎn)集為V(G0)×V(G1) ,其圖中的兩個點(diǎn) (a1,b1)和 (a2,b2) 相鄰當(dāng)且僅當(dāng)a1與a2在G0中相鄰或者b1與b2在G1中相鄰且a1=a2[11]。

      Sarala等[12]在兩個連通圖G0和G1的字典序乘積的基礎(chǔ)上介紹了圖的4種新運(yùn)算。

      令F∈{S,R,Q,T} ,則G0和G1關(guān)于字典序乘積的F-和G0[G1]F定義為F(G0)[G1]?E?,其中E?={(a,b1)(a,b2)∈E(F(G0)[G1]):a∈V(F(G0))?V(G0),b1b2∈E(G1)}。

      若G0=G1=P3,則P3[P3]S,P3[P3]Q,P3[P3]R,P3[P3]T如圖2所示。

      圖2 F∈{S,R,Q,T} 時圖P3[P3]的4種運(yùn)算Fig. 2 Four operations on graph P3[P3] at F ? {S,R,Q,T}

      2 主要結(jié)果

      本文確定了關(guān)于字典序乘積圖的F-和的廣義和連通度指標(biāo)的上下界。令n1,m1分別表示圖G0的頂點(diǎn)數(shù)和邊數(shù),n2,m2分別表示G1的頂點(diǎn)數(shù)和邊數(shù), δG0和 ?G0分別表示圖G0的最小度和最大度, δG1和 ?G1分別表示圖G1的最小度和最大度。本文首先考慮F=S。

      定理1當(dāng) α 為負(fù)數(shù),廣義和連通度指標(biāo)滿足不等式γ1(S)≤χα(G0[G1]S)≤γ2(S),其中,

      證明:

      由于對于a1∈V(G0) ,有dS(G0)(a1)=dG0(a1) ,所以式(1)成立。

      由等式 |E(S(G0))|=2|E(G0)|=2m1,當(dāng)a2∈V(S(G0))?V(G0) 時,dS(G0)(a2)=2 ,所以

      [n2dG0(a1)+dG1(b1)+2n2]α≥2m1n22(n2?G0+?G1+2n2)α

      同理可得

      不等式取等號當(dāng)且僅當(dāng)圖G0和G1均為正則圖。

      為了驗(yàn)證定理1的上下界,本文舉例1說明。

      例1:當(dāng)G0=P4,G1=P2時,

      χα(G0[G1]S)=2×6α+2×10α+8×7α+16×9α

      γ1(S)=4×10α+24×9α

      γ2(S)=4×6α+24×7α

      滿足 γ1(S)≤χα(G0[G1]S)≤γ2(S) 。

      定理2當(dāng)F=R時,對于負(fù)數(shù) α ,廣義和連通度指標(biāo)滿足不等式 γ1(R)≤χα(G0[G1]R)≤γ2(R) ,其中

      不等式取等號當(dāng)且僅當(dāng)圖G0和G1均為正則圖。

      證明:

      由于 δG0≤dG0(a)≤?G0,δG1≤dG1(b)≤?G1,不等式取等號當(dāng)且僅當(dāng)圖G0和G1均為正則圖,因此可以得到

      由于對于a1∈V(G0) ,有dR(G0)(a1)=2dG0(a1) ,所以式(2)成立。

      由于dR(G0)(a1)=2dG0(a1) 、a1a2∈E(R(G0)) 和a1,a2∈V(G0) 當(dāng)且僅當(dāng)a1a2∈E(G0) ,因此

      由等式 |E(R(G0))?E(G0)|=2|E(G0)|=2m1,當(dāng)a1∈V(G0) 時,dR(G0)(a1)=2dG0(a1) ;當(dāng)a2∈V(R(G0))?V(G0)時,dR(G0)(a2)=2 ,所以

      不等式取等號當(dāng)且僅當(dāng)圖G0和G1均為正則圖。

      為了驗(yàn)證定理2的上下界,本文舉例2說明。

      例2:當(dāng)G=P4,H=P2時,

      滿足 γ1(R)≤χα(G0[G1]R)≤γ2(R) 。

      定理3當(dāng)F=Q時,對于負(fù)數(shù)α,廣義和連通度指標(biāo)滿足不等式γ1(Q)≤χα(G0[G1]Q)≤γ2(Q),其中

      不等式取等號當(dāng)且僅當(dāng)圖G0和G1均為正則圖。

      證明:

      由于 δG0≤dG0(a)≤?G0,δG1≤dG1(b)≤?G1,不等式取等號當(dāng)且僅當(dāng)圖G0和G1均為正則圖,因此可得

      由于對于a1∈V(G0) ,有dQ(G0)(a1)=dG0(a1) ,所以式(3)成立。

      由于a1和a2分別對應(yīng)于G0中的邊wiwj和wjwk,因此

      不等式取等號當(dāng)且僅當(dāng)圖G0和G1均為正則圖。

      為了驗(yàn)證定理3的上下界,本文舉例3說明。

      例3: 當(dāng)G=P4,H=P2時,

      定理4當(dāng)F=T時,對于負(fù)數(shù) α ,廣義和連通度指標(biāo)滿足不等式 γ1(T)≤χα(G0[G1]T)≤γ2(T) ,其中

      不等式取等號當(dāng)且僅當(dāng)圖G0和G1均為正則圖。

      為了驗(yàn)證定理4的上下界,本文舉例4說明。

      例4: 當(dāng)G=P4,H=P2時,

      χα(G0[G1]T)=2×10α+8×11α+16×14α+8×15α+8×17α+6×18α

      γ1(T)=16×18α+8×16α+24×17α

      γ2(T)=8×8α+24×9α+16×10α

      滿足 γ1(T)≤χα(G0[G1]T)≤γ2(T) 。

      3 結(jié) 論

      本文先給出了基于字典序乘積的4種運(yùn)算,并得到運(yùn)算圖中頂點(diǎn)的度與未做運(yùn)算的圖的度之間的關(guān)系,再利用最大度和最小度計算了在 α<0 的情況下基于字典序乘積的圖的4種運(yùn)算下的廣義和連通度指標(biāo)上下界,即 γ1(F)≤χα(G0[G1]F)≤γ2(F) ,其中F∈{S,R,Q,T}。如果α,>0那么γ2(F)≤χα(G0[G1]F)≤γ1(F)。因此對于其他的不同乘積,也可以把這4種運(yùn)算推廣到其他乘積上面,同樣找出乘積圖中頂點(diǎn)的度與圖G0、G1中頂點(diǎn)的度之間的數(shù)量關(guān)系,再利用最大度最小度求出廣義和連通度指標(biāo)的上下界。不過困難的是對于有些乘積,很難找出乘積圖中頂點(diǎn)的度與原圖中頂點(diǎn)的度之間的關(guān)系。

      猜你喜歡
      圖記下界乘積
      乘積最大
      煙圖記
      趣味(語文)(2020年3期)2020-07-27 01:42:40
      Dirichlet級數(shù)及其Dirichlet-Hadamard乘積的增長性
      Lower bound estimation of the maximum allowable initial error and its numerical calculation
      圖記
      時代人物(2016年5期)2016-06-22 13:53:22
      復(fù)變?nèi)呛瘮?shù)無窮乘積的若干應(yīng)用
      矩陣Hadamard積的上下界序列
      圖記 端午節(jié)的驚喜
      最大度為10的邊染色臨界圖邊數(shù)的新下界
      圖記
      時代人物(2014年12期)2015-01-29 13:58:42
      柘城县| 安阳市| 交口县| 冕宁县| 安多县| 安康市| 化德县| 交城县| 武汉市| 咸宁市| 平阳县| 息烽县| 甘泉县| 北辰区| 潞西市| 赤壁市| 新巴尔虎右旗| 沽源县| 象州县| 龙川县| 美姑县| 呼伦贝尔市| 云阳县| 邯郸市| 桂林市| 防城港市| 名山县| 肥乡县| 太和县| 金坛市| 集贤县| 博爱县| 呼图壁县| 金塔县| 贡觉县| 克什克腾旗| 青龙| 布拖县| 高安市| 林口县| 枞阳县|