Число Ловаса (Cnvlk Lkfgvg)

Число Ловаса графа — вещественное число, которое является верхней границей ёмкости Шеннона этого графа. Число Ловаса известно также под именем тета-функция Ловаса и обычно обозначается как $\vartheta (G)$ . Это число впервые ввёл Ласло Ловас в статье 1979 года «On the Shannon Capacity of a Graph» («О ёмкости Шеннона графа»)^[1].

Определение

Пусть G = (V, E) — граф с n вершинами. Упорядоченное множество n единичных векторов $U=(u_{i}\mid i\in V)\subset \mathbf {R} ^{N}$ называется ортонормальным представлением графа G в R^N, если u_i и u_j ортогональны, когда вершины i и j несмежны в G:

u_{i}^{\mathrm {T} }u_{j}={\begin{cases}1,&i=j,\\0,&ij\notin E.\end{cases}}

Ясно, что любой граф допускает ортонормальное представление с N=n (просто вершинам сопоставим вершины различных векторов стандартного базиса^[англ.] пространства Rⁿ, хотя такое представление не является правильным (произведение векторов равно нулю, даже если соответствующие вершины смежны), разве что граф вообще не имеет рёбер. Правильное представление для N = n возможно, однако, в общем случае, N может быть существенно меньше числа вершин n.

Число Ловаса ϑ графа G определяется следующим образом:

\vartheta (G)=\min _{c,U}\max _{i\in V}{\frac {1}{(c^{\mathrm {T} }u_{i})^{2}}},

где c — единичный вектор в R^N, а U — ортонормальное представление G в R^N. Здесь минимизация неявно предполагается и по размерности N, однако без потери общности достаточно предположить N = n ^[2]. Интуитивно, это соответствует минимизации половины угла кругового конуса, содержащего векторы ортонормального представления графа G. Если оптимальный угол равен $\phi$ , то $\theta (G)=1/cos^{2}(\phi )$ и c соответствует оси симметрии конуса^[3].

Эквивалентные выражения

Пусть G = (V, E) — граф с n вершинами. Пусть A — n × n симметричные матрицы, такие, что a_ij = 1 всякий раз, когда i = j или $ij\notin E$ , и пусть $\lambda _{max}(A)$ обозначает наибольшее собственное значение матрицы A. Тогда альтернативным способом вычисления числа Ловаса графа G является следующее^[4]:

\vartheta (G)=\min _{A}\lambda _{\max(}A).

Следующий метод является двойственным к предыдущему. Пусть B —n × n симметричные положительно определённые матрицы, такие, что b_ij = 0 для любого $ij\in E$ и Tr(B) = 1. Здесь Tr обозначает след (сумма диагональных элементов), а J является n × n матрицей единиц. Тогда^[5]

\vartheta (G)=\max _{B}\operatorname {Tr} (BJ).

Tr(BJ) просто равна сумме всех элементов B.

Число Ловаса можно вычислить в терминах дополнения графа G. Пусть d — единичный вектор и $V=(v_{i}\mid i\in V)$ — ортонормальное представление графа G^[6].

\vartheta (G)=\max _{d,V}\sum _{i\in V}(d^{\mathrm {T} }v_{i})^{2}.

Значение ϑ для некоторых хорошо известных графов

Граф	Значение $\theta$
Полный граф	$\vartheta (K_{n})=1$
Граф без рёбер	$\vartheta ({\bar {K}}_{n})=n$
Граф пятиугольника	$\vartheta (C_{5})={\sqrt {5}}$
Циклы	$\vartheta (C_{n})={\begin{cases}{\frac {n\cos(\pi /n)}{1+\cos(\pi /n)}}&n\equiv 1\mod 2,\\{\frac {n}{2}}&n\equiv 0\mod 2\end{cases}}$
Граф Петерсена	$\vartheta (KG_{5,2})=4$
Кнезеровские графы	$\vartheta (KG_{n,k})={\binom {n-1}{k-1}}$
Многодольные графы	$\vartheta (K_{n_{1},\dots ,n_{k}})=\max _{1\leq i\leq k}n_{i}$

Свойства

Если $G\boxtimes H$ обозначает сильное произведение графов графов G и H, тогда^[7]

\vartheta (G\boxtimes H)=\vartheta (G)\vartheta (H).

Если G является дополнением графа G, то^[8]

\vartheta (G)\vartheta ({\bar {G}})\geq n,

и неравенство превращается в равенство, если граф G вершинно-транзитивен.

«Теорема сэндвича» Ловаса

«Теорема сэндвича» Ловаса утверждает, что число Ловаса лежит между двумя другими числами, вычисление которых является NP-полной задачей^[9]. Точнее,

\omega (G)\leq \vartheta ({\bar {G}})\leq \chi (G),

где $\omega (G)$ — кликовое число графа G (размер наибольшей клики) а $\chi (G)$ — хроматическое число графа G (наименьшее число цветов, необходимое для раскраски вершин G так, что никакие две смежные вершины не раскрашены в один цвет). Однако значение $\theta (G)$ может быть аппроксимировано методом эллипсоидов за время, ограниченное полиномиальной функцией от числа вершин графа G^[10].

Связь с ёмкостью Шеннона

Ёмкость Шеннона графа G определяется следующим образом:

\Theta (G)=\sup _{k}{\sqrt[{k}]{\alpha (G^{k})}}=\lim _{k\rightarrow \infty }{\sqrt[{k}]{\alpha (G^{k})}},

где $\alpha (G)$ является числом независимости графа G (размер наибольшего независимого множества графа G), а G^k — сильное произведение графа G самого на себя k раз. Ясно, что $\Theta (G)\geq \alpha (G)$ . Однако число Ловаса даёт верхнюю границу ёмкости Шеннона графа^[11], поскольку

\alpha (G)\leq \Theta (G)\leq \vartheta (G).

Например, пусть C₅ , пятиугольник, — граф малоразличимости сообщений для канала. С момента появления статьи Шеннона^[12] встала задача определения значения $\Theta (C_{5})$ . Ловас первым^[1] установил, что $\Theta (C_{5})={\sqrt {5}}$ .

Ясно, что $\Theta (C_{5})\geq \alpha (C_{5})=2$ . Однако, $\alpha (C_{5}^{2})\geq 5$ , поскольку «11», «23», «35», «54», «42» являются пятью взаимно различимыми сообщениями (образующие независимое множество из пяти вершин в сильном квадрате графа C₅, т.е. $C_{5}\boxtimes C_{5}$ ), так что $\Theta (C_{5})\geq {\sqrt {5}}$ .

Чтобы показать, что эта граница является точной, пусть $U=(u_{1},u_{2},u_{3},u4,u_{5})$ будет ортонормальным представлением пятиугольника:

u_{k}={\begin{pmatrix}\cos {\theta }\\\sin {\theta }\cos {\varphi _{k}}\\\sin {\theta }\sin {\varphi _{k}}\end{pmatrix}},\quad \cos {\theta }={\frac {1}{\sqrt[{4}]{5}}},\quad \varphi _{k}={\frac {2\pi k}{5}}

И пусть $c=(1,0,0)$ . Если использовать эти величины в определении числа Ловаса, мы получим $\theta (C_{5})\leq {\sqrt {5}}$ . Следовательно, $\Theta (C_{5})={\sqrt {5}}$ .

Однако существуют графы, для которых число Ловаса и ёмкость Шеннона отличаются, так что число Ловаса не может быть использовано, в общем случае, для вычисления точной ёмкости Шеннона для графа^[13].

Квантовая физика

Число Ловаса было обобщено для «некоммутативных графов» в контексте квантовой связи^[англ.]^[14]. Число Ловаса возникает также в квантовой контекстуальности^[англ.] при попытке объяснить мощность квантовых компьютеров^[15].

Примечания

↑ ¹ ² Lovász, 1979.
↑ Если N > n, то можно всегда получить меньшее значение, ограничив c подпространством, натянутым на вектора u_i, размерность которого не превышает n.
↑ Lovász, 1995–2001, с. 28 Proposition 5.1.
↑ Lovász, 1979, с. Theorem 3.
↑ Lovász, 1979, с. Theorem 4.
↑ Lovász, 1979, с. Theorem 5.
↑ Lovász, 1979, с. Lemma 2, Theorem 7.
↑ Lovász, 1979, с. Corollary 2, Theorem 8.
↑ Knuth, 1994.
↑ Grötschel, Lovász, Schrijver, 1981.
↑ Lovász, 1979, с. Theorem 1.
↑ Shannon, 1956.
↑ Haemers, 1979.
↑ Duan, Severini, Winter, 2013.
↑ Howard, Wallman, Veitch, Emerson, 2014, с. 351.

Литература

Mark Howard, Joel Wallman, Victor Veitch, Joseph Emerson. Contextuality supplies the 'magic' for quantum computation // Nature. — 2014. — Июнь (т. 510). — С. 351. — doi:10.1038/nature13460. — PMID 24919152.
Runyao Duan, Simone Severini, Andreas Winter. Zero-error communication via quantum channels, non-commutative graphs and a quantum Lovász ϑ function // IEEE Trans. Inf. Theory. — 2013. — Т. 59, вып. 2. — С. 1164–1174. — doi:10.1109/TIT.2012.2221677. — arXiv:1002.2514.
Martin Grötschel, László Lovász, Alexander Schrijver. The ellipsoid method and its consequences in combinatorial optimization // Combinatorica. — 1981. — Т. 1, вып. 2. — С. 169–197. — doi:10.1007/BF02579273. Архивировано 18 июля 2011 года.
Martin Grötschel, László Lovász, Alexander Schrijver. Chapter 9.3. Orthonormal Representations // Geometric Algorithms and Combinatorial Optimization. — Springer, 1988. — С. 285. — ISBN 978-0-387-13624-0.
Willem H. Haemers. On Some Problems of Lovász Concerning the Shannon Capacity of a Graph // IEEE Transactions on Information Theory. — 1979. — Т. 25. — С. 231–232. — doi:10.1109/tit.1979.1056027. Архивировано 5 марта 2012 года.
Donald E. Knuth. The sandwich theorem // Electronic Journal of Combinatorics. — 1994. — С. A1. — arXiv:math/9312214.
László Lovász. On the Shannon Capacity of a Graph // IEEE Transactions on Information Theory. — 1979. — Т. IT-25, вып. 1. — С. 1–7. — doi:10.1109/tit.1979.1055985.
László Lovász. Chapter 3.2. Chromatic number, cliques, and perfect graphs // An Algorithmic Theory of Numbers, Graphs and Convexity. — SIAM, 1986. — С. pp. 75. — ISBN 978-0-89871-203-2.
László Lovász. Semidefinite programs and combinatorial optimization. — 1995–2001., Лекции.
- László Lovász. Semidefinite programs and combinatorial optimization // Recent Advances in Algorithms and Combinatorics / Reed, Sales. — 2003.
Claude Shannon. The zero error capacity of a noisy channel // IRE Transactions on Information Theory. — 1956. — Т. 2, вып. 3. — С. 8–19. — doi:10.1109/TIT.1956.1056798.

Ссылки

Weisstein, Eric W. Lovász Number (англ.) на сайте Wolfram MathWorld.
Weisstein, Eric W. Sandwich Theorem (англ.) на сайте Wolfram MathWorld.
Weisstein, Eric W. Shannon Capacity (англ.) на сайте Wolfram MathWorld.

[_dc58a2afa16b78fd-1] ¹ ² Lovász, 1979.

[2] Если N > n, то можно всегда получить меньшее значение, ограничив c подпространством, натянутым на вектора u_i, размерность которого не превышает n.

[_c5e9b6b17fd15357-3] Lovász, 1995–2001, с. 28 Proposition 5.1.

[_4eff3eb9b6d71588-4] Lovász, 1979, с. Theorem 3.

[_4eff3eb9b6d7158f-5] Lovász, 1979, с. Theorem 4.

[_4eff3eb9b6d7158e-6] Lovász, 1979, с. Theorem 5.

[_7dddbcc8ac7816ac-7] Lovász, 1979, с. Lemma 2, Theorem 7.

[_48fbd28acf21b51a-8] Lovász, 1979, с. Corollary 2, Theorem 8.

[_d5b73caa59a8710e-9] Knuth, 1994.

[_6244f98682969a71-10] Grötschel, Lovász, Schrijver, 1981.

[_4eff3eb9b6d7158a-11] Lovász, 1979, с. Theorem 1.

[_76857528df41e7f3-12] Shannon, 1956.

[_7d47fb7b22f18af2-13] Haemers, 1979.

[_3a28c09de4d51f73-14] Duan, Severini, Winter, 2013.

[_aa754eaac4ce1b92-15] Howard, Wallman, Veitch, Emerson, 2014, с. 351.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]