4817
правок
Онлайн-алгоритм раскраски интервалов: различия между версиями
Материал из WEGA
Онлайн-алгоритм раскраски интервалов (посмотреть исходный код)
Версия от 12:08, 20 августа 2025
, 20 август→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 45: | Строка 45: | ||
Далее определяется фаза i < | Далее определяется фаза <math>i < \omega</math>. Фазы строятся таким образом, чтобы в начале фазы <math>i</math> было достаточно большое количество точек, содержащих заданный набор из <math>3 i - 2</math> цветов (интересующие точки). Без потери общности предположим, что это цвета <math>1, ..., 3i - 2</math>, где размер наибольшей клики равен <math>i</math>. Существуют и другие точки, содержащие другие наборы <math>i</math> цветов или наборы не более <math>i - 1</math> цветов. Все эти точки называются пустыми точками. В это время интересующие точки разбиваются на последовательные множества по четыре. | ||
Далее определяются некоторые дополнительные интервалы, увеличивающие размер наибольшей клики ровно на единицу. Пусть дано множество из четырех точек | Далее определяются некоторые дополнительные интервалы, увеличивающие размер наибольшей клики ровно на единицу. Пусть дано множество из четырех точек <math>a_1, a_2, a_3, a_4</math> и пусть <math>b</math> – самая левая пустая точка справа от <math>a_1</math>, между <math>a_1</math> и <math>a_2</math>. Если такой точки не существует, положим <math>b = (a_1 + a_2)/2</math>. Аналогично, пусть <math>c</math> – крайняя правая пустая точка между <math>a_3</math> и <math>a_4</math>, и если такой точки нет, положим <math>c = (a_3 + a_4)/2</math>. Пусть <math>d</math> – точка между <math>a_2</math> и <math>a_3</math>, не являющаяся пустой. Вводятся интервалы <math>I_1 = [a_1, (a_1 + b)/2]</math> и <math>I_2 = [(c + a_4)/2, a_4]</math>. Очевидно, что ни один из них не может получить один из используемых в настоящее время <math>3i - 2</math> цветов. Если они оба получат один и тот же новый цвет, то вводятся интервалы <math>I_3 = [(a_1 + b)/2, d]</math> и <math>I_4 = [d, (c + a_4)/2]</math>. Интервал <math>I_3</math> пересекается с <math>a_2</math> и с <math>I_1</math>. Поэтому он получает еще один дополнительный цвет. Второй интервал <math>I_4</math> пересекается с <math>I_3</math>, <math>a_3</math> и <math>I_2</math>. Поэтому ему присваивается третий новый цвет. Если <math>I_1</math> и <math>I_2</math> получают разные новые цвета, то вводится интервал <math>I_5 = [(a_1 + b)/2, (c + a_4)/2]</math>. Поскольку <math>I_5</math> пересекается с <math>I_1, I_2, a_2, a_3</math>, он должен получить третий новый цвет. Каждый такой интервал <math>[a_1, a_4]</math> сжимается в единственную точку, содержащую <math>3i + 1</math> цветов. Поскольку цветов меньше <math>3\omega</math>, а каждая точка использует ровно <math>3i + 1 < 3 \omega</math> из них, то таких вариантов меньше <math>(3 \omega)!</math> и можно выбрать достаточно большое число точек, имеющих одинаковый набор цветов. Точки, содержащие именно такой набор цветов, становятся интересными точками следующей фазы, а остальные – пустыми точками следующей фазы. Точки, которые являются пустыми точками предыдущих фаз и не содержатся в сжатых интервалах, остаются пустыми. Единственные точки, в которых пересекаются новые интервалы, – это точки, в которых не было предыдущих интервалов, поэтому размер клики увеличивается ровно на 1. | ||
В это время может быть выполнена фаза i + 1. После фазы | В это время может быть выполнена фаза <math>i + 1</math>. После фазы <math>\omega - 1</math> остается не менее <math>3 \omega -2</math> цветов; утверждение доказано. Заметим, что до этой фазы требуется минимальное число в четыре интересных точки. | ||
== Применение == | == Применение == | ||
