基于拉普拉斯度的k-均勻超圖的圖熵極值

盧鵬麗, 薛玉龍

(蘭州理工大學(xué) 計(jì)算機(jī)與通信學(xué)院, 甘肅 蘭州 730050)

設(shè)H=(V(H ),E(H ))是一個(gè)頂點(diǎn)數(shù)為n，超邊數(shù)為m的超圖.其中頂點(diǎn)集V(H )={1,2,…,n}，超邊集E(H )={e1,e2,…,em}(不包括空集).和圖相比較，超圖的每條超邊上可以有多個(gè)頂點(diǎn).若超圖的所有超邊都有相同的頂點(diǎn)個(gè)數(shù)k，則稱之為k-均勻超圖.顯而易見(jiàn)，通常意義上的圖就是2-均勻超圖.因此，圖是一種特殊的超圖，超圖也可以看成是一般圖的推廣.因此，超圖的一些性質(zhì)與圖的性質(zhì)相似，但是又有所不同.通常情況下為了敘述簡(jiǎn)便，一般也將超邊簡(jiǎn)稱為邊.沒(méi)有重邊的k-均勻超圖被稱為簡(jiǎn)單k-均勻超圖.在超圖中長(zhǎng)度為r的途徑W用一個(gè)頂點(diǎn)和邊交替的序列v0e1v1e2…ervr來(lái)表示，其中{vi-1,vi}?ei，i=1,…,r.若回路中除v0=vr外，沒(méi)有其他頂點(diǎn)或者邊重復(fù)，則這個(gè)回路被稱為圈.若v0=vr，則稱途徑W為一個(gè)回路.若途徑W中沒(méi)有頂點(diǎn)或者邊重復(fù)，則稱這條途徑W為超路Pn.若超圖中任意兩個(gè)頂點(diǎn)之間有途徑連接，則該超圖被稱為是連通的.本文中，只考慮簡(jiǎn)單連通的k-均勻(k≥3)超圖.

在超圖中，若頂點(diǎn)v∈e，則稱頂點(diǎn)v和邊e相關(guān)聯(lián).若存在一條邊包含頂點(diǎn)vi和vj，則稱頂點(diǎn)vi和vj相鄰接.若兩條邊的交集ei∩ej≠?，則表示這兩條邊vi和vj相鄰.對(duì)于k-均勻超圖H，包含頂點(diǎn)v∈V(H )的邊的個(gè)數(shù)定義為頂點(diǎn)v的度，即dv=|ej:v∈ej∈E(H )|.度d=1的頂點(diǎn)稱為懸掛點(diǎn)，否則被稱為非懸掛點(diǎn).若邊e∈E(H)正好包含k-1個(gè)懸掛點(diǎn)，則稱e為懸掛邊，否則被稱為非懸掛邊.

定義1[1]設(shè)H是一個(gè)頂點(diǎn)數(shù)為n，邊數(shù)為m，連通分支數(shù)為l的k-均勻超圖.則H的圈數(shù)為c(H )=m(k-1)-n+l.因此，超圖H可以稱為c(H )圈超圖.

由于本文中只考慮簡(jiǎn)單連通超圖，所以c(H)=m(k-1)-n+1.

定義2[2]超樹(shù)是連通、無(wú)圈的超圖.

定義3[2-3]樹(shù)的k次冪稱為k-均勻超樹(shù).

超樹(shù)(hypertree)的每條邊上最多有兩個(gè)非懸掛點(diǎn)，本文討論的超樹(shù)均是hypertree.與化學(xué)樹(shù)的定義類似，定義化學(xué)超樹(shù)是最大度不超過(guò)4的超樹(shù).

定義5[4]設(shè)G是一個(gè)頂點(diǎn)集V(G)={v1,v2,…,vn}的連通圖，其中頂點(diǎn)vi的度為di.則基于度的圖熵定義為

