Русская Википедия:Число Ловаса
Число Ловаса графа — вещественное число, которое является верхней границей ёмкости Шеннона этого графа. Число Ловаса известно также под именем тета-функция Ловаса и обычно обозначается как <math>\vartheta(G) </math>. Это число впервые ввёл Ласло Ловас в статье 1979 года «On the Shannon Capacity of a Graph» («О ёмкости Шеннона графа»)Шаблон:Sfn.
Определение
Пусть G = (V, E) — граф с n вершинами. Упорядоченное множество n единичных векторов <math>U=(u_i \mid i \in V) \subset \mathbf{R}^N</math> называется ортонормальным представлением графа G в RN, если ui и uj ортогональны, когда вершины i и j несмежны в G:
- <math>
u_i^\mathrm{T} u_j =
\begin{cases}
1, & i=j, \\
0, & ij \notin E.
\end{cases}
</math> Ясно, что любой граф допускает ортонормальное представление с N=n (просто вершинам сопоставим вершины различных векторов Шаблон:Не переведено 5 пространства Rn, хотя такое представление не является правильным (произведение векторов равно нулю, даже если соответствующие вершины смежны), разве что граф вообще не имеет рёбер. Правильное представление для N = n возможно, однако, в общем случае, N может быть существенно меньше числа вершин n.
Число Ловаса ϑ графа G определяется следующим образом:
- <math>
\vartheta(G)=\min_{c, U} \max_{i \in V} \frac{1}{(c^\mathrm{T} u_i)^2},
</math> где c — единичный вектор в RN, а U — ортонормальное представление G в RN. Здесь минимизация неявно предполагается и по размерности N, однако без потери общности достаточно предположить N = n [1]. Интуитивно, это соответствует минимизации половины угла кругового конуса, содержащего векторы ортонормального представления графа G. Если оптимальный угол равен <math>\phi</math>, то <math>\theta(G)=1/cos^2(\phi) </math> и c соответствует оси симметрии конусаШаблон:Sfn.
Эквивалентные выражения
Пусть G = (V, E) — граф с n вершинами. Пусть A — n × n симметричные матрицы, такие, что aij = 1 всякий раз, когда i = j или <math>ij \notin E</math>, и пусть <math>\lambda_{max}(A) </math> обозначает наибольшее собственное значение матрицы A. Тогда альтернативным способом вычисления числа Ловаса графа G является следующееШаблон:Sfn:
- <math>
\vartheta(G)=\min_A \lambda_\max(A).
</math>
Следующий метод является двойственным к предыдущему. Пусть B —n × n симметричные положительно определённые матрицы, такие, что bij = 0 для любого <math>ij \in E</math> и Tr(B) = 1. Здесь Tr обозначает след (сумма диагональных элементов), а J является n × n матрицей единиц. ТогдаШаблон:Sfn
- <math>
\vartheta(G)=\max_B \operatorname{Tr}(BJ).
</math> Tr(BJ) просто равна сумме всех элементов B.
Число Ловаса можно вычислить в терминах дополнения графа Шаблон:Overline. Пусть d — единичный вектор и <math>V = (v_i \mid i \in V) </math> — ортонормальное представление графа Шаблон:OverlineШаблон:Sfn.
- <math>
\vartheta(G)=\max_{d,V} \sum_{i \in V} (d^\mathrm{T} v_i)^2.
</math>
Значение ϑ для некоторых хорошо известных графов
| Граф | Значение <math>\theta</math> |
|---|---|
| Полный граф | <math> \vartheta(K_n)=1 </math> |
| Граф без рёбер | <math> \vartheta(\bar{K}_n)=n </math> |
| Граф пятиугольника | <math> \vartheta(C_5)=\sqrt{5} </math> |
| Циклы | <math> \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} </math> |
| Граф Петерсена | <math> \vartheta(KG_{5,2})=4 </math> |
| Кнезеровские графы | <math> \vartheta(KG_{n,k})=\binom{n-1}{k-1} </math> |
| Многодольные графы | <math> \vartheta(K_{n_1,\dots,n_k})=\max_{1 \leq i \leq k} n_i </math> |
Свойства
Если <math>G \boxtimes H</math> обозначает сильное произведение графов графов G и H, тогдаШаблон:Sfn
- <math> \vartheta(G \boxtimes H)=\vartheta(G) \vartheta(H). </math>
Если Шаблон:Overline является дополнением графа G, тоШаблон:Sfn
- <math> \vartheta(G) \vartheta(\bar{G}) \geq n, </math>
и неравенство превращается в равенство, если граф G вершинно-транзитивен.
«Теорема сэндвича» Ловаса
«Теорема сэндвича» Ловаса утверждает, что число Ловаса лежит между двумя другими числами, вычисление которых является NP-полной задачейШаблон:Sfn. Точнее,
- <math> \omega(G) \leq \vartheta(\bar{G}) \leq \chi(G), </math>
где <math>\omega(G)</math> — кликовое число графа G (размер наибольшей клики) а <math>\chi(G)</math> — хроматическое число графа G (наименьшее число цветов, необходимое для раскраски вершин G так, что никакие две смежные вершины не раскрашены в один цвет). Однако значение <math>\theta(G)</math> может быть аппроксимировано методом эллипсоидов за время, ограниченное полиномиальной функцией от числа вершин графа GШаблон:Sfn.
Связь с ёмкостью Шеннона
Ёмкость Шеннона графа G определяется следующим образом:
- <math>
\Theta(G)
=\sup_k \sqrt[k]{\alpha(G^k)} =\lim_{k \rightarrow \infty} \sqrt[k]{\alpha(G^k)}, </math> где <math>\alpha(G) </math> является числом независимости графа G (размер наибольшего независимого множества графа G), а Gk — сильное произведение графа G самого на себя k раз. Ясно, что <math>\Theta(G) \ge \alpha(G)</math>. Однако число Ловаса даёт верхнюю границу ёмкости Шеннона графаШаблон:Sfn, поскольку
- <math> \alpha(G) \leq \Theta(G) \leq \vartheta(G). </math>
Например, пусть C5 , пятиугольник, — граф малоразличимости сообщений для канала. С момента появления статьи ШеннонаШаблон:Sfn встала задача определения значения <math>\Theta(C_5)</math>. Ловас первымШаблон:Sfn установил, что <math>\Theta(C_5) = \sqrt{5}</math>.
Ясно, что <math>\Theta(C_5) \ge \alpha(C_5) = 2</math>. Однако, <math>\alpha(C_5^2) \ge 5</math>, поскольку «11», «23», «35», «54», «42» являются пятью взаимно различимыми сообщениями (образующие независимое множество из пяти вершин в сильном квадрате графа C5, т.е. <math>C_5 \boxtimes C_5</math>), так что <math>\Theta(C_5) \ge \sqrt{5}</math>.
Чтобы показать, что эта граница является точной, пусть <math>U = (u_1, u_2, u_3, u4, u_5) </math> будет ортонормальным представлением пятиугольника:
- <math>
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}
</math> И пусть <math>c = (1, 0, 0)</math>. Если использовать эти величины в определении числа Ловаса, мы получим <math>\theta(C_5) \le \sqrt{5}</math>. Следовательно, <math>\Theta(C_5) = \sqrt{5}</math>.
Однако существуют графы, для которых число Ловаса и ёмкость Шеннона отличаются, так что число Ловаса не может быть использовано, в общем случае, для вычисления точной ёмкости Шеннона для графаШаблон:Sfn.
Квантовая физика
Число Ловаса было обобщено для «некоммутативных графов» в контексте Шаблон:Не переведено 5Шаблон:Sfn. Число Ловаса возникает также в Шаблон:Не переведено 5 при попытке объяснить мощность квантовых компьютеровШаблон:Sfn.
Примечания
Литература
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Книга
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Книга
- Шаблон:Книга, Лекции.
- Шаблон:Статья
Ссылки
- ↑ Если N > n, то можно всегда получить меньшее значение, ограничив c подпространством, натянутым на вектора ui, размерность которого не превышает n.
