4501
правка
Раскраска графа: различия между версиями
Перейти к навигации
Перейти к поиску
м
→Векторная раскраска графов
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 19: | Строка 19: | ||
== Векторная раскраска графов == | == Векторная раскраска графов == | ||
Все алгоритмы, достигающие наилучших соотношений для приближенной раскраски при малом значении <math>\chi (G) \; </math> [1, 3, 13, 15], основываются на идее векторной раскраски, предложенной Карджером, Мотвани и Суданом [15] | Все алгоритмы, достигающие наилучших соотношений для приближенной раскраски при малом значении <math>\chi (G) \; </math> [1, 3, 13, 15], основываются на идее [[векторная раскраска графа|векторной раскраски]], предложенной Карджером, Мотвани и Суданом [15]. | ||
(Векторная раскраска, предложенная в [15], тесно связана с <math>\theta</math>-функцией Ловаса [19]. Эта связь будет обсуждаться ниже). | |||
Определение 1. Векторная k-раскраска графа заключается в присваивании вершинам графа единичных векторов, таких, что для каждой дуги скалярное произведение векторов, присвоенных ее конечным точкам, не превышает (в том смысле, что оно может только быть более отрицательным). | '''Определение 1.''' Векторная k-раскраска графа заключается в присваивании вершинам графа единичных векторов, таких, что для каждой дуги скалярное произведение векторов, присвоенных ее конечным точкам, не превышает -1/(k - 1) (в том смысле, что оно может только быть более отрицательным). | ||
| Строка 35: | Строка 36: | ||
Здесь мы предполагаем, что V = [1... n] и что векторы fvigni=1 принадлежат к Rn. Каждый k-раскрашиваемый граф также является векторно k-раскрашиваемым. Это можно показать, если идентифицировать каждый цветовой класс с одной вершиной идеального (k-1)-мерного симплекса с центром в источнике. Более того, в отличие от хроматического числа, векторная k-раскраска, если таковая существует, может быть найдена за полиномиальное время при помощи алгоритмов полуопределенного программирования (с поправкой на произвольно малую ошибку в скалярных произведениях). | Здесь мы предполагаем, что V = [1... n] и что векторы fvigni=1 принадлежат к Rn. Каждый k-раскрашиваемый граф также является векторно k-раскрашиваемым. Это можно показать, если идентифицировать каждый цветовой класс с одной вершиной идеального (k-1)-мерного симплекса с центром в источнике. Более того, в отличие от хроматического числа, векторная k-раскраска, если таковая существует, может быть найдена за полиномиальное время при помощи алгоритмов полуопределенного программирования (с поправкой на произвольно малую ошибку в скалярных произведениях). | ||
| Строка 55: | Строка 56: | ||
Функция Xi{G), вычисляющая точное векторное хроматическое число графа G, равна 9-функции Ловаса на G [15, 19], где G – дополнение графа G. Функция X i(G) называется сильным векторным хроматическим числом. Аналог утверждения 1 верен как для ~X2(G), так и для ~x*3(G). Обозначим размер максимальной клики графа G как !(G); тогда имеет место 5l2(G)<l3(G)< <math>\chi (G) \; </math>. | Функция Xi{G), вычисляющая точное векторное хроматическое число графа G, равна 9-функции Ловаса на G [15, 19], где G – дополнение графа G. Функция X i(G) называется сильным векторным хроматическим числом. Аналог утверждения 1 верен как для ~X2(G), так и для ~x*3(G). Обозначим размер максимальной клики графа G как !(G); тогда имеет место 5l2(G)<l3(G)< <math>\chi (G) \; </math>. | ||
== Основные результаты == | == Основные результаты == | ||