Число Ловаса

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

Определение

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

${\displaystyle 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 определяется следующим образом:

${\displaystyle \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. Если оптимальный угол равен ${\displaystyle \phi }$, то ${\displaystyle \theta (G)=1/cos^{2}(\phi )}$ и c соответствует оси симметрии конуса^[3].

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

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

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

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

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

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

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

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

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

Граф	Значение ${\displaystyle \theta }$
Полный граф	${\displaystyle \vartheta (K_{n})=1}$
Граф без рёбер	${\displaystyle \vartheta ({\bar {K}}_{n})=n}$
Граф пятиугольника	${\displaystyle \vartheta (C_{5})={\sqrt {5}}}$
Циклы	${\displaystyle \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}}}$
Граф Петерсена	${\displaystyle \vartheta (KG_{5,2})=4}$
Кнезеровские графы	${\displaystyle \vartheta (KG_{n,k})={\binom {n-1}{k-1}}}$
Многодольные графы	${\displaystyle \vartheta (K_{n_{1},\dots ,n_{k}})=\max _{1\leq i\leq k}n_{i}}$

Свойства

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

${\displaystyle \vartheta (G\boxtimes H)=\vartheta (G)\vartheta (H).}$

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

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

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

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

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

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

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

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

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

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

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

${\displaystyle \alpha (G)\leq \Theta (G)\leq \vartheta (G).}$

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

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

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

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

${\displaystyle 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}}}$

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

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

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

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