Введение
Функция в алгебраической теории графов
Хроматический полином — это графовый полином, изучаемый в алгебраической теории графов, области математики. Он подсчитывает количество раскрасок графа как функцию от числа цветов и был первоначально определен Джорджем Дэвидом Биркоффом для исследования задачи о четырёх цветах. Он был обобщён до полинома Тютте Хасслером Уитни и У. Т. Тютте, что связало его с моделью Поттса в статистической физике.
История
Джордж Дэвид Биркофф ввел хроматический полином в 1912 году, определив его первоначально только для планарных графов, в попытке доказать теорему о четырех красках. Если обозначает количество правильных раскрасок графа G с использованием k цветов, то можно было бы доказать теорему о четырех красках, показав для всех планарных графов G. Таким образом, он надеялся применить мощные инструменты анализа и алгебры для изучения корней полиномов к комбинаторной задаче раскраски. Хасслер Уитни обобщил полином Биркоффа с планарных графов на общие графы в 1932 году. В 1968 году Рональд К. Рид задался вопросом, какие полиномы являются хроматическими полиномами для каких-либо графов – вопрос, который до сих пор остается открытым, – и ввел понятие хроматически эквивалентных графов. Сегодня хроматические полиномы являются одним из центральных объектов алгебраической теории графов.
Определение
Для графа G, подсчитывает количество его (собственных) раскрасок вершин k цветами. Другие часто используемые обозначения включают , , или . Существует единственный полином , который при вычислении для любого целого числа k ≥ 0 совпадает с ; он называется хроматическим полиномом графа G.
Например, чтобы раскрасить путь на 3 вершинах с помощью k цветов, можно выбрать любой из k цветов для первой вершины, любой из оставшихся k-1 цветов для второй вершины и, наконец, для третьей вершины, любой из k-1 цветов, отличных от цвета второй вершины. Следовательно, является числом k-раскрасок пути. Для переменной x (не обязательно целого числа) мы получаем (Раскраски, различающиеся только перестановкой цветов или автоморфизмами графа G, считаются различными.)
Хроматическая эквивалентность
Два графа называются хроматически эквивалентными, если у них один и тот же хроматический полином. Изоморфные графы имеют один и тот же хроматический полином, но неизоморфные графы могут быть хроматически эквивалентными. Например, все деревья на n вершинах имеют один и тот же хроматический полином. В частности, он является хроматическим полиномом как для графа «коготь», так и для пути на 4 вершинах. Граф называется хроматически уникальным, если он определяется своим хроматическим полиномом с точностью до изоморфизма. Иными словами, если G хроматически уникален, то равенство хроматических полиномов G и H подразумевает, что G и H изоморфны. Все циклические графы хроматически уникальны.
Категоризация
Хроматический полином категорифицируется теорией гомологии, тесно связанной с гомологией Хованова.
Эффективные алгоритмы
Для некоторых основных классов графов известны замкнутые формулы для хроматического полинома. Например, это верно для деревьев и клик, как указано в таблице выше. Алгоритмы полиномиального времени известны для вычисления хроматического полинома для более широких классов графов, включая хордальные графы и графы с ограниченной шириной клики. Последний класс включает кографы и графы с ограниченной шириной дерева, такие как внешнепланарные графы.
Снижение
Рекуррентное соотношение удаления-сжатия предоставляет способ вычисления хроматического полинома, называемый алгоритмом удаления-сжатия. В первой форме (с минусом) рекурсия завершается на множестве пустых графов. Во второй форме (с плюсом) она завершается на множестве полных графов. Это является основой для многих алгоритмов раскраски графов. Функция ChromaticPolynomial в пакете Combinatorica компьютерной системы алгебры Mathematica использует вторую рекурсию, если граф плотный, и первую рекурсию, если граф разреженный. В худшем случае время работы любой из формул удовлетворяет тому же рекуррентному соотношению, что и числа Фибоначчи, поэтому в худшем случае алгоритм выполняется за время, которое отличается от времени работы в пределах полиномиального множителя
на графе с n вершинами и m ребрами. Анализ можно улучшить до полиномиального множителя числа остовных деревьев входного графа. На практике используются стратегии ветвей и границ и отбраковка изоморфизма графов, чтобы избежать некоторых рекурсивных вызовов, а время работы зависит от эвристики, используемой для выбора пары вершин.
Метод кубика
Существует естественная геометрическая интерпретация раскраски графов, основанная на том, что раскраска графа, рассматриваемая как присвоение натуральных чисел каждой вершине, является вектором в целочисленной решетке. Совпадение цветов двух вершин и эквивалентно равенству их координат в векторе раскраски, поэтому каждое ребро можно связать с гиперплоскостью вида. Множество таких гиперплоскостей для заданного графа называется его графической аранжировкой. Правильные раскраски графа – это точки решетки, избегающие запрещенных гиперплоскостей. При ограничении набором цветов, точки решетки содержатся в кубе. В этом контексте хроматический полином подсчитывает количество точек решетки в этом кубе, избегающих графическую аранжировку.