Число Ловаса

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

Определение

Пусть G = (V, E) — граф с n вершинами. Упорядоченное множество n единичных векторов U = ( u i ∣ i ∈ V ) ⊂ R N {displaystyle U=(u_{i}mid iin V)subset mathbf {R} ^{N}} называется ортонормальным представлением графа G в RN, если ui и uj ортогональны, когда вершины i и j несмежны в G:

u i T u j = { 1 , i = j , 0 , i j ∉ E . {displaystyle u_{i}^{mathrm {T} }u_{j}={egin{cases}1,&i=j,,&ij otin E.end{cases}}}

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

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

ϑ ( G ) = min c , U max i ∈ V 1 ( c T u i ) 2 , {displaystyle vartheta (G)=min _{c,U}max _{iin V}{frac {1}{(c^{mathrm {T} }u_{i})^{2}}},}

где c — единичный вектор в RN, а U — ортонормальное представление G в RN. Здесь минимизация неявно предполагается и по размерности N, однако без потери общности достаточно предположить N = n . Интуитивно, это соответствует минимизации половины угла кругового конуса, содержащего векторы ортонормального представления графа G. Если оптимальный угол равен ϕ {displaystyle phi } , то θ ( G ) = 1 / c o s 2 ( ϕ ) {displaystyle heta (G)=1/cos^{2}(phi )} и c соответствует оси симметрии конуса.

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

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

ϑ ( G ) = min A λ max ( A ) . {displaystyle vartheta (G)=min _{A}lambda _{max(}A).}

Следующий метод является двойственным к предыдущему. Пусть B —n × n симметричные положительно определённые матрицы, такие, что bij = 0 для любого i j ∈ E {displaystyle ijin E} и Tr(B) = 1. Здесь Tr обозначает след (сумма диагональных элементов), а J является n × n матрицей единиц. Тогда

ϑ ( G ) = max B Tr ⁡ ( B J ) . {displaystyle vartheta (G)=max _{B}operatorname {Tr} (BJ).}

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

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

ϑ ( G ) = max d , V ∑ i ∈ V ( d T v i ) 2 . {displaystyle vartheta (G)=max _{d,V}sum _{iin V}(d^{mathrm {T} }v_{i})^{2}.}

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

Свойства

Если G ⊠ H {displaystyle Goxtimes H} обозначает сильное произведение графов графов G и H, тогда

ϑ ( G ⊠ H ) = ϑ ( G ) ϑ ( H ) . {displaystyle vartheta (Goxtimes H)=vartheta (G)vartheta (H).}

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

ϑ ( G ) ϑ ( G ¯ ) ≥ n , {displaystyle vartheta (G)vartheta ({ar {G}})geq n,}

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

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

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

ω ( G ) ≤ ϑ ( G ¯ ) ≤ χ ( G ) , {displaystyle omega (G)leq vartheta ({ar {G}})leq chi (G),}

где ω ( G ) {displaystyle omega (G)} — кликовое число графа G (размер наибольшей клики) а χ ( G ) {displaystyle chi (G)} — хроматическое число графа G (наименьшее число цветов, необходимое для раскраски вершин G так, что никакие две смежные вершины не раскрашены в один цвет). Однако значение θ ( G ) {displaystyle heta (G)} может быть аппроксимировано методом эллипсоидов за время, ограниченное полиномиальной функцией от числа вершин графа G.

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

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

Θ ( G ) = sup k α ( G k ) k = lim k → ∞ α ( G k ) k , {displaystyle Theta (G)=sup _{k}{sqrt[{k}]{alpha (G^{k})}}=lim _{k ightarrow infty }{sqrt[{k}]{alpha (G^{k})}},}

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

α ( G ) ≤ Θ ( G ) ≤ ϑ ( G ) . {displaystyle alpha (G)leq Theta (G)leq vartheta (G).}

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

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

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

u k = ( cos ⁡ θ sin ⁡ θ cos ⁡ φ k sin ⁡ θ sin ⁡ φ k ) , cos ⁡ θ = 1 5 4 , φ k = 2 π k 5 {displaystyle u_{k}={egin{pmatrix}cos { heta }sin { heta }cos {varphi _{k}}sin { heta }sin {varphi _{k}}end{pmatrix}},quad cos { heta }={frac {1}{sqrt[{4}]{5}}},quad varphi _{k}={frac {2pi k}{5}}}

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

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

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

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