Число Ловаса

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

Определение

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

$u_i^{\mathrm{T}}{u}_j=\{\begin{array}{cc}1,& i=j,\\ 0,& ij\notin E.\end{array}$

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

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

$\vartheta (G)=\underset{c,U}{\min }\underset{i\in V}{\max }\frac{1}{(c^{\mathrm{T}}{u}_i{)}^2},$

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

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

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

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

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

$\vartheta (G)=\underset{B}{\max }\mathrm{Tr}(BJ).$

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

Число Ловаса можно вычислить в терминах дополнения графа Шаблон:Overline. Пусть d — единичный вектор и $V=(v_i\mid i\in V)$ — ортонормальное представление графа Шаблон:OverlineШаблон:Sfn.

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

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

Граф	Значение $\theta$
Полный граф	$\vartheta (K_n)=1$
Граф без рёбер	$\vartheta ({\overline{K}}_n)=n$
Граф пятиугольника	$\vartheta (C_5)=\sqrt{5}$
Циклы	$\vartheta (C_n)=\{\begin{array}{cc}\frac{n\cos (\pi /n)}{1+\cos (\pi /n)}& n\equiv 1mod2,\\ \frac{n}{2}& n\equiv 0mod2\end{array}$
Граф Петерсена	$\vartheta (K{G}_{5,2})=4$
Кнезеровские графы	$\vartheta (K{G}_{n,k})=(\genfrac{}{}{0ex}{}{n-1}{k-1})$
Многодольные графы	$\vartheta (K_{n_1,\dots ,n_k})=\underset{1\le i\le k}{\max }{n}_i$

Свойства

Если $G⊠H$ обозначает сильное произведение графов графов G и H, тогдаШаблон:Sfn

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

Если Шаблон:Overline является дополнением графа G, тоШаблон:Sfn

$\vartheta (G)\vartheta (\overline{G})\ge n,$

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

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

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

$\omega (G)\le \vartheta (\overline{G})\le \chi (G),$

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

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

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

$\mathrm{\Theta }(G)=\underset{k}{\sup }\sqrt[k]{\alpha (G^k)}=\underset{k\to \mathrm{\infty }}{\lim }\sqrt[k]{\alpha (G^k)},$

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

$\alpha (G)\le \mathrm{\Theta }(G)\le \vartheta (G).$

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

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

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

Чтобы показать, что эта граница является точной, пусть $U=(u_1,u_2,u_3,u4,u_5)$ будет ортонормальным представлением пятиугольника:

$u_k=\left(\begin{array}{c}\cos \theta \\ \sin \theta \cos {\phi }_k\\ \sin \theta \sin {\phi }_k\end{array}\right),\cos \theta =\frac{1}{\sqrt[4]{5}},{\phi }_k=\frac{2\pi k}{5}$

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

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

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

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

Литература

• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Книга
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Книга
• Шаблон:Книга, Лекции.
  • Шаблон:Книга
• Шаблон:Статья

Ссылки

• Шаблон:MathWorld
• Шаблон:MathWorld
• Шаблон:MathWorld