Русская Википедия:Хроматический многочлен

Материал из Онлайн справочника
Перейти к навигацииПерейти к поиску

Файл:Chromatic polynomial of all 3-vertex graphs BW.png
Все неизоморфные графы с 3 вершинами и их хроматические многочлены, по часовой стрелке сверху.
Независимое 3-множество: <math>k^3</math>.
Ребро и одна вершина: <math>k^2(k-1)</math>.
3-путь: <math>k(k-1)^2</math>.
3-клика: <math>k(k-1)(k-2)</math>.

Хроматический многочлен — многочлен, изучаемый в алгебраической теории графов, представляющий число раскрасок графа как функцию от числа цветов. Первоначально определён Джорджем Биркгофов для попытки решения на проблемы четырёх красок. Обобщен и систематически изучен Хасслером Уитни, Татт обобщил хроматический многочлен до многочлена Татта, связав его с Шаблон:Не переведено 5 статистической физики.

История

Джордж Биркгоф ввёл хроматический многочлен в 1912 году, определяя его только для планарных графов в попытке доказать теорему о четырёх красках. Если <math>P(G, k)</math> обозначает число правильных раскрасок графа G k цветами, то можно было бы доказать теорему о четырёх красках, показав, что <math>P(G, 4)>0</math> для всех планарных графов G. Таким образом он надеялся использовать мощь математического анализа и алгебры для изучения корней многочленов для изучения комбинаторной задачи раскраски.

Хасслер Уитни обобщил многочлен Биркгофа с планарного случая на графы общего вида в 1932. В 1968 году Рид поднял вопрос: какие многочлены являются хроматическими многочленами для некоторых графов (задача остаётся открытой), и ввёл понятие хроматически эквивалентных графов. В настоящее время хроматические многочлены являются центральными объектами алгебраической теории графовШаблон:Sfn.

Определение

Файл:Chromatic polynomial of all 3-vertex graphs BW with colorings.png
Все правильные раскраски графов с 3 вершинами при использовании kцветов (<math>k=0,1,2,3</math>). Хроматический многочлен каждого графа интерполирует число правильных раскрасок.

Хроматический многочлен графа G считает число правильных раскрасок вершин. Обычно многочлен обозначается как <math>P_G(k)</math>, <math>\chi_G(k)</math>, <math>\pi_G(k)</math> или <math>P(G, k)</math>. Последнее обозначение будем использовать в остальной части статьи.

Например, путь <math>P_3</math> с 3 вершинами не может быть раскрашен в 0 цветов или 1 цветом. Используя 2 цвета граф можно раскрасить двумя способами. Используя 3 цвета граф можно раскрасить 12 способами.

Доступно цветов <math>k</math> 0 1 2 3
Число раскрасок <math>P(P_3, k)</math> 0 0 2 12

Для графа G с n вершинами хроматический многочлен определяется как уникальный интерполирующий многочлен степени, не превосходящей n, проходящий через точки

<math>\left \{ (0, P(G, 0)), (1, P(G, 1)), \cdots, (n, P(G, n)) \right \}.</math>

Если граф G не содержит вершин с петлями, то хроматический многочлен является приведённым многочленом степени в точности n. Фактически, для приведённого выше примера мы имеем

<math>P(P_3, t)= t(t-1)^2, \qquad P(P_3, 3)=12.</math>

Хроматический многочлен включает по меньшей мере столько информации о раскрашиваемости графа G, сколько содержится в хроматическом числе. Более того, хроматическое число является наименьшим положительным целым, при котором хроматический многочлен не обращается в нуль,

<math>\chi (G)=\min\{ k : P(G, k) > 0 \}.</math>

Примеры

