Гомоморфизм графов

Гомоморфизм из снарка «цветок» J₅ в цикл C₅.
Это также ретракция в центральные пять вершин. Тогда J₅, фактически, гомоморфно эквивалентен ядру C₅.

Гомоморфизм графов — это отображение между двумя графами, не нарушающее структуру. Более конкретно, это отображение между набором вершин двух графов, которое отображает смежные вершины в смежные.

Гомоморфизмы обобщают различные понятия раскрасок графов и позволяет выражение важных классов задач удовлетворения ограничений, таких как некоторые задачи составления расписаний или задачи распределения радиочастот. Факт, что гомоморфизмы могут быть использованы последовательно, приводит к богатым алгебраическим структурам — предпорядку на графах, дистрибутивной решётке и категориям (одна для неориентированных графов и одна для ориентированных графов). Вычислительная сложность поиска гомоморфизма между заданными графами в общем случае запредельная, но известно много частных случаев, когда задача выполнима за полиномиальное время. Границы между решаемыми и непреодолимыми случаями находятся в области активных исследований.

Определения

В этой статье, если не сказано другое, под графами понимаются конечные неориентированные графы с разрешёнными петлями, но кратные рёбра (параллельные) не разрешены. Гомоморфизм графа: f из графа $G=(V(G),E(G))$ в граф $H=(V(H),E(H))$, что записывается как

$f:G\to H$,

это функция из V(G) в V(H), которая отображает конечные точки каждого ребра из G в конечные точки некоторого ребра из H. Формально, из $\{u,v\}\in E(G)$ следует $\{f(u),f(v)\}\in E(H)$, для всех пар вершин u, v из V(G). Если существует некоторый гомоморфизм из G в H, то говорят, что граф G гомоморфен графу H, или что он H-раскрашиваем. Это часто обозначается как

$G\to H$.

Определение выше распространяется на ориентированные графы. Тогда для гомоморфизма $f:G\to H,(f(u),f(v))$ является дугой (ориентированным ребром) графа H, когда (u,v) является дугой графа G.

Существует инъективный гомоморфизм из G в H (то есть отображение, которое никогда не отображает различные вершины в одну) тогда и только тогда, когда G является подграфом графа H. Если гомоморфизм $f:G\to H$ является биекцией (соответствием один-к-одному между вершинами графа G и графа H) обратная функция которого является также гомоморфизм графа, тогда f является изоморфизмом графов.

Накрывающие отображения являются частым видом гомоморфизмов, который отражает определение и многие свойства накрытия в топологии. Они определяются как сюръективные гомоморфизмы, которые локально биективны, то есть является биекцией в окрестности каждой вершины. Примером служит двойное покрытие двудольным графом, образованное из графа путём разбиения каждой вершины v на $v_{0}$ и $v_{1}$ и заменой каждого ребра u,v на два ребра $u_{0},v_{1}$ и $v_{0},u_{1}$. Функция, отображающая v₀ и v₁ в v исходного графа, является гомоморфизмом и накрывыающим отображением.

Гомеоморфизм графа является отдельным понятием, не связанным прямо с гомоморфизмами. Грубо говоря, он требует инъективности, но позволяет отображение ребер в пути (а не просто в рёбра). Миноры графа остаются более слабым понятием.

Ядра и ретракты

K₇, полный граф с 7 вершинами, является ядром.

Основная статья: Ядро (теория графов)

Два графа G и H гомоморфно эквивалентны, если $G\to H$ и $H\to G$.

Ретракция — это гомоморфизм r из графа G в подграф H графа G, такой, что r(v)=v для каждой вершины v из H. В этом случае подграф H называется ретрактом графа G.

Ядро — это граф, не имеющий гомоморфизма в любой собственный подграф. Эквивалентно, ядро можно определить как граф, который не является ретрактом для любого собственного подграфа. Любой граф G гомоморфно эквивалентен единственному ядру (с точностью до изоморфизма), которое называется ядром графа G. Заметим, что это неверно для бесконечных графов общего вида. Однако те же определения применимы и к ориентированным графам и ориентированный граф также эквивалентен единственному ядру. Любой неориентированный и ориентированный граф содержит своё ядро и как ретракт, и как порождённый подграф.

