盧鵬麗, 薛玉龍

(蘭州理工大學 計算機與通信學院, 甘肅 蘭州 730050)

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

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

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

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

定義2[2]超樹是連通、無圈的超圖.

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

超樹(hypertree)的每條邊上最多有兩個非懸掛點，本文討論的超樹均是hypertree.與化學樹的定義類似，定義化學超樹是最大度不超過4的超樹.

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

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

1 基本理論

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

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

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

引理1設超圖H上存在兩個頂點vi和vj使得拉普拉斯度δi≥δj+2(k-1)，其中頂點vi∈e∈E(H )，頂點vj?e.若超圖H通過定義7的移邊操作，移動邊e上的頂點vi到頂點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設超圖H上存在兩個頂點vi和vj使得拉普拉斯度δi≥δj≥2(k-1)，其中頂點vj∈e∈E(H)，頂點vi?e.若超圖H通過定義7的移邊操作，移動邊e上的頂點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]設H ′是單圈k-均勻超圖H經(jīng)過移邊操作后得到的超圖.若H ′是連通的，則H ′仍然是單圈k-均勻超圖.

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

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

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

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

2.1 k-均勻超樹

證畢

2.2 單圈k-均勻超圖

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

當且僅當H ?H**時，左側等式成立.當且僅當H ?H*時，右側等式成立.

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

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

當圈上包含的邊數(shù)相同時，多懸掛邊結構的拉普拉斯度為k-1的頂點個數(shù)比單懸掛邊結構的多.因此，只需考慮多懸掛邊結構的特殊情況，拉普拉斯度為k-1的頂點個數(shù)最多時，h(H )取最大值.多懸掛邊結構的單圈k-均勻超圖中最多有n-2個頂點的拉普拉斯度為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-均勻超圖

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

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

情況1：頂點u在圈C中，即u∈C.

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

若頂點u=v1或者v2.不失一般性，設頂點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′)，矛盾.

若頂點u≠v1,v2.設f1是一條不包含頂點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：頂點u不在圈C中，即u?C.

找一條從頂點u開始最長超路P=vf1u1f2…fsus(頂點ui?C，邊f(xié)i?C，i=1,2,…,s)，其中頂點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′)，矛盾.

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

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

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

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

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

相反的，設e∈E(H )有k-1個懸掛點，但頂點u?e.令w∈e是拉普拉斯度δw≥2(k-1)的頂點.令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中所有圈的一個公共點.

相反的，設H中的圈C=v1e1v2e2…etvt+1(vt+1=v1)不包含頂點u.找一條從頂點v開始的超路P=vf1u1f2…us-1fsu(頂點ui?C，i=1,2,…,s-1，邊f(xié)j?C，j=1,2,…,s)，其中頂點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：對任意在H中的圈C，都有構成圈C的邊數(shù)|e(C)|=2，其中e(C)={e|e∈C}.

用C=v1e1v2e2…etvt+1(vt+1=v1)表示H中的一個圈.不失一般性，設頂點v2≠u∈e1(u和v1不是同一個頂點).若構成圈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 )

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

證畢

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

當且僅當H ?H**時，左側等式成立.當且僅當H ? H*，右側等式成立.

2.4 k-均勻化學超樹

設T*是頂點數(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-均勻化學超樹.

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

因此

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

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

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

證畢

當且僅當T∈T*時，左側等式成立.當且僅當T ?Pn時，右側等式成立.

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

證畢

3 結論

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