Онлайн-алгоритм раскраски интервалов: различия между версиями

'''Теорема 1. Пусть имеется граф интервалов, который выдается в режиме онлайн вместе с его реализацией. Любой онлайновый алгоритм использует не менее <math>3 \omega -2</math> цвета для раскраски графа, и существует алгоритм, который достигает этой границы.'''

После создания каждой фазы некоторые участки прямой сжимаются в отдельные точки. Пусть дана точка <math>p</math>, являющаяся результатом сжатия интервала <math>[a, b]</math>. Каждый представленный в прошлом интервал, содержащийся в <math>[a, b]</math>, также сжимается в <math>p</math>, и поэтому такая точка наследует список цветов, который не может получить ни один содержащий ее интервал. Это сделано для простоты доказательства и означает, что для данной точки <math>p</math>, которая является результатом сжатия, либо содержатся все интервалы, которые были сжаты в эту точку, либо она не пересекается ни с одним из них.