Хроматические многочлены для некоторых графов
Треугольник <math>K_3</math> <math>t(t-1)(t-2)</math>
Полный граф <math>K_n</math> <math>t(t-1)(t-2)\cdots(t-(n-1))</math>
Путь <math>P_n</math> <math>t(t-1)^{n-1}</math>
Любое дерево с n вершинами <math>t(t-1)^{n-1}</math>
Цикл <math>C_n</math> <math>(t-1)^n+(-1)^n(t-1)</math>
Граф Петерсена <math>t(t-1)(t-2) \left (t^7-12t^6+67t^5-230t^4+529t^3-814t^2+775t-352 \right)</math>

Свойства

Для фиксированного графа G с n вершинами хроматический многочлен <math>P(G, t)</math> является, фактически, многочленом степени n. По определению, вычисление значения многочлена <math>P(G, k)</math> даёт число k-раскрасок графа G для <math>k=0, 1,\cdots, n</math>. То же самое верно для k > n.

Выражение

<math>(-1)^{|V(G)|} P(G,-1)</math>

даёт число ациклических ориентаций графа GШаблон:Sfn.

Значение производной от многочлена в точке 1, <math>P'(G, 1)</math> равно с точностью до знака хроматическому инварианту <math>\theta(G)</math>.

Если граф G имеет n вершин, m рёбер и c компонент <math>G_1, \cdots, G_c</math>, то

  • Коэффициенты при <math> t^0, \cdots, t^{c-1}</math> равны нулю.
  • Коэффициенты при <math> t^c, \cdots, t^n</math> все ненулевые.
  • Коэффициент при <math>t^n</math> в <math>P(G, t)</math> равен 1.
  • Коэффициент при <math>t^{n-1}</math> в <math>P(G, t)</math> равен <math>-m</math>.
  • Коэффициенты любого хроматического многочлена знакопеременны.
  • Абсолютные значения коэффициентов любого хроматического многочлена образует Шаблон:Не переведено 5Шаблон:Sfn.
  • <math>P(G, t) = P(G_1, t)P(G_2,t) \cdots P(G_c,t)</math>

Граф G с n вершинами является деревом тогда и только тогда, когда

<math>P(G, t) = t(t-1)^{n-1}.</math>

Хроматическая эквивалентность

Файл:Chromatically equivalent graphs.svg
Три графа с хроматическим многочленом, равным <math>(x-2)(x-1)^3x</math>.

Говорят, что два графа хроматически эквивалентны, если они имеют одинаковые хроматические многочлены. Изоморфные графы имеют одинаковые хроматические многочлены, но неизоморфные графы могут быть хроматически эквивалентными. Например, все деревья с n вершинами имеют одинаковые хроматические многочлены:

<math>(x-1)^{n-1}x,</math>

В частности,

<math>(x-1)^3x</math>

является хроматическим многочленом как для клешни, так и для пути с 4 вершинами.

Хроматическая единственность

Граф является хроматически уникальным, если он определяется хроматическим многочленом с точностью до изоморфизма. Другими словами, если граф G хроматически уникален, то из <math>P(G, t) = P(H, t)</math> следует, что G и H изоморфны.

Все циклы хроматически уникальныШаблон:Sfn.

Хроматические корни

Корень (или нуль) хроматического многочлена (называется «хроматическим корнем») — это значение x, для которого <math>P(G, x)=0</math>. Хроматические корни хорошо изучены. Фактически, исходным побуждением Биркгофа для введения хроматического многочлена было показать, что для планарных графов <math>P(G, x)>0</math> для x ≥ 4. Это доказало бы теорему о четырёх красках.

Никакой граф нельзя раскрасить в 0 цветов, так что 0 всегда является хроматическим корнем. Только графы без рёбер могут быть раскрашены в один цвет, так что 1 является хроматическим корнем любого графа, имеющего по меньшей мере одно ребро. С другой стороны, за исключением этих двух случаев, никакой граф не может иметь в качестве хроматического корня вещественное число, меньшее либо равное 32/27Шаблон:Sfn. Результат Татта связывает золотое сечение <math>\phi</math> с изучением хроматических корней, показывая, что хроматические корни существуют очень близко к <math>\phi^2</math> — если <math>G_n</math> является планарной триангуляцией сферы, то

