主题
Search

香农容量

DOWNLOAD Mathematica Notebook下载 Wolfram Notebook

设 alpha(G) 表示图 G 的独立数。那么香农容量 Theta(G)，有时也记为 c(G)，G 的定义为

Theta(G)=lim_(k->infty)[alpha(G□AdjustmentBox[x, BoxMargins -> {{-0.65, 0.13913}, {-0.5, 0.5}}, BoxBaselineShift -> -0.1]...□AdjustmentBox[x, BoxMargins -> {{-0.65, 0.13913}, {-0.5, 0.5}}, BoxBaselineShift -> -0.1]G_()_(k))]^(1/k),

其中 □AdjustmentBox[x, BoxMargins -> {{-0.65, 0.13913}, {-0.5, 0.5}}, BoxBaselineShift -> -0.1] 表示图强积 (Shannon 1956, Alon and Lubetzky 2006)。香农容量是一个重要的信息论参数，因为它代表了由图 G 表示的通信模型中字母表的有效大小 (Alon 1998)。

Theta(G) 的下界是独立数

alpha(G)<=Theta(G)

上界是 Lovász 数 和 Haemers 数。

一般来说，香农容量很难计算 (Brimkovet al. 2000)。事实上，循环图 C_5 的香农容量直到 1979 年才被确定为 Theta(C_5)=sqrt(5) (Lovász 1979)，而 C_7 的香农容量可能是极值组合学中最臭名昭著的未解决问题之一 (Bohman 2003)。

Lovász (1979) 表明，(n,r)-Kneser 图的香农容量是 (n-1; r-1)，顶点传递 自补图（包括所有 Paley 图）G 的香农容量是 sqrt(|V(G)|)，Petersen 图的香农容量是 4。

所有香农容量已知的图都在 k=1（即在其独立数处；例如，完美图）、k=2（例如，自补 顶点传递图 - 包括 Paley 图）达到其容量，否则在任何 k 值下都无法达到（例如，循环图 C_5 与单例图的图并集）(Alon and Lubetzky 2006)。

另请参阅

图强积, Haemers 数, 独立数, Lovász 数, 完美图, 夹逼定理

使用 Wolfram|Alpha 探索

参考文献

Alon, N. “显式拉姆齐图和正交标签。” Elec. J. Combin. 1, No. R12, 1-8, 1994。Alon, N. “并集的香农容量。” Combinatorica 18, 301-310, 1998。Alon, N. 和 Lubetzky, E. “图的香农容量及其幂的独立数。” IEEE Trans. Inform. Th. 52, 2172-2176, 2006。Bohman, T. “奇数循环的香农容量的极限定理。I。” Proc. Amer. Math. Soc. 131, 3559-3569, 2003。Bohman, T. 和 Holzman, R. “奇数循环的补集的香农容量的非平凡下界。” IEEE Trans. Inform. Th. 49, 721-722, 2003。Brimkov, V. E.; Codenotti, B.; Crespi, V.; 和 Leoncini, M. “关于某些循环图的 Lovász 数。” 在 算法和复杂性。2000 年 3 月 1 日至 3 日在罗马举行的第 4 届意大利会议 (CIAC 2000) 的论文集 (Ed. G. Bongiovanni, G. Gambosi, 和 R. Petreschi)。柏林：施普林格出版社，pp. 291-305, 2000。Haemers, W. “图的香农容量的上限。” 在 图论中的代数方法。 匈牙利塞格德：pp. 267-272, 1978。Haemers, W. “关于 Lovász 关于图的香农容量的一些问题。” IEEE Trans. Inform. Th. 25, 231-232, 1979。Knuth, D. E. “夹逼定理。” Electronic J. Combinatorics 1, No. 1, A1, 1-48, 1994。 http://www.combinatorics.org/Volume_1/Abstracts/v1i1a1.html。Lovász, L. “关于图的香农容量。” IEEE Trans. Inform. Th. IT-25, 1-7, 1979。Riis, S. “图熵、网络编码和猜测。” 2007 年 11 月 27 日。 http://arxiv.org/abs/0711.4175v1。Schrijver, A. “Delsarte 和 Lovász 界限的比较。” IEEE Trans. Inform. Th. 25, 425-429, 1979。Shannon, C. E. “噪声信道的零误差容量。” IRE Trans. Inform. Th. 2, 8-19, 1956。van Lint, J. H. 和 Wilson, R. M. 组合学课程。 纽约：剑桥大学出版社，1992 年。

在 Wolfram|Alpha 中引用

香农容量

请这样引用

Weisstein, Eric W. “香农容量。” 来自 MathWorld--Wolfram Web 资源。 https://mathworld.net.cn/ShannonCapacity.html

主题分类