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

Задача раскраски интервалов определяется следующим образом. Интервалы на вещественной прямой представляются последовательно один за другим, и онлайновый алгоритм должен присвоить каждому интервалу цвет до появления следующего интервала таким образом, чтобы никакие два пересекающихся интервала не имели одинакового цвета. Цель также заключается в том, чтобы минимизировать количество цветов, используемых для раскраски интервалов. Последняя задача эквивалентна раскраске графов интервалов. Это графы, в представлении (или реализации) которых каждый интервал представляет вершину, а две вершины имеют общее ребро тогда и только тогда, когда они пересекаются. Предполагается, что граф интервалов выдается в онлайновом режиме вместе с его реализацией.

Прежде чем обсуждать онлайн-задачу, необходимо указать некоторые свойства графов интервалов. Существует простой оффлайновый алгоритм, который производит оптимальную раскраску таких графов. Мы говорим, что алгоритм применяет подход First Fit, если каждый раз, когда ему нужно присвоить интервалу цвет, он назначает цвет с наименьшим индексом, который все еще позволяет получить допустимую раскраску. Оптимальный алгоритм просто рассматривает интервалы, отсортированные слева направо по их левым конечным точкам, и применяет подход First Fit. Заметим, что в результирующей раскраске никогда не используется более <math>\omega</math> цветов. И в самом деле, графы интервалов совершенны. //''Граф <math>G</math> является совершенным, если любой индуцированный подграф <math>G</math>, <math>G'</math> (включая <math>G</math>), может быть раскрашен с помощью <math>\omega(G')</math> цветов, где <math>\omega(G')</math> – размер клики наибольшей кардинальности в <math>G'</math>. (Для любого графа <math>\omega</math> является очевидной нижней границей его хроматического числа).''//