Гомоморфизм графов — это отображение между двумя графами, не нарушающее структуру. Более конкретно, это отображение между набором вершин двух графов, которое отображает смежные вершины в смежные.
Гомоморфизмы обобщают различные понятия раскрасок графов и позволяют выражение важных классов задач удовлетворения ограничений, таких как некоторые задачи или задачи . Факт, что гомоморфизмы могут быть использованы последовательно, приводит к богатым алгебраическим структурам — предпорядку на графах, и категориям (одна для неориентированных графов и одна для ориентированных графов). Вычислительная сложность поиска гомоморфизма между заданными графами в общем случае запредельная, но известно много частных случаев, когда задача выполнима за полиномиальное время. Границы между решаемыми и непреодолимыми случаями находятся в области активных исследований.
Определения В этой статье, если не сказано другое, под графами понимаются конечные неориентированные графы с разрешёнными петлями, но кратные рёбра (параллельные) не разрешены. Гомоморфизм графа: f из графа в граф , что записывается как , это функция из V(G) в V(H), которая отображает конечные точки каждого ребра из G в конечные точки некоторого ребра из H. Формально, из следует , для всех пар вершин u, v из V(G). Если существует некоторый гомоморфизм из G в H, то говорят, что граф G гомоморфен графу H, или что он H-раскрашиваем. Это часто обозначается как .
Определение выше распространяется на ориентированные графы. Тогда для гомоморфизма является дугой (ориентированным ребром) графа H, когда (u,v) является дугой графа G.
Существует инъективный гомоморфизм из G в H (то есть отображение, которое никогда не отображает различные вершины в одну) тогда и только тогда, когда G является подграфом графа H. Если гомоморфизм является биекцией (соответствием один-к-одному между вершинами графа G и графа H) обратная функция которого является также гомоморфизм графа, тогда f является изоморфизмом графов.
Накрывающие отображения являются частым видом гомоморфизмов, который отражает определение и многие свойства накрытия в топологии. Они определяются как сюръективные гомоморфизмы, которые локально биективны, то есть является биекцией в окрестности каждой вершины. Примером служит двойное покрытие двудольным графом, образованное из графа путём разбиения каждой вершины v на и и заменой каждого ребра u,v на два ребра и . Функция, отображающая v0 и v1 в v исходного графа, является гомоморфизмом и накрывающим отображением.
Гомеоморфизм графа является отдельным понятием, не связанным прямо с гомоморфизмами. Грубо говоря, он требует инъективности, но позволяет отображение ребер в пути (а не просто в рёбра). Миноры графа остаются более слабым понятием.
Ядра и ретракты
Два графа G и H гомоморфно эквивалентны, если и .
Ретракция — это гомоморфизм r из графа G в подграф H графа G, такой, что r(v)=v для каждой вершины v из H. В этом случае подграф H называется ретрактом графа G.
Ядро — это граф, не имеющий гомоморфизма в любой собственный подграф. Эквивалентно, ядро можно определить как граф, который не является ретрактом для любого собственного подграфа. Любой граф G гомоморфно эквивалентен единственному ядру (с точностью до изоморфизма), которое называется ядром графа G. Заметим, что это неверно для бесконечных графов общего вида. Однако те же определения применимы и к ориентированным графам и ориентированный граф также эквивалентен единственному ядру. Любой неориентированный и ориентированный граф содержит своё ядро и как ретракт, и как порождённый подграф.
Например, все полные графы Kn и все нечётные циклы (графов-циклов нечётной длины) являются ядрами. Любой 3-раскрашиваемый граф G, содержащий треугольник (то есть имеет полный граф K3 в качестве подграфа) гомеоморфно эквивалентен K3. Это потому, с одной стороны, что 3-раскраска графа G, это то же самое, что и гомоморфизм , как объяснено ниже. С другой стороны, любой подграф графа G тривиально допускает гомоморфизм в G, откуда следует, что . Это также означает, что K3 является ядром любого такого графа G. Аналогично, любой двудольный граф, который имеет по меньшей мере одно ребро, эквивалентен K2.
Связь с раскрасками k-Раскраска для некоторого целого k — это назначение одного из k цветов каждой вершине графа G так, что конечные вершины каждого ребра имеют различные цвета. k-Раскраски графа G соответствуют в точности гомоморфизмам из G в полный граф Kk. Более того, вершины графа Kk соответствуют k цветам и два цвета смежны как вершины графа Kk тогда и только тогда, когда они различны. Следовательно, функция определяет гомоморфизм в Kk тогда и только тогда, когда смежные вершины графа G выкрашены в разные цвета. В частности, граф G k-раскрашиваем тогда и только тогда, когда Kk-раскрашиваем.
Если есть два гомоморфизма и , то их суперпозиция является также гомоморфизмом. Другими словами, если граф H может быть выкрашен в k цветов и существует гомоморфизм G в H, то G может быть также выкрашен в k цветов. Поэтому из следует , где означает хроматическое число графа (наименьшее число цветов k, в которые можно раскрасить граф).
Варианты Гомоморфизмы общего вида можно рассматривать также как вид раскраски — если вершины фиксированного графа H являются допустимыми цветами, а рёбра графа H описывают, какие цвета совместимы, то H-раскраска графа G — это назначение цветов вершинам графа G так, что смежные вершины получают совместимые цвета. Многие понятия раскраски графов вмещаются в эту схему и могут быть выражены как гомоморфизмы графов в различные семейства графов. Цикловые раскраски можно определить с помощью гомоморфизмов в цикловые полные графы, уточняя обычное понятие раскраски. Дробная и b-кратная раскраска могут быть определены с помощью гомоморфизмов в кнезеровские графы T-раскраски соответствуют гомоморфизмам в некоторые бесконечные графы. Ориентированная раскраска ориентированного графа является гомоморфизмом в любой ориентированный граф. — это локально инъективный гомоморфизм в дополнение пути, что означает, что он должен быть инъективным в окрестности каждой вершины.
Ориентации без длинных путей
Другая интересная связь касается ориентации графов. Ориентация неориентированного графа G — это любой ориентированный граф, полученный выбором из двух возможных ориентаций каждого ребра. Примером ориентации полного графа Kk служит транзитивный турнир с вершинами 1,2,…,k и дугами из i в j, когда i < j. Гомоморфизм между ориентациями графов G и H даёт гомоморфизм между неориентированными графами G и H, если просто игнорировать ориентации. С другой стороны, если дан гомоморфизм между неориентированными графами, любая ориентация of H может быть отражена в ориентацию графа of G, так что имеет гомоморфизм в . Поэтому граф G k-раскрашиваем (имеет гомоморфизм в Kk) тогда и только тогда, когда некоторая ориентация G имеет гомоморфизм в .
Фольклорная теорема гласит, что для любых k ориентированный граф G имеет гомоморфизм в тогда и только тогда, когда он не допускает гомоморфизма из . Здесь — ориентированный путь с вершинами 1, 2, …, n и дугами из i в i + 1 для i=1, 2, …, n − 1. Таким образом, граф k-раскрашиваем тогда и только тогда, когда он имеет ориентацию, которая не допускает гомоморфизма из . Это утверждение может быть слегка усилено до утверждения, что граф k-раскрашиваем тогда и только тогда, когда некоторая ориентация не содержит ориентированного пути длины k (нет в качестве подграфа). Это Теорема Галлаи — Хассе — Роя — Витавера.
Связь с задачами удовлетворения ограничений
Примеры
Некоторые задачи расписаний можно промоделировать как вопрос о нахождении гомоморфизмов графа. Как пример, можно попробовать назначить практические занятия так, чтобы два курса, посещаемые тем же студентом, не были по времени слишком близки. Курсы образуют граф G, с рёбрами между двумя курсами, если их посещает один и тот же студент. Возможное время проведения курсов образует граф H с рёбрами между двумя временны́ми окнами, если расстояние по времени между ними достаточно велико. Например, если хотят иметь циклическое еженедельное расписание, такое, что каждый студент приходит на практические занятия через день, то граф H был бы дополнением графа C7. Гомоморфизм графа из G в H является тогда назначением курсов по временным окнам. Чтобы добавить требование, скажем, чтобы никакой студент не имел занятия как в пятницу, так и в понедельник, достаточно удалить одно ребро из графа H.
Простая задача может быть поставлена следующим образом. Имеется несколько передатчиков беспроводной сети. Нужно выбрать на каждом из них частотный канал, по которому он будет передавать данные. Чтобы избежать помех, географически близкие передатчики должны иметь каналы с достаточно отличающимися частотами. Если это условие ограничено простым порогом для понятия «географически близки» и «достаточно далеки», допустимый выбор каналов соответствует снова гомоморфизму графа. Здесь графом G будет набор передатчиков с рёбрами между ними, если они географически близки, а графом H будет набор каналов с рёбрами между каналами, если частоты достаточно отличаются. Хотя эта модель сильно упрощена, она допускает некоторую гибкость — для пары передатчиков, которые не близки, но могут мешать друг другу ввиду географических особенностей, может быть добавлена дуга в G. А дуга между передатчиками, которые не работают в одно и то же время, может быть из графа удалена. Аналогично, ребро между парой каналов, которые далеко друг от друга, но имеют помехи в виде гармоник может быть удалено из графа H.
В каждом случае эти упрощённые модели показывают много особенностей, которые следует отрабатывать на практике. Задачи удовлетворения ограничений, которые обобщают задачи гомоморфизма графа, могут выражать дополнительные типы условий (такие как индивидуальные предпочтения или ограничения на число совпадающих назначений). Это позволяет сделать модели более реалистичными и практичными.
Формальная точка зрения Графы и ориентированные графы можно рассматривать как частые случаи более общего понятия, называемого (которые определяются как множество с кортежем отношений на нём). Ориентированные графы являются структурами с одним бинарным отношением (смежность) на области (множестве вершин). Заметим, что реляционные структуры в статье называются реляционными системами.. С этой точки зрения таких структур являются в точности гомоморфизмами графов. В общем случае вопрос поиска гомоморфизма из одной структуры в другую является задачей удовлетворения ограничений (, 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.
Структура гомоморфизмов Суперпозиции гомоморфизмов являются гомоморфизмами. В частности, отношение на графах транзитивно (и, тривиально, рефлексивно), так что это отношение является предпорядком на графах. Будем обозначать класс эквивалентности графа G по гомоморфизму через [G]. Класс эквивалентности может быть представлен единственным ядром в [G].