Номер Ловаша

В теории графов число Ловаса графа — это действительное число , которое является верхней границей емкости Шеннона графа. Она также известна как тэта-функция Ловаса и обычно обозначается $\vartheta (G)$, используя рукописную форму греческой буквы тета, чтобы контрастировать с вертикальной тетой, используемой для обозначения способности Шеннона. Эта величина была впервые введена Ласло Ловасом в его статье 1979 года «О шенноновской емкости графа» .

Точные численные аппроксимации этого числа можно вычислить за полиномиальное время с помощью полуопределенного программирования и метода эллипсоидов . Число Ловаса дополнения любого графа находится между хроматическим числом и кликовым числом графа и может использоваться для вычисления этих чисел на графах, для которых они равны, включая идеальные графы .

Определение

Позволять $G=(V,E)$ быть графиком на $n$ вершины. Заказанный набор $n$ единичные векторы $U=(u_{i}\mid i\in V)\subset \mathbb {R} ^{N}$ называется представлением ортонормированным $G$ в $\mathbb {R} ^{N}$, если $u_{i}$ и $u_{j}$ ортогональны, если вершины $i$ и $j$ не являются соседними в $G$: $$u_{i}^{\mathrm {T} }u_{j}={\begin{cases}1,&{\text{if }}i=j,\\0,&{\text{if }}ij\notin E.\end{cases}}$$ Очевидно, что каждый граф допускает ортонормированное представление с $N=n$: просто представьте вершины различными векторами из стандартного базиса $\mathbb {R} ^{N}$. В зависимости от графика можно было бы принять $N$ значительно меньше числа вершин $n$.

Число Ловаса $\vartheta$ графа $G$ определяется следующим образом: $$\vartheta (G)=\min _{c,U}\max _{i\in V}{\frac {1}{(c^{\mathrm {T} }u_{i})^{2}}},$$ где $c$ является единичным вектором в $\mathbb {R} ^{N}$ и $U$ является ортонормированным представлением $G$ в $\mathbb {R} ^{N}$. Здесь неявно минимизация осуществляется и по размерности $N$, однако без ограничения общности достаточно рассмотреть $N=n$. Интуитивно это соответствует минимизации половины угла конуса вращения , содержащего все представляющие векторы ортонормированного представления $G$. Если оптимальный угол $\phi$, затем $\vartheta (G)=1/\cos ^{2}\phi$ и $c$ соответствует оси симметрии конуса.

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

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

Следующий метод двойственен предыдущему. Позволять $B$ диапазон по всему $n\times n$ симметричные положительно полуопределенные матрицы такие, что $b_{ij}=0$ всякий раз, когда вершины $i$ и $j$ смежны и такие, что след (сумма диагональных элементов) $B$ является $\operatorname {Tr} (B)=1$. Позволять $J$ быть $n\times n$ матрица из единиц . Затем $$\vartheta (G)=\max _{B}\operatorname {Tr} (BJ).$$ Здесь, $\operatorname {Tr} (BJ)$ это просто сумма всех записей $B$.

Число Ловаса можно также вычислить с помощью графа дополнений. ${\bar {G}}$. Позволять $d$ быть единичным вектором и $U=(u_{i}\mid i\in V)$ быть ортонормированным представлением ${\bar {G}}$. Затем $$\vartheta (G)=\max _{d,U}\sum _{i\in V}(d^{\mathrm {T} }u_{i})^{2}.$$

Ценность известных графиков

Число Ловаса было рассчитано для следующих графиков:

График	Номер Ловаша
Полный график	$\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)}}&{\text{for odd }}n,\\{\frac {n}{2}}&{\text{for even }}n\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).$$

