WikiSort.ru - Не сортированное

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

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

${\displaystyle (x-1)^{n-1}x,}$

В частности,

${\displaystyle (x-1)^{3}x}$

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

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

Граф является хроматически уникальным, если он определяется хроматическим многочленом с точностью до изоморфизма. Другими словами, если граф G хроматически уникален, то из ${\displaystyle P(G,t)=P(H,t)}$ следует, что G и H изоморфны.

Все циклы хроматически уникальны^[4].

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

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

Никакой граф нельзя раскрасить в 0 цветов, так что 0 всегда является хроматическим корнем. Только графы без рёбер могут быть раскрашены в один цвет, так что 1 является хроматическим корнем любого графа, имеющего по меньшей мере одно ребро. С другой стороны, за исключением этих двух случаев, никакой граф не может иметь в качестве хроматического корня вещественное число, меньшее либо равное 32/27^[5]. Результат Тата связывает золотое сечение ${\displaystyle \phi }$ с изучением хроматических корней, показывая, что хроматические корни существуют очень близко к ${\displaystyle \phi ^{2}}$ — если ${\displaystyle G_{n}}$ является планарной триангуляцией сферы, то

${\displaystyle P(G_{n},\phi ^{2})\leq \phi ^{5-n}.}$

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

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

Хроматический многочлен категоризирован с помощью теории гомологий, близко связанной с гомологией Хованова^[en][7].

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

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

Известны алгоритмы полиномиального времени для вычисления хроматического многочлена для широкого класса графов, в который входят хордальные графы^[8] и графы с ограниченной кликовой шириной^[9][10]. Второй из этих классов, в свою очередь, включает кографы и графы с ограниченной древесной шириной, такие как внешнепланарные графы.

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

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

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

${\displaystyle P(G,k)=P(G-uv,k)-P(G/uv,k)}$ ,

где ${\displaystyle u}$ и ${\displaystyle v}$ являются смежными вершинами и ${\displaystyle G-uv}$ является графом с удалённым ребром ${\displaystyle uv}$ . Эквивалентно,

${\displaystyle P(G,k)=P(G+uv,k)+P(G/uv,k)}$

если ${\displaystyle u}$ и ${\displaystyle v}$ не смежны и ${\displaystyle G+uv}$ является графом с добавленным ребром ${\displaystyle uv}$ . В первой форме рекурсия прекращается на наборе пустых графов. Эти рекуррентные отношения называются также Фундаментальной теоремой редукции^[12]. Любопытство Тата о том, какие другие свойства графа удовлетворяют тем же рекуррентным соотношениям, привело к открытию обобщения хроматического многочлена на две переменные, многочлену Тата.

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

${\displaystyle \phi ^{n+m}=\left({\frac {1+{\sqrt {5}}}{2}}\right)^{n+m}\in O\left(1{,}62^{n+m}\right)}$

на графе с n вершинами и m рёбрами^[14]. Анализ времени работы можно улучшить до полиномиального множителя числа ${\displaystyle t(G)}$ остовных деревьев входного графа^[15]. На практике используется стратегия ветвей и границ вместе с отбрасыванием изоморфных графов, чтобы исключить рекурсивные вызовы, и время зависит от эвристики, используемой при выборе пары вершин (для исключения–стягивания).

Метод куба

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

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

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

В многочлене

${\displaystyle P(G,t)=a_{1}t+a_{2}t^{2}+\dots +a_{n}t^{n},}$

коэффициент ${\displaystyle a_{n}}$ всегда равен 1, а также известны некоторые другие свойства коэффициентов. Это поднимает вопрос, нельзя ли вычислить некоторые коэффициенты попроще. Однако задача вычисления a_r для фиксированного r и данного графа G является #P-трудной^[17].

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