Число Ловаса

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

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

Определение

[править | править код]

Пусть G = (VE) — граф с n вершинами. Упорядоченное множество n единичных векторов называется ортонормальным представлением графа G в RN, если ui и uj ортогональны, когда вершины i и j несмежны в G:

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

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

где c — единичный вектор в RN, а U — ортонормальное представление G в RN. Здесь минимизация неявно предполагается и по размерности N, однако без потери общности достаточно предположить N = n [2]. Интуитивно, это соответствует минимизации половины угла кругового конуса, содержащего векторы ортонормального представления графа G. Если оптимальный угол равен , то и c соответствует оси симметрии конуса[3].

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

[править | править код]

Пусть G = (VE) — граф с n вершинами. Пусть An × n симметричные матрицы, такие, что aij = 1 всякий раз, когда i = j или , и пусть обозначает наибольшее собственное значение матрицы A. Тогда альтернативным способом вычисления числа Ловаса графа G является следующее[4]:

Следующий метод является двойственным к предыдущему. Пусть Bn × n симметричные положительно определённые матрицы, такие, что bij = 0 для любого и Tr(B) = 1. Здесь Tr обозначает след (сумма диагональных элементов), а J является n × n матрицей единиц. Тогда[5]

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

Число Ловаса можно вычислить в терминах дополнения графа G. Пусть d — единичный вектор и — ортонормальное представление графа G[6].

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

[править | править код]
Граф Значение
Полный граф
Граф без рёбер
Граф пятиугольника
Циклы
Граф Петерсена
Кнезеровские графы
Многодольные графы

Если обозначает сильное произведение графов графов G и H, тогда[7]

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

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

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

[править | править код]

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

где кликовое число графа G (размер наибольшей клики) а хроматическое число графа G (наименьшее число цветов, необходимое для раскраски вершин G так, что никакие две смежные вершины не раскрашены в один цвет). Однако значение может быть аппроксимировано методом эллипсоидов за время, ограниченное полиномиальной функцией от числа вершин графа G[10].

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

[править | править код]

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

где является числом независимости графа G (размер наибольшего независимого множества графа G), а Gkсильное произведение графа G самого на себя k раз. Ясно, что . Однако число Ловаса даёт верхнюю границу ёмкости Шеннона графа[11], поскольку

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

Например, пусть C5 , пятиугольник, — граф малоразличимости сообщений для канала. С момента появления статьи Шеннона[12] встала задача определения значения . Ловас первым[1] установил, что .

Ясно, что . Однако, , поскольку «11», «23», «35», «54», «42» являются пятью взаимно различимыми сообщениями (образующие независимое множество из пяти вершин в сильном квадрате графа C5, т.е. ), так что .

Чтобы показать, что эта граница является точной, пусть будет ортонормальным представлением пятиугольника:

И пусть . Если использовать эти величины в определении числа Ловаса, мы получим . Следовательно, .

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

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

[править | править код]

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

Примечания

[править | править код]
  1. 1 2 Lovász, 1979.
  2. Если N > n, то можно всегда получить меньшее значение, ограничив c подпространством, натянутым на вектора ui, размерность которого не превышает n.
  3. Lovász, 1995–2001, с. 28 Proposition 5.1.
  4. Lovász, 1979, с. Theorem 3.
  5. Lovász, 1979, с. Theorem 4.
  6. Lovász, 1979, с. Theorem 5.
  7. Lovász, 1979, с. Lemma 2, Theorem 7.
  8. Lovász, 1979, с. Corollary 2, Theorem 8.
  9. Knuth, 1994.
  10. Grötschel, Lovász, Schrijver, 1981.
  11. Lovász, 1979, с. Theorem 1.
  12. Shannon, 1956.
  13. Haemers, 1979.
  14. Duan, Severini, Winter, 2013.
  15. Howard, Wallman, Veitch, Emerson, 2014, с. 351.

Литература

[править | править код]