4501
правка
Раскраска графа: различия между версиями
Перейти к навигации
Перейти к поиску
→Векторная раскраска графов
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 35: | Строка 35: | ||
Здесь мы предполагаем, что V = [1... n] и что векторы | Здесь мы предполагаем, что V = [1... n] и что векторы <math>\{ v_i \}_{i=1}^n </math> принадлежат к <math>R_n \; </math>. Каждый k-раскрашиваемый граф также является векторно k-раскрашиваемым. Это можно показать, если идентифицировать каждый цветовой класс с одной вершиной идеального (k-1)-мерного симплекса с центром в источнике. Более того, в отличие от хроматического числа, векторная k-раскраска, если таковая существует, может быть найдена за полиномиальное время при помощи алгоритмов полуопределенного программирования (с поправкой на произвольно малую ошибку в скалярных произведениях). | ||
'''Утверждение 1 (сложность векторной раскраски [15])'''. Пусть <math>\varepsilon > 0 \; </math>. Если граф G имеет векторную k-раскраску, то векторная <math>(k + \varepsilon) \;</math> -раскраска графа G может быть построена за время, полиномиальное относительно <math>n \; </math> и <math>log(1 / \varepsilon) \; </math> | |||
Можно усилить определение 1, чтобы получить другое понятие векторной раскраски и векторного хроматического числа. | Можно усилить определение 1, чтобы получить другое понятие векторной раскраски и векторного хроматического числа. | ||
при условии: | <math>\overrightarrow{\chi}_2 (G)</math> Минимизировать k | ||
1 | |||
при условии: <math>\langle v_i, v_j \rangle = - \frac {1} {k - 1} \; \; \forall (i, j) \in E</math> | |||
<math>\langle v_i, v_j \rangle = 1 \; \; \forall i \in V</math>. | |||
1 | |||
i | |||
<math>\overrightarrow{\chi}_3 (G)</math> Минимизировать k | |||
при условии: <math>\langle v_i, v_j \rangle = - \frac {1} {k - 1} \; \; \forall (i, j) \in E</math> | |||
<math>\langle v_i, v_j \rangle \ge - \frac {1} {k - 1} \; \; \forall i, j \in V</math> | |||
<math>\langle v_i, v_j \rangle = 1 \; \; \forall i \in V</math>. | |||