主题
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 数, 夹逼定理, 香农容量

使用 Wolfram|Alpha 探索

参考文献

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.

在 Wolfram|Alpha 上被引用

Lovász 数

引用为

Weisstein, Eric W. "Lovász 数。" 来自 MathWorld--Wolfram Web 资源。 https://mathworld.net.cn/LovaszNumber.html

主题分类