Если ${\bar {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$ так, чтобы никакие две соседние вершины не были окрашены в один и тот же цвет).

Стоимость $\vartheta (G)$ может быть сформулирована как полуопределенная программа и численно аппроксимирована методом эллипсоида за время, ограниченное полиномом от числа вершин графа G . Для совершенных графов хроматическое число и кликовое число равны и, следовательно, оба равны $\vartheta ({\bar {G}})$. Вычислив приближение $\vartheta ({\bar {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_{5}$, пятиугольник . Со времени появления оригинальной статьи Шеннона (1956) проблема определения значения $\Theta (C_{5})$. Впервые было установлено Ловасом (1979), что $\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_{5}$), таким образом $\Theta (C_{5})\geq {\sqrt {5}}$.

Чтобы показать, что эта оценка точна, пусть $U=(u_{1},\dots ,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)$. Используя этот выбор в первоначальном определении числа Ловаса, мы получаем $\vartheta (C_{5})\leq {\sqrt {5}}$. Следовательно, $\Theta (C_{5})={\sqrt {5}}$.

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

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

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

См. также

• Функция Тардоса — монотонная аппроксимация числа Ловаса графа дополнений , которая может быть вычислена за полиномиальное время и использовалась для доказательства нижних оценок сложности монотонной схемы .

Ссылки

• Кабельо, Адан; Северини, Симоне ; Винтер, Андреас (27 января 2014 г.), «Теоретико-графовый подход к квантовым корреляциям» , Physical Review Letters , 112 (4): 040401, arXiv : 1401.7081 , doi : 10.1103/PhysRevLett.112.040401 , PMID   24580419 , S2CID   34998358
• Дуань, Руняо; Северини, Симоне ; Винтер, Андреас (2013), «Связь с нулевой ошибкой через квантовые каналы, некоммутативные графы и квантовую ϑ-функцию Ловаса», IEEE Transactions on Information Theory , 59 (2): 1164–1174, arXiv : 1002.2514 , doi : 10.1109 /ТИТ.2012.2221677 , S2CID   4690143
• Гретшель, Мартин ; Ловас, Ласло ; Шрийвер, Александр (1981), «Метод эллипсоида и его последствия в комбинаторной оптимизации» (PDF) , Combinatorica , 1 (2): 169–197, doi : 10.1007/BF02579273 , S2CID   43787103 , заархивировано из оригинала (PDF) на 18 июля 2011 г.
• Гретшель, Мартин ; Ловас, Ласло ; Шрийвер, Александр (1993), Геометрические алгоритмы и комбинаторная оптимизация , Алгоритмы и комбинаторика, том. 2 (2-е изд.), Springer-Verlag, Берлин, номер номера : 10.1007/978-3-642-78240-4 , ISBN.  978-3-642-78242-8 , МР   1261419 , стр. 285
• Хемерс, Виллем Х. (1979), «О некоторых проблемах Ловаса, касающихся емкости Шеннона графа» , IEEE Transactions on Information Theory , 25 (2): 231–232, doi : 10.1109/tit.1979.1056027 , заархивировано из оригинал от 5 марта 2012 г.
• Ховард, Марк; Уоллман, Джоэл; Вейч, Виктор; Эмерсон, Джозеф (19 июня 2014 г.), «Контекстуальность обеспечивает «магию» квантовых вычислений», Nature , 510 (7505): 351–5, arXiv : 1401.4174 , Bibcode : 2014Natur.510..351H , doi : 10.1038/nature13460 , ПМИД   24919152 , S2CID   4463585
• Кнут, Дональд Э. (1994), «Теорема о сэндвиче», Electronic Journal of Combinatorics , 1 : A1, arXiv : math/9312214 , doi : 10.37236/1193
• Ловас, Ласло (1979), «О емкости графа по Шеннону», IEEE Transactions on Information Theory , IT-25 (1): 1–7, doi : 10.1109/tit.1979.1055985
• Ловас, Ласло (1986), «Глава 3.2: Хроматическое число, клики и совершенные графы», Алгоритмическая теория чисел, графов и выпуклости , Общество промышленной и прикладной математики , стр. 75 , ISBN  978-0-89871-203-2
• Ловас, Ласло (1995–2001), Полуопределенные программы и комбинаторная оптимизация (конспекты лекций)
• Риддл, Марсия Линг (2003), Сэндвич-теорема и расчет тета-функции для нескольких графов (дипломная работа магистра), Университет Бригама Янга, hdl : 1877/etd181
• Шеннон, Клод (1956), «Пропускная способность зашумленного канала с нулевой ошибкой», IRE Transactions on Information Theory , 2 (3): 8–19, doi : 10.1109/TIT.1956.1056798
• Тодд, Майк; Чунг, Син-Шуэн (21 февраля 2012 г.), «Лекция 9: Формулировки SDP тета-функции Ловаса», Конспект лекций для OR6327, Полуопределенное программирование (PDF) , Корнельский университет

Внешние ссылки

• Вайсштейн, Эрик В. , « Число Ловаса » (« Сэндвич-теорема ») в MathWorld .