早在1949年，Shannon等[5]為了解決通信中信息量化的問(wèn)題提出Shannon熵.受此啟發(fā)，Dehmer[6]將Shannon熵的概念引入圖論中，用來(lái)描述圖的結(jié)構(gòu)信息，簡(jiǎn)稱為圖熵. Cao等[4]基于圖熵的定義提出了基于度的圖熵，確定了一些圖類的圖熵極值，并找到了圖熵與度冪之和的關(guān)系.Das等[7]得到了基于度冪的圖熵的一些上界和下界，并刻畫(huà)了極值圖.Hu等[8]確定了基于度的一些特定均勻超圖的圖熵的極值.關(guān)于圖熵的研究還有很多，詳見(jiàn)文獻(xiàn)[9-12].

1 基本理論

設(shè)π(H)=(δ1,δ2,…,δn)為超圖H的非增拉普拉斯度序列，其中δ1≥δ2≥…δn，則

根據(jù)定義5，定義超圖中基于拉普拉斯度的圖熵為

定義7[2]設(shè)超圖H=(V(H),E(H))中頂點(diǎn)u∈V(H)，邊e1,…,er∈E(H)，其中r≥1，u?ei(i=1,…,r).令頂點(diǎn)vi∈ei，邊e′i=(ei﹨{vi}∪{u})，其中i=1,…,r.設(shè)超圖H′=(V(H),E′(H))的邊集E′(H)=(E(H)﹨{e1,…,er})∪{e′1,…,e′r}.因此，通過(guò)分別移動(dòng)超圖H邊(e1,…,er)上的頂點(diǎn)(v1,…,vr)到頂點(diǎn)u可得到超圖H′.

引理1設(shè)超圖H上存在兩個(gè)頂點(diǎn)vi和vj使得拉普拉斯度δi≥δj+2(k-1)，其中頂點(diǎn)vi∈e∈E(H )，頂點(diǎn)vj?e.若超圖H通過(guò)定義7的移邊操作，移動(dòng)邊e上的頂點(diǎn)vi到頂點(diǎn)vj可得到超圖H′，則h(H)>h(H′).

證明由于δi≥δj+2(k-1)，因此δi>δi-(k-1)≥δj+(k-1)>δj.則

其中ξ1∈(δi-(k-1),δi)，ξ2∈(δj,δj+(k-1)).

證畢.

引理2設(shè)超圖H上存在兩個(gè)頂點(diǎn)vi和vj使得拉普拉斯度δi≥δj≥2(k-1)，其中頂點(diǎn)vj∈e∈E(H)，頂點(diǎn)vi?e.若超圖H通過(guò)定義7的移邊操作，移動(dòng)邊e上的頂點(diǎn)vj到vi可得到超圖H′，則h(H)

證明由于δi≥δj≥2(k-1)，因此δi+(k-1)>δi≥δj>δj-(k-1).則

h(H)-h(H′)=δilog2δi+δjlog2δj-

(δi+(k-1))log2(δi+(k-1))-

(δj-(k-1))log2(δj-(k-1))=

-{(δi+(k-1))log2(δi+(k-1))-

δilog2δi}+{δjlog2δj-

(δj-(k-1))log2(δj-(k-1))}=

-(k-1)(log2ξ1-log2ξ2)<0

其中:ξ1∈(δi,δi+k-1)，ξ2∈(δj-(k-1),δj).

證畢

引理3[2]設(shè)H ′是單圈k-均勻超圖H經(jīng)過(guò)移邊操作后得到的超圖.若H ′是連通的，則H ′仍然是單圈k-均勻超圖.

引理4[2]設(shè)H ′是雙圈k-均勻超圖H經(jīng)過(guò)移邊操作后得到的超圖.若H ′是連通的，則H ′仍然是雙圈k-均勻超圖.

