4501
правка
Раскраска графа: различия между версиями
Перейти к навигации
Перейти к поиску
м
→Векторная раскраска графов
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 38: | Строка 38: | ||
'''Утверждение 1 (сложность векторной раскраски [15])'''. Пусть <math>\varepsilon > 0 \; </math>. Если граф G имеет векторную k-раскраску, то векторная <math>(k + \varepsilon) \;</math> -раскраска графа G может быть построена за время, полиномиальное относительно <math>n \; </math> и <math>log(1 / \varepsilon) \; </math> | '''Утверждение 1 (сложность векторной раскраски [15])'''. Пусть <math>\varepsilon > 0 \; </math>. Если граф G имеет векторную k-раскраску, то векторная <math>(k + \varepsilon) \;</math> -раскраска графа G может быть построена за время, полиномиальное относительно <math>n \; </math> и <math>log(1 / \varepsilon) \; </math>. | ||