Раскраска графа: различия между версиями
Перейти к навигации
Перейти к поиску
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 63: | Строка 63: | ||
== Основные результаты == | == Основные результаты == | ||
Предположим, что граф G имеет n вершин и максимальную степень | Предположим, что граф G имеет <math>n \; </math> вершин и максимальную степень <math>\Delta \; </math>. Нотации <math>\tilde{O} (\cdot) \; </math> и <math>\tilde{\Omega} (\cdot) \; </math> используются для подавления полилогарифмических множителей. Основной результат Карджера, Мотвани и Судана [15] заключается в следующем: | ||
Теорема 1 ([15]) Если % (G) = k, то граф G может быть раскрашен за полиномиальное время при помощи min{6{Al~2lk), б(и1~3/(/с+1))} цветов. | '''Теорема 1 ([15]) Если % (G) = k, то граф G может быть раскрашен за полиномиальное время при помощи min{6{Al~2lk), б(и1~3/(/с+1))} цветов.''' | ||
| Строка 107: | Строка 107: | ||
Векторная раскраска, включая 9-функцию Ловаса и ее варианты, также активно изучалась в контексте алгоритмов аппроксимации и для других задач – таких как аппроксимация <math>\alpha (G) \; </math>, аппроксимация задачи минимального вершинного покрытия и комбинаторная оптимизация в контексте случайных графов. | Векторная раскраска, включая 9-функцию Ловаса и ее варианты, также активно изучалась в контексте алгоритмов аппроксимации и для других задач – таких как аппроксимация <math>\alpha (G) \; </math>, аппроксимация задачи минимального вершинного покрытия и комбинаторная оптимизация в контексте случайных графов. | ||
== Применение == | == Применение == | ||