因此，單圈k-均勻超圖經(jīng)過(guò)定義7中的移邊操作之后仍然是單圈k-均勻超圖.雙圈k-均勻超圖經(jīng)過(guò)定義7中的移邊操作之后仍然是雙圈k-均勻超圖.

引理5[14]設(shè)f為定義在實(shí)數(shù)集R上的嚴(yán)格凸函數(shù)，x,y∈Rn，則

2 基于拉普拉斯度的圖熵上、下界與極值圖

2.1 k-均勻超樹(shù)

證畢

2.2 單圈k-均勻超圖

設(shè)H*是拉普拉斯度序列π(H*)=[2k-2(m),k-1(n-m)]的單圈k-均勻超圖.H**是拉普拉斯度序列π(H**)=[2k-3(2),k-1(n-2)]的單圈k-均勻超圖.

當(dāng)且僅當(dāng)H ?H**時(shí)，左側(cè)等式成立.當(dāng)且僅當(dāng)H ?H*時(shí)，右側(cè)等式成立.

證明設(shè)f(x)=xlog2x，其中x≥0.由于f(x)是嚴(yán)格凸函數(shù)，因此h(H )滿足引理5中的結(jié)論.非增拉普拉斯度序列π(H )=(δ1,δ2,…,δn)中的前r項(xiàng)越大，則h(H )越大.反之，則結(jié)論相反.換而言之，由于拉普拉斯度之和為k(k-1)m，且連通圖中拉普拉斯度最小為k-1，因此拉普拉斯度序列中k-1的個(gè)數(shù)越多，則h(H )越大.

單圈k-均勻超圖可以分為以下三種結(jié)構(gòu)：多懸掛邊，單懸掛邊，無(wú)懸掛邊.不難得出，有懸掛邊結(jié)構(gòu)的單圈k-均勻超圖最大的拉普拉斯度δ1>2(k-1)，而無(wú)懸掛邊結(jié)構(gòu)時(shí)δ1=2(k-1).根據(jù)引理5，可得單圈k-均勻超圖是無(wú)懸掛邊結(jié)構(gòu)時(shí)，h(H)取到最小值，即h(H)≥h(H*).無(wú)懸掛邊結(jié)構(gòu)的單圈k-均勻超圖的拉普拉斯度序列π(H*)=[2k-2(m),k-1(n-m)].因此

當(dāng)圈上包含的邊數(shù)相同時(shí)，多懸掛邊結(jié)構(gòu)的拉普拉斯度為k-1的頂點(diǎn)個(gè)數(shù)比單懸掛邊結(jié)構(gòu)的多.因此，只需考慮多懸掛邊結(jié)構(gòu)的特殊情況，拉普拉斯度為k-1的頂點(diǎn)個(gè)數(shù)最多時(shí)，h(H )取最大值.多懸掛邊結(jié)構(gòu)的單圈k-均勻超圖中最多有n-2個(gè)頂點(diǎn)的拉普拉斯度為k-1，其拉普拉斯度序列π(H**)=[2k-3(2),k-1(n-2)].因此

由上述討論，可得

{2m(k-1)log2[2(k-1)]+

(n-m)(k-1)log2(k-1)}

證畢

2.3 雙圈k-均勻超圖

設(shè)H*是拉普拉斯度序列π(H*)=[2k-2(m+1),k-1(n-m-1)]的雙圈k-均勻超圖.H**是拉普拉斯度序列π(H**)=[mk-m,2k-3(2),k-1(n-3)]的雙圈k-均勻超圖.

證明使用反證法證明.設(shè)HH*獲得最小的基于拉普拉斯度的圖熵.則至少存在一個(gè)頂點(diǎn)u滿足δu≥3k-3.令e為包含頂點(diǎn)u的非懸掛邊，C=v1e1v2e2…etvt+1(vt+1=v1)是H中的一個(gè)圈.而滿足條件的頂點(diǎn)u有以下兩種情況.

情況1：頂點(diǎn)u在圈C中，即u∈C.