<math>P(G_n,\phi^2) \leq \phi^{5-n}.</math>

В то время как вещественная прямая, таким образом, имеет большие куски, которые не содержат хроматических корней ни для какого графа, любая точка на комплексной плоскости произвольно близка к хроматическому корню в том смысле, что существует бесконечное семейство графов, хроматические корни которых плотны на комплексной плоскостиШаблон:Sfn.

Категоризация

Хроматический многочлен категоризирован с помощью теории гомологий, близко связанной с Шаблон:Не переведено 5Шаблон:Sfn.

Алгоритмы

Шаблон:Карточка Шаблон:Карточка

Вычислительные задачи, связанные с хроматическими многочленами

  • нахождение хроматического многочлена <math>P(G, t)</math> для данного графа G;
  • вычисление <math>P(G, k)</math> в фиксированной точке k для данного графа G.

Первая задача более общая, поскольку, зная коэффициенты <math>P(G, t)</math>, мы можем вычислить значение многочлена в любой точке за полиномиальное время. Вычислительная сложность второй задачи сильно зависит от величины k. Когда k является натуральным числом, задачу можно рассматривать как вычисление количества k-раскрасок данного графа. Например, задача включает подсчёт 3-раскрасок в качестве канонической задачи для изучения сложности подсчёта. Эта задача является полной в классе #P.

Эффективные алгоритмы

Для некоторых базовых классов графов известны явные формулы хроматических многочленов. Например, это верно для деревьев и клик, что показано в таблице выше.

Известны алгоритмы полиномиального времени для вычисления хроматического многочлена для широкого класса графов, в который входят хордальные графыШаблон:Sfn и графы с ограниченной кликовой ширинойШаблон:SfnШаблон:Sfn. Второй из этих классов, в свою очередь, включает кографы и графы с ограниченной древесной шириной, такие как внешнепланарные графы.

В интернете присутствуют лица, пытающиеся решить задачу коллективно, и им помогают активные автономные помощники, особенно для хроматических многочленов высокой степениШаблон:Sfn.

Удаление — стягивание

Рекурсивный способ вычисления хроматического многочлена базируется на стягивании ребра — для пары вершин <math>u</math> и <math>v</math> граф <math>G/uv</math> получается путём слияния двух вершин и удаления ребра между ними. Хроматический многочлен удовлетворяет рекурсивному соотношению

<math>P(G,k)=P(G-uv, k)- P(G/uv,k)</math>,

где <math>u</math> и <math>v</math> являются смежными вершинами и <math>G-uv</math> является графом с удалённым ребром <math>uv</math>. Эквивалентно,

<math>P(G,k)= P(G+uv, k) + P(G/uv,k)</math>

если <math>u</math> и <math>v</math> не смежны и <math>G+uv</math> является графом с добавленным ребром <math>uv</math>. В первой форме рекурсия прекращается на наборе пустых графов. Эти рекуррентные отношения называются также фундаментальной теоремой редукцииШаблон:Sfn. Вопрос Татта о том, какие другие свойства графа удовлетворяют тем же рекуррентным соотношениям, привёл к открытию обобщения хроматического многочлена на две переменные — многочлену Татта.

Выражения дают рекурсивную процедуру, называемую алгоритмом удаления — стягивания, которая является базисом многих алгоритмов раскраски графов. Функция ChromaticPolynomial в системе компьютерной алгебры Mathematica использует вторую рекуррентную формулу если граф плотный, и первую, если граф разреженныйШаблон:Sfn. Худшее время работы для обоих формул удовлетворяет рекуррентному соотношению для чисел Фибоначчи, так что в худшем случае алгоритм работает за время (с точностью до некоторого полиномиального коэффициента)

<math>\phi^{n+m}=\left (\frac{1+\sqrt{5}}{2} \right)^{n+m}\in O\left(1{,}62^{n+m}\right)</math>