Например, все полные графы K_n и все нечётные циклы (графов-циклов нечётной длины) являются ядрами. Любой 3-раскрашиваемый граф G, содержащий треугольник (то есть имеет полный граф K₃ в качестве подграфа) гомеоморфно эквивалентен K₃. Это потому, с одной стороны, что 3-раскраска графа G, это то же самое, что и гомоморфизм $G\to K_{3}$, как объяснено ниже. С другой стороны, любой подграф графа G тривиально допускает гомоморфизм в G, откуда следует, что $K_{3}\to G$. Это также означает, что K₃ является ядром любого такого графа G. Аналогично, любой двудольный граф, который имеет по меньшей мере одно ребро, эквивалентен K₂.

Связь с раскрасками

k-Раскраска для некоторого целого k — это назначение одного из k цветов каждой вершине графа G так, что конечные вершины каждого ребра имеют различные цвета. k-Раскраски графа G соответствуют в точности гомоморфизмам из G в полный граф K_k. Более того, вершины графа K_k соответствуют k цветам и два цвета смежны как вершины графа K_k тогда и только тогда, когда они различны. Следовательно, функция определяет гомоморфизм в K_k тогда и только тогда, когда смежные вершины графа G выкрашены в разные цвета. В частности, граф G k-раскрашиваем тогда и только тогда, когда K_k-раскрашиваем.

Если есть два гомоморфизма $G\to H$ и $H\to K_{k}$, то их суперпозиция $G\to K_{k}$ является также гомоморфизм. Другими словами, если граф H может быть выкрашен в k цветов и существует гомоморфизм G в H, то G может быть также выкрашен в k цветов. Поэтому из $G\to H$ следует $\chi (G)\leqslant \chi (H)$, где $\chi$ означает хроматическое число графа (наименьшее число цветов k, в которые можно раскрасить граф).

Варианты