不失一般性，設(shè)邊e=e1，頂點(diǎn)u∈e1.找一條從頂點(diǎn)u開(kāi)始最長(zhǎng)的超路P=uf1u1f2…fsus，其中頂點(diǎn)ui?C且邊f(xié)i?C(i=1,2,…,s).顯然，頂點(diǎn)us的拉普拉斯度δus=k-1.

若頂點(diǎn)u=v1或者v2.不失一般性，設(shè)頂點(diǎn)u=v1，則拉普拉斯度δv1≥3.令H′=(V(H),E(H′))為邊集E(H′)=(E(H)﹨{e1})∪{e′1}的雙圈k-均勻(k≥3)超圖，其中邊e′1=(e1﹨{v1})∪{us}.根據(jù)引理1，可得h(H)>h(H′)，矛盾.

若頂點(diǎn)u≠v1,v2.設(shè)f1是一條不包含頂點(diǎn)u的邊，其中f1≠e1.令H ′=(V(H ),E(H ′))為邊集E(H ′)=(E(H )﹨{e1,f1})∪{e′1,f′1}的超圖，其中邊e′1=(e1﹨{v1})∪{us}，f′1=(f1﹨{u})∪{v1}.根據(jù)引理1，可得h(H )>h(H ′)，矛盾.

情況2：頂點(diǎn)u不在圈C中，即u?C.

找一條從頂點(diǎn)u開(kāi)始最長(zhǎng)超路P=vf1u1f2…fsus(頂點(diǎn)ui?C，邊f(xié)i?C，i=1,2,…,s)，其中頂點(diǎn)v∈ei，i∈{1,2,…,t}，邊f(xié)j-1∩fj={u}，j∈{1,2,…,s}.令H′=(V(H),E(H′))為邊集E(H′)=(E(H)﹨{e1,fj})∪{e′1,f′j}的雙圈k-均勻(k≥3)超圖，其中邊e′1=(e1﹨{vi})∪{us}，邊f(xié)′j=(fj﹨{u})∪{vi}.根據(jù)引理1，可得h(H)>h(H′)，矛盾.

由上述討論可得，當(dāng)且僅當(dāng)H ?H*時(shí)，h(H)取到最小值，即

h(H )≥(m+1)(2k-2)log2(2k-2)+

(n-m-1)(k-1)log2(k-1)

設(shè)H ?H**獲得最大的基于拉普拉斯度的圖熵，令u是拉普拉斯度最大的頂點(diǎn).而頂點(diǎn)u有以下3種情況.

情況1：若邊e∈E(H )有k-1個(gè)懸掛點(diǎn)，則頂點(diǎn)u∈e.

相反的，設(shè)e∈E(H )有k-1個(gè)懸掛點(diǎn)，但頂點(diǎn)u?e.令w∈e是拉普拉斯度δw≥2(k-1)的頂點(diǎn).令H ′=(V(H ),E(H ′))為邊集E(H′)=(E(H )﹨{e})∪{e′}的雙圈k-均勻(k≥3)超圖，其中邊e′=(e﹨{w})∪{u}.根據(jù)引理2，得h(H )

情況2:u是H中所有圈的一個(gè)公共點(diǎn).

相反的，設(shè)H中的圈C=v1e1v2e2…etvt+1(vt+1=v1)不包含頂點(diǎn)u.找一條從頂點(diǎn)v開(kāi)始的超路P=vf1u1f2…us-1fsu(頂點(diǎn)ui?C，i=1,2,…,s-1，邊f(xié)j?C，j=1,2,…,s)，其中頂點(diǎn)v∈ei，i∈{1,2,…,t}.令H ′=(V(H ),E(H ′))為邊集E(H ′)=(E(H )﹨{ei,f1})∪{e′i,f′1}的雙圈k-均勻(k≥3)超圖，其中邊e′i=(ei﹨{vi})∪{u}，邊f(xié)′1=(f1﹨{v})∪{vi}.根據(jù)引理2，可得h(H )