на графе с n вершинами и m рёбрамиШаблон:Sfn. Анализ времени работы можно улучшить до полиномиального множителя числа <math>t(G)</math> остовных деревьев входного графаШаблон:Sfn. На практике используется стратегия ветвей и границ вместе с отбрасыванием изоморфных графов, чтобы исключить рекурсивные вызовы, и время зависит от эвристики, используемой при выборе пары вершин (для исключения-стягивания).

Метод куба

Существует естественный геометрический подход к раскраске графов, если заметить, что при назначении натуральных чисел каждой вершине раскраска графов является вектором целочисленной решётки. Поскольку присвоение двум вершинам <math>i</math> и <math>j</math> одного цвета эквивалентно равенству координат <math>i</math> и <math>j</math> в векторе раскраски, каждое ребро можно ассоциировать с гиперплоскостью вида <math>\{x\in R^d:x_i=x_j\}</math>. Набор таких гиперплоскостей для данного графа называется его графической Шаблон:Не переведено 5. Правильная раскраска графа — это раскраска, вектор которой не оказывается на запрещённой плоскости. Ограниченные множеством цветов <math>k</math>, точки решётки попадают в куб <math>[0,k]^n</math>. В этом контексте хроматический многочлен подсчитывает точки решётки в <math>[0,k]</math>-кубе, которые не попадают на графическую конфигурацию.

Вычислительная сложность

Задача вычисления числа 3-раскрасок данного графа является каноническим примером #P-полной задачи, так что задача вычисления коэффициентов хроматического многочлена #P-трудна. Аналогично, вычисление <math>P(G, 3)</math> для данного графа G #P-полна. С другой стороны, для <math>k=0,1,2</math> легко вычислить <math>P(G, k)</math>, так что соответствующие задачи имеют полиномиальную по времени трудность. Для целых чисел <math>k>3</math> задача #P-трудна, что устанавливается подобно случаю <math>k=3</math>. Фактически, известно, что <math>P(G, x)</math> #P-трудна для всех x (включая отрицательные целые числа и даже все комплексные числа), за исключением трёх «простых точек»[1]. Таким образом, сложность вычисления хроматического многочлена полностью понятна.

В многочлене

<math>P(G, t)= a_1 t + a_2t^2+\dots +a_nt^n,</math>

коэффициент <math>a_n</math> всегда равен 1, а также известны некоторые другие свойства коэффициентов. Это поднимает вопрос, нельзя ли вычислить некоторые коэффициенты попроще. Однако задача вычисления ar для фиксированного r и данного графа G является #P-труднойШаблон:Sfn.

Не известно никакого аппроксимационного алгоритма вычисления <math>P(G, x)</math> для любого x, за исключением трёх простых точек. В целых точках <math>k=3,4,\dots</math> соответствующая задача разрешимости определения, может ли данный граф быть раскрашен в k цветов, NP-трудна. Такие задачи не могут быть аппроскимированы с любым коэффициентом с помощью полиномиального вероятностного алгоритма с ограниченной ошибкой, разве только NP = RP, поскольку любая мультипликативная аппроксимация различала бы значения 0 и 1, что было бы эффективным решением задачи с помощью полиномиального вероятностного алгоритма с ограниченной ошибкой в форме задачи разрешимости. В частности, при некоторых предположениях, это исключает возможность полностью полиномиальной рандомизированной аппроксимационной схемы (FPRAS). Для других точек нужны более сложные рассуждения и вопрос находится в фокусе активных поисков. На 2008 известно, что не существует FPRAS-схемы для вычиcления <math>P(G, x)</math> для любого x > 2, разве только NP = RPШаблон:Sfn.

Примечания

Шаблон:Примечания

Литература

Ссылки

Шаблон:Rq

Партнерские ресурсы
Криптовалюты
Магазины
Хостинг
Разное

  1. ↑ Йегер, Вертиган и Уэлш Шаблон:Harv, базируясь на сведении Линиала Шаблон:Harv.
Источник — http://wikihandbk.com/ruwiki/index.php?title=Русская_Википедия:Хроматический_многочлен&oldid=11265655