Раскраска графа: различия между версиями

Раскраска графа (посмотреть исходный код)

1 байт добавлено , 17 февраля 2015

м

4430

правок

Версия от 01:30, 17 февраля 2015 (просмотреть исходный код) Irina (обсуждение \| вклад) м (→‎Векторная раскраска графов) ← Предыдущая правка		Версия от 01:32, 17 февраля 2015 (просмотреть исходный код) 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>.