情況3：對(duì)任意在H中的圈C，都有構(gòu)成圈C的邊數(shù)|e(C)|=2，其中e(C)={e|e∈C}.

用C=v1e1v2e2…etvt+1(vt+1=v1)表示H中的一個(gè)圈.不失一般性，設(shè)頂點(diǎn)v2≠u∈e1(u和v1不是同一個(gè)頂點(diǎn)).若構(gòu)成圈C的邊數(shù)|e(C)|≥3，則令H′=(V(H),E(H′))為邊集E(H′)=(E(H)﹨{e2})∪{e′2}的雙圈k-均勻(k≥3)超圖，其中e′2=(e2﹨{v2})∪{u}.根據(jù)引理2，可得h(H )

由上述討論可得，當(dāng)且僅當(dāng)H?H**時(shí)，h(H)取到最大值，即h(H )≤(mk-k)log2(mk-k)+(4k-6)log2(2k-3)+(n-3)(k-1)log2(k-1).

證畢

根據(jù)引理6對(duì)雙圈k-均勻(k≥3)超圖的h(H)的討論，可得如下結(jié)論.

當(dāng)且僅當(dāng)H ?H**時(shí)，左側(cè)等式成立.當(dāng)且僅當(dāng)H ? H*，右側(cè)等式成立.

2.4 k-均勻化學(xué)超樹(shù)

設(shè)T*是頂點(diǎn)數(shù)為n，邊數(shù)為m=3a+i+1(i=0,1,2)，拉普拉斯度序列為π(T*)=[4k-4(a),(i+1)(k-1),k-1(n-a-1)]的k-均勻化學(xué)超樹(shù).

證明h(T)滿足引理5中的結(jié)論.因此，拉普拉斯度為k-1的頂點(diǎn)個(gè)數(shù)越多，則h(T)越大.拉普拉斯度序列的前r項(xiàng)越大，則h(T)越大.化學(xué)超樹(shù)的最大度不超過(guò)4，即拉普拉斯度最大為4k-4.若存在一對(duì)頂點(diǎn)vi和vj，其拉普拉斯度分別是δi和δj，使4(k-1)>δi≥δj≥2(k-1).通過(guò)引理2中的移邊操作，頂點(diǎn)vi和vj的拉普拉斯度分別變?yōu)棣膇+(k-1)和δj-(k-1)，得到了一個(gè)新的化學(xué)超樹(shù)T′.根據(jù)引理2，可以證明h(T)

因此

1) 若m-1≡0(mod 3)，則

2) 若m-1≡0(mod 3)，則

3) 若m-1≡0(mod 3)，則

證畢

當(dāng)且僅當(dāng)T∈T*時(shí)，左側(cè)等式成立.當(dāng)且僅當(dāng)T ?Pn時(shí)，右側(cè)等式成立.

證明注意到超路Pn也是化學(xué)超樹(shù).根據(jù)定理1，可得化學(xué)超樹(shù)T ?Pn時(shí)，Iδ(T )取到最大值.因此

證畢

3 結(jié)論

本文將簡(jiǎn)單圖的一些結(jié)果推廣到k-均勻超圖.利用超圖拉普拉斯度的性質(zhì)，通過(guò)移邊操作，分別得到了在k-均勻超樹(shù)、單圈k-均勻超圖、雙圈k-均勻超圖以及k-均勻化學(xué)超樹(shù)中基于拉普拉斯度的圖熵極值，并確定了極值圖.在接下來(lái)的工作中，還可以將上述結(jié)論推廣到n圈k-均勻超圖，但由于n圈k-均勻超圖中存在許多復(fù)雜的結(jié)構(gòu)，所以拉普拉斯度序列將是非常多變的，這是研究中的一個(gè)難點(diǎn).