Гомоморфизмы общего вида можно рассматривать также как вид раскраски — если вершины фиксированного графа H являются допустимыми цветами, а рёбра графа H описывают, какие цвета совместимы, то H-раскраска графа G — это назначение цветов вершинам графа G так, что смежные вершины получают совместимые цвета. Многие понятия раскраски графов вмещаются в эту схему и могут быть выражены как гомоморфизмы графов в различные семейства графов. Цикловые раскраски можно определить с помощью гомоморфизмов в цикловые полные графы, уточняя обычное понятие раскраски. Дробная и b-кратная раскраска могут быть определены с помощью гомоморфизмов в кнезеровские графы T-раскраски соответствуют гомоморфизмам в некоторые бесконечные графы. {Ориентированная раскраска ориентированного графа является гомоморфизмом в любой ориентированный граф. L(2,1)-раскраска — это локально инъективный гомоморфизм в дополнение пути, что означает, что он должен быть инъективным в окрестности каждой вершины.

Ориентации без длинных путей

Основная статья: Теорема Галлаи — Хассе — Роя — Витавера

Другая интересная связь касается ориентации графов. Ориентация неориентированного графа G — это любой ориентированный граф, полученный выбором из двух возможных ориентаций каждого ребра. Примером ориентации полного графа K_k служит транзитивный турнир ${\vec {T}}_{k}$ с вершинами 1,2,…,k и дугами из i в j, когда i < j. Гомоморфизм между ориентациями графов G и H даёт гомоморфизм между неориентированными графами G и H, если просто игнорировать ориентации. С другой стороны, если дан гомоморфизм $G\to H$ между неориентированными графами, любая ориентация ${\vec {H}}$ of H может быть отражена в ориентацию графа ${\vec {G}}$ of G, так что ${\vec {G}}$ имеет гомоморфизм в ${\vec {H}}$. Поэтому граф G k-раскрашиваем (имеет гомоморфизм в K_k) тогда и только тогда, когда некоторая ориентация G имеет гомоморфизм в ${\vec {T}}_{k}$.

Фольклорная теорема гласит, что для любых k ориентированный граф G имеет гомоморфизм в ${\vec {T}}_{k}$ тогда и только тогда, когда он не допускает гомоморфизма из ${\vec {P}}_{k+1}$. Здесь ${\vec {P}}_{n}$ — ориентированный путь с вершинами 1, 2, …, n и дугами из i в i + 1 для i=1, 2, …, n − 1. Таким образом, граф k-раскрашиваем тогда и только тогда, когда он имеет ориентацию, которая не допускает гомоморфизма из ${\vec {P}}_{k+1}$. Это утверждение может быть слегка усилено до утверждения, что граф k-раскрашиваем тогда и только тогда, когда некоторая ориентация не содержит ориентированного пути длины k (нет ${\vec {P}}_{k+1}$ в качестве подграфа). Это Теорема Галлаи — Хассе — Роя — Витавера.

Связь с задачами удовлетворения ограничений

Примеры

Граф H несоседних дней недели изоморфен дополнению графа C₇ и в цикловой клике K_7/2

Некоторые задачи расписаний можно промоделировать как вопрос о нахождении гомоморфизмов графа. Как пример, можно попробовать назначить практические занятия так, чтобы два курса, посещаемые тем же студентом, не были по времени слишком близки. Курсы образуют граф G, с рёбрами между двумя курсами, если их посещает один и тот же студент. Возможное время проведения курсов образует граф H с рёбрами между двумя временны́ми окнами, если расстояние по времени между ними достаточно велико. Например, если хотят иметь циклическое еженедельное расписание, такое, что каждый студент приходит на практические занятия через день, то граф H был бы дополнением графа C₇. Гомоморфизм графа из G в H является тогда назначением курсов по временным окнам. Чтобы добавить требование, скажем, чтобы никакой студент не имел занятия как в пятницу, так и в понедельник, достаточно удалить одно ребро из графа H.

Простая задача распределения частот может быть поставлена следующим образом. Имеется несколько передатчиков беспроводной сети. Нужно выбрать на каждом из них частотный канал, по которому он будет передавать данные. Чтобы избежать помех, географически близкие передатчики должны иметь каналы с достаточно отличающимися частотами. Если это условие ограничено простым порогом для понятия «географически близки» и «доствточно далеки», допустимый выбор каналов соответствует снова гомоморфизму графа. Здесь графом G будет набор передатчиков с рёбрами между ними, если они географически близки, а графом H будет набор каналов с рёбрами между каналами, если частоты достаточно отличаются. Хотя эта модель сильно упрощена, она допускает некоторую гибкость — для пары передатчиков, которые не близки, но могут мешать друг другу ввиду географических особенностей, может быть добавлена дуга в G. А дуга между передатчиками, которые не работают в одно и то же время, может быть из графа удалена. Аналогично, ребро между парой каналов, которые далеко друг от друга, но имеют помехи в виде гармоник может быть удалено из графа H.

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

Формальная точка зрения

Ориентированные и ориентированные графы можно рассматривать как частые случаи более общего понятия, называемого реляционные структуры (которые определяются как множество с кортежем отношений на нём). Ориентированные графы являются структурами с одним бинарным отношением (смежность) на области (множестве вершин). С этой точки зрения гомоморфизмы таких структур являются в точности гомоморфизмами графов. В общем случае вопрос поиска гомоморфизма из одной структуры в другую является задачей удовлетворения ограничений (англ. constraint satisfaction problem, CSP). Случай графов даёт конкретный первый шаг, который помогает понять более сложные задачи удовлетворения ограничений. Многие алгоритмические методы поиска гомоморфизмов графа, наподобие поиска с возвратом, распространения ограничений и локального поиска применимы ко всем задачам удовлетворения ограничений.

Для графов G и H вопрос, имеет ли граф G гомоморфизм в граф H, соответствует частному случаю задачи удовлетворения ограничений с только одним видом ограничений. В этой задаче переменными будут вершины графа G, а областью значений каждой переменной будет набор вершин графа H. Решением является функция, которая назначает каждой переменной элемент из области значений, так что функция f отображает V(G) в V(H). Каждое ребро или дуга (u,v) графа G тогда соответствует ограничению ((u,v), E(H)). Это ограничение выражает, что решение должно отображать дугу (u,v) в пару (f(u),f(v)), которая является отношением E(H), то есть, в дугу графа H. Решением задачи является решение, которое удовлетворяет всем ограничениям, то есть это в точности гомоморфизм из G в H.

Структура гомоморфизмов

Суперпозиции гомоморфизмов являются гомоморфизмами. В частности, отношение $\to$ на графах транзитивно (и, тривиально, рефлексивно), так что это отношение является предпорядком на графах. Будем обозначать класс эквивалентности графа G по гомоморфизму через [G]. Класс эквивалентности может быть представлен единственным ядром в [G]. Отношение $\to$ частично упорядочено на этих классах эквивалентности. Оно определяет частично упорядоченное множество.

Пусть G < H означает, что существует гомоморфизм из G в H, но нет гомоморфизма из H в G. Отношение $\to$ является плотным порядком, это означает, что для всех (неориентированных) графов G, H таких, что G < H, существует граф K, такой, что G < K < H (это выполняется во всех случаях, за исключением тривиальных случаев $G=K_{0}$ или $K_{1}$). Например, между любыми двумя полными графами (за исключением $K_{0},K_{1}$) есть бесконечно много цикловых полных графов, соответствующих рациональным числам.

Частично упорядоченное множество классов эквивалентности графов по гомоморфизму является дистрибутивной решёткой, с объединением [G] и [H], определённым как (класс эквивалентности) дизъюнктное объединение $[G\cup H]$ и пересечение [G] и [H] определяется как тензорное произведение $[G\times H]$ (выбор графов G и H в качестве представителей классов эквивалентности [G] и [H] не имеет значения). Неприводимые в объединении элементы этой решётки — это в точности связные графы. Это можно показать, используя факт, что гомоморфизм отображает связный граф в связную компоненту целевого графа. Неприводимые в пересечении элементы этой решётки — это в точности мультипликативные графы. Это графы K, такие, что произведение $G\times H$ имеет гомоморфизм в K только тогда, когда один из графов G или H имеет такой гомоморфизм. Выявление мультипликативных графов является сердцевиной гипотезы Хедетниеми.

Гомоморфизмы графов образуют также категорию с графами в качестве объектов и гомоморфизмами в качестве стрелок. Начальным объектом является пустой граф, в то время как терминальным объектом является граф с одной вершиной и одной петлёй в этой вершине. Тензорное произведение графов является произведением в теории категорий и экспоненциальный граф является экспоненциальным объектом для категории. Поскольку эти две операции всегда определены, категория графов является декартово замкнутой категорией. По тем же причинам решётка классов эквивалентности графов по гомоморфизмам, фактически, является алгеброй Гейтинга.

Для ориентированных графов применимы те же определения. В частности, $\to$ частично упорядочено на классах эквивалентности ориентированных графов. Этот порядок отличается от порядка $\to$ на классах эквивалентности неориентированных графов, но содержит его в качестве подпорядка. Это потому, что любой неориентированный граф можно рассматривать как ориентированный, в котором любая дуга (u,v) появляется вместе с обратной дугой (v,u), а это не меняет определение гомоморфизма. Порядок $\to$ для ориентированных графов снова является дистрибутивной решёткой и алгеброй Гейтинга с операциями объединения и пересечения, определённых как ранее. Однако этот порядок не плотный. Существует также категория с ориентированными графами в качестве объектов и гомоморфизмами в качестве стрелок, которая снова является декартово замкнутой категорией.

Несравнимые графы

Граф Грёча несравним с треугольником K₃

Имеется много несравнимых графов согласно предпорядку гомоморфизмов, то есть пары графов, таких, что нет гомоморфизмов из одного в другой. Один из путей построения таковых графов — рассмотрение нечётного обхвата графа G, то есть длины его самого короткого цикла нечётной длины. Нечётный обхват, эквивалентно, является наименьшим нечётным числом g, для которого существует гомоморфизм из графа-цикла с g вершинами в G. По этой причине, если $G\to H$, то нечётный обхват графа G больше либо равен нечётного обхвата графа H.

С другой стороны, если $G\to H$, то хроматическое число графа G меньше либо равно хроматическому числу графа H. Поэтому, если граф G имеет строго больший нечётный обхват, чем H и строго большее хроматическое число, чем H, то G и H несравнимы Например, граф Грёча является 4-хроматичным (раскрашивается в 4 цвета) и свободным от треугольников (он имеет обхват 4 и нечётный обхват 5), так что он несовместим с треугольником K₃.

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

Среди ориентированных графов найти несравнимые пары много проще. Например, рассмотрим ориентированные графы-циклы ${\vec {C}}_{n}$ с вершинами 1, 2, …, n и рёбрами из i в i + 1 (для i=1, 2, …, n − 1) и из n в 1. Существует гомоморфизм из ${\vec {C}}_{n}$ в ${\vec {C}}_{k}(n,k\geqslant 3)$ тогда и только тогда, когда n кратно k. В частности ориентированные графы-циклы ${\vec {C}}_{n}$ с простыми n все несравнимы.

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

В задаче о гомоморфизме графа экземпляр задачи состоит из пары графов (G,H), а решением является гомоморфизм из G в H. Общая задача разрешимости, спрашивающая, имеется ли решение этой задачи, NP-полна. Однако ограничения на графы дают ряд различных задач, некоторые из которых решить легче. Методы, которые используют ограничения на левый граф G, сильно отличаются от методов, использующихся на правый граф H, но в каждом случае дихотомия (строгие границы между простыми и сложными случаями) известна или предполагается.

Гомоморфизмы в фиксированный граф

Задача о гомоморфизме с фиксированным графом H с правой стороны каждого экземпляра называется задачей H-раскраски. Когда H является полным графом K_k, это задача k-раскраски графа, которая разрешима за полиномиальное время для k=0, 1, 2 и NP-полна в других случаях. В частности, возможность K₂-раскраски графа G эквивалентна двудольности графа G, что можно проверить за линейное время. Более обще, когда H является двудольным графом, возможность H-раскраски эквивалентна возможности K₂-раскраски (или K₀ / K₁ -раскрашиваемости, когда H пусто или не имеет рёбер), а следовательно, равным образом легко решается. Павол Хелл и Ярослав Нешетрил доказали, что для неориентированных графов никакой другой случай не является лёгким:

Теорема Хелла — Нешетрила (1990): Задача H-раскраски лежит в классе P, если H двудолен и NP-сложна в противном случае.

Теорема известна также как теорема о дихотомии для гомоморфизма (неориентированного) графа, поскольку она делит задачи H-раскраски на NP-полные и задачи класса P без промежуточных случаев. Для ориентированных графов ситуация более сложная и, фактически, эквивалентна более общему вопросу описания сложности удовлетворения ограничений. Оказывается, что задачи H-раскраски для ориентированных графов настолько же общи и настолько же разнолики, как и задачи удовлетворения ограничений с любыми другими видами ограничений. Формально, (конечный) язык ограничений Γ является конечной областью и конечным набором отношений в этой области. CSP(Γ) является задачей удовлетворения ограничений, где экземплярам позволяется использование только ограничений из Γ.

Теорема (Федер, Варди 1998): Для любого языка ограничений Γ задача CSP(Γ) эквивалентна после полиномиального сведения некоторой задаче H-раскраски для некоторого ориентированного графа H.

Интуитивно это означает, что любая алгоритмическая техника или результат о сложности, применимые к задачам H-раскраскам для ориентированных графов H, применимы также и для общих задач удовлетворения ограничений. В частности, можно спросить, может ли теорема Хелла — Нешетрила быть распространена на ориентированные графы. По теореме выше это эквивалентно гипотезе Федера — Варди о дихотомии задач удовлетворения ограничений, которая утверждает, что для любого языка ограничений Γ задача CSP(Γ) либо NP-полна, либо принадлежит классу P.

Гомоморфизмы из фиксированного семейства графов

Задача о гомоморфизме с одним фиксированным графом G в левой стороне может быть решена полным перебором за время |V(H)|^O(|V(G)|), то есть полиномиально от размера входного графа H. Другими словами, задача тривиальна в P для графов G ограниченного размера. Интересный вопрос тогда, какие другие свойства графа G, кроме размера, делают возможными полиномиальные алгоритмы.

Ключевым свойством оказывается древесная ширина, мера, насколько граф похож на дерево. Для графа G с древесной шириной, не превосходящей k, и графа H задача о гомоморфизме может быть решена за время|V(H)|^O(k) стандартными методами динамического программирования. Фактически, достаточно предположить, что ядро графа G имеет древесную ширину, не превосходящую k. Это верно даже в случае, когда ядро не известно.

Показатель в алгоритме с временем работы|V(H)|^O(k) не может быть снижен существенно — не существует алгоритма, работающего за время|V(H)|^{o(tw(G) /log tw(G))} при верности гипотезы об экспоненциальном времени (англ. exponential time hypothesis, ETH), даже если вход ограничен любым классом графов неограниченной древесной ширины. ETH является недоказанным допущением, аналогичным допущению P ≠ NP, но более строгим. При тех же допущениях нет других свойств, которые могут быть использованы для получения алгоритмов полиномиального времени. Это формализуется теоремой:

Теорема (Мартин Гроэ): Для вычислимого класса графов ${\mathcal {G}}$, задача о гомоморфизме для $(G,H)$ с $G\in {\mathcal {G}}$ принадлежит P тогда и только тогда, когда графы ${\mathcal {G}}$ имеют ядра ограниченной древесной ширины (в допущении ETH) .

Можно задать вопрос, разрешима ли задача с произвольно высокой зависимостью от G, но с фиксированной полиномиальной зависимостью от размера графа H. Ответ положительный, если мы ограничим граф G классом с ядрами ограниченной древесной ширины, и отрицательный для всех других классов. На языке параметризованной сложности это утверждение формально гласит, что задача о гомоморфизме с графом ${\mathcal {G}}$, параметризованная по размеру (числу рёбер) графа G, показывает дихотомию. Она фиксированно-параметрически разрешима, если графы в классе ${\mathcal {G}}$ имеют ядра ограниченной древесной ширины, и W[1]-полна в противном случае.

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

См. также

• Гипотеза Сидоренко

Литература

Книги общего характера

• Peter Cameron. Graph Homomorphisms, Combinatorics Study Group Notes. — 2006.
• Pavol Hell, Jaroslav Nešetřil. Graphs and Homomorphisms. — Oxford University Press, 2004. — Т. 28. — ISBN 0-19-852817-5.
• Geňa H., Tardif C. Graph homomorphisms: structure and symmetry // Graph Symmetry: Algebraic Methods and Applications. — Springer, 1997. — С. 107–166. — doi:10.1007/978-94-015-8937-6_4.
• Chris Godsil, Gordon Royle. 6. Homomorphisms // Algebraic Graph Theory. — Springer–Verlag New York, 2001. — Т. 207. — (Graduate Texts in Mathematics). — ISBN 978-1-4613-0163-9. — doi:10.1007/978-1-4613-0163-9.

В универсальной алгебре и с учётом ограничений

• Bodirsky M. Graph Homomorphisms and Universal Algebra, Course Notes. — 2007.
• Pavol Hell, Jaroslav Nešetřil. Colouring, constraint satisfaction, and complexity // Computer Science Review. — 2008. — Т. 2, вып. 2. — С. 143–163. — doi:10.1016/j.cosrev.2008.10.003.

В теории решёток и теории категорий

• Brown R., Morris I., Shrimpton J., Wensley C. D. Graphs of morphisms of graphs // Electronic Journal of Combinatorics. — 2008. — Т. 15, вып. 1. — С. A1.
• Gray C. T. The Digraph Lattice. — 2014. (AMSI Vacation Research Scholarships, student research report supervised by Brian Davey and Jane Pitkethly, La Trobe University).