Число Ловаса

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

Определение

Пусть 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 . Интуитивно, это соответствует минимизации половины угла кругового конуса, содержащего векторы ортонормального представления графа G. Если оптимальный угол равен $\phi$, то $\theta (G)=1/cos^{2}(\phi )$ и c соответствует оси симметрии конуса.

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

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

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

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

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

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

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

$\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, тогда

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

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

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

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

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

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

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

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

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

Ёмкость Шеннона графа 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)$. Однако число Ловаса даёт верхнюю границу ёмкости Шеннона графа, поскольку

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

Граф пятиугольника

Например, пусть C₅ , пятиугольник, — граф малоразличимости сообщений для канала. С момента появления статьи Шеннона встала задача определения значения $\Theta (C_{5})$. Ловас первым установил, что $\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}}$.

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

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

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

Ссылки

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