主題
Search

Lovász 數

下載 Mathematica 筆記本下載 Wolfram 筆記本

圖 G 的 Lovász 數 theta(G)，有時也稱為 G 的 theta 函式，由 Lovász (1979) 引入，其明確目標是估計圖的 夏農容量。設 G 為一個圖，A 為實矩陣族 A=(a_(ij))，使得如果 i 和 j 在 G 中相鄰，則 a_(ij)=0，其中其他元素不受約束。令 A 的特徵值表示為 lambda_1(A)>=lambda_2(A)>=...>=lambda_n(A)。那麼

theta(G)=max_(A in A)[1-(lambda_1(A))/(lambda_n(A))]
(1)

(Lovász 1979, Knuth 1994, Brimkov et al. 2000).

一個等價的定義考慮實矩陣族 B=(b_(ij)) B，使得如果 i=j 或 j 和 i 在 G 中相鄰，則 b_(ij)=0，其他元素不受約束。那麼

theta(G)=min_(B in B)lambda_1(B).
(2)

設 theta(G) 為圖 圖 G 的 Lovász 數。那麼

omega(G)<=theta(G^_)<=chi(G),
(3)

其中 omega(G) 是 團數，chi(G) 是 色數。這是 夾逼定理。它可以透過改變圖補的角色來重寫，得到

omega(G^_)<=theta(G)<=chi(G^_),
(4)

可以使用 omega(G^_)=alpha(G) （其中 alpha 是獨立數）和 theta(G)=chi(G^_) （團覆蓋數）寫成

alpha(G)<=theta(G)<=theta(G).
(5)

儘管在確定 theta(G) 的問題上做了大量工作，但對於有趣的特殊圖的顯式值仍然是一個開放問題 (Brimkov et al. 2000)。然而，對於幾種簡單圖族，theta(G) 的顯式公式是已知的。例如，對於 迴圈圖 C_n，其中 n>=3 且為奇數，

theta(C_n)=(ncos(pi/n))/(1+cos(pi/n))
(6)

(Lovász 1979, Brimkov et al. 2000).

自補圖 頂點傳遞圖（包括 Paley 圖）具有 theta(G)=sqrt(V(G))，Kneser 圖 K(n,r) 具有

theta(K(n,r))=(n-1; r-1)
(7)

(Lovász 1979).

Fung (2011) 給出了 Keller 圖 G_1, G_2, ..., 的 Lovász 數，分別為 4, 6, 28/3, 2^4, 2^5, ....

下表給出了一些特殊情況。

圖 Gtheta(G)
雞尾酒會圖 K_(n×2)2
完全圖 K_n1
完全 k-部圖 K_(n_1,...,n_k)max_(1<=i<=k)n_i
迴圈圖 C_n{n for n=1; (ncos(pi/n))/(1+cos(pi/n)) for n>=3 odd; n/2 for n even
空圖 K^__nn
Kneser 圖 K(n,r)(n-1; r-1)
Paley 圖sqrt(V(G))
迴圈圖 C_5sqrt(5)
Petersen 圖 P4

Brimkov et al. (2000) 確定了四次 迴圈圖 的附加閉合形式，即

theta(Ci_(1,2)(n))=n{1-(1/2-cos(ax)-cos[x(a+1)])/([cos(ax)-1][cos(ax+1)-1])} theta(Ci_(1,3)(n)) =n{1-(cos^2y-cosycos(bx)+cos^2(bx)-1)/((cosy+1)[cos(bx)-1][1-cosy+cos(bx)])}
(8)

對於奇數 n，其中

x=(2pi)/n
(9)
y=pi/n
(10)
a=|_n/3_|
(11)
b=[(n-3)/6],
(12)

|_z_| 是 向下取整函式，[z] 是 向上取整函式。這些是公式的特殊情況

theta(Ci_(1,j)(n))=min_(x,y)max_(i=0,1,...(n-1)/2)f_i(x,y),
(13)

其中

f_0(x,y)=n+2x+2y
(14)
f_i(x,y)=2xcos((2pii)/n)+2ycos((2piij)/n),
(15)

Lovász 數滿足

theta(G□AdjustmentBox[x, BoxMargins -> {{-0.65, 0.13913}, {-0.5, 0.5}}, BoxBaselineShift -> -0.1]H)<=theta(G)theta(H),
(16)

其中 G□AdjustmentBox[x, BoxMargins -> {{-0.65, 0.13913}, {-0.5, 0.5}}, BoxBaselineShift -> -0.1]H 表示 圖的強積 (Lovász 1979)。此外，如果 G 是 頂點傳遞 的，那麼

theta(G)theta(G^_)=n,
(17)

其中 G^_ 表示 G 的 圖補。

Haemers 數 有時比 Lovász 數能更好地限制 夏農容量。

參見

團數, 著色, Haemers 數, 夾逼定理, 夏農容量

使用 探索

參考文獻

Brimkov, V. E.; Codenotti, B.; Crespi, V.; and Leoncini, M. "On the Lovász Number of Certain Circulant Graphs." In Algorithms and Complexity. Papers from the 4th Italian Conference (CIAC 2000) Held in Rome, March 1-3, 2000 (Ed. G. Bongiovanni, G. Gambosi, and R. Petreschi). Berlin: Springer-Verlag, pp. 291-305, 2000.Fung, M. "The Lovász Number of the Keller Graphs." Master thesis. Universiteit Leiden: Mathematisch Instituut, 2011.Knuth, D. E. "The Sandwich Theorem." Electronic J. Combinatorics 1, No. 1, A1, 1-48, 1994. http://www.combinatorics.org/Volume_1/Abstracts/v1i1a1.html.Lovász, L. "On the Shannon Capacity of a Graph." IEEE Trans. Inform. Th. IT-25, 1-7, 1979.Skarakis, C. "The Sandwich Theorem." §4.2.3 in "Convex Optimization: Theory and Practice." MSc dissertation. York, UK: Department of Mathematics, University of York, pp. 43-46, Aug. 22, 2008. http://keithbriggs.info/documents/Skarakis_MSc.pdf.

在 上被引用

Lovász 數

引用為

Weisstein, Eric W. "Lovász 數。" 來自 Web 資源。 https://mathworld.tw/LovaszNumber.html

主題分類