Войти
Гомоморфизм из цветочного снарка J5в граф циклов C 5.. Это также ретракция на подграф на пяти центральных вершинах. Таким образом, J 5 фактически гомоморфно эквивалентен ядру C5.В математическом поле теории графов гомоморфизм графов - это отображение между двумя графами, которое учитывает их структуру. Более конкретно, это функция между наборами вершин двух графов, которая отображает смежные вершины на соседние вершины.
Гомоморфизмы обобщают различные понятия раскраски графов и позволяют выразить важный класс проблем удовлетворения ограничений, таких как определенное планирование или частотное присвоение проблемы. Тот факт, что гомоморфизмы могут быть составлены, приводит к богатым алгебраическим структурам: предпорядок на графах, дистрибутивная решетка и категория (один для неориентированных графов и один для ориентированных графов). Вычислительная сложность поиска гомоморфизма между заданными графами в целом недопустима, но много известно о частных случаях, которые разрешимы за полиномиальное время. Границы между поддающимися лечению и неразрешимыми случаями были активной областью исследований.
В этой статье, если не указано иное, графы конечны, неориентированные графы с циклами разрешены, но множественными ребрами (параллельные края) запрещены. Гомоморфизм графа f из графа G = (V (G), E (G)) в граф H = (V (H), E (H)), записанный
- это функция из V (G) в V (H), которая отображает концы каждого ребра в G в концы ребра в H. Формально {u, v} ∈ E (G) влечет {f ( u), f (v)} ∈ E (H), для всех пар вершин u, v в V (G). Если существует какой-либо гомоморфизм из G в H, то говорят, что G гомоморфен H или H-раскрашиваем . Это часто обозначается как просто:
Приведенное выше определение распространяется на ориентированные графы. Тогда для гомоморфизма f: G → H, (f (u), f (v)) является дугой (направленным ребром) H, если (u, v) является дугой G.
Существует инъективный гомоморфизм из G в H (т. Е. Тот, который никогда не отображает отдельные вершины в одну вершину) тогда и только тогда, когда G является подграфом в H. Если гомоморфизм f: G → H является биекцией (взаимно однозначным соответствием между вершинами G и H), обратная функция также является гомоморфизмом графа, то f является изоморфизм графов .
Покрывающие карты - это особый вид гомоморфизмов, которые отражают определение и многие свойства покрывающих карт в топологии. Они определены как сюръективные гомоморфизмы (т.е. что-то отображается в каждую вершину), которые также являются локально биективными, то есть биекцией на окрестности каждой вершины. Примером является двудольное двойное покрытие, сформированное из графа путем разделения каждой вершины v на v 0 и v 1 и замены каждого ребра u, v ребрами u 0,v1и v 0,u1. Отображение функций v 0 и v 1 в покрытии к v в исходном графе является гомоморфизмом и покрывающим отображением.
График гомеоморфизм - это другое понятие, не связанное напрямую с гомоморфизмами. Грубо говоря, это требует инъекции, но позволяет отображать ребра на пути (а не только на ребра). Миноры графика - еще более расслабленное понятие.
K7, полный граф с 7 вершинами, является ядром. Два графа G и H гомоморфно эквивалентны, если G → H и H → G. Карты не обязательно сюръективны или инъективны. Например, полные двудольные графы K 2,2 и K 3,3 гомоморфно эквивалентны: каждая карта может быть определена как левая (соотв. справа) половина графа области и отображение только на одну вершину в левой (соответственно правой) половине графа изображения.
Ретракция - это гомоморфизм r из графа G в подграф H графа G такой, что r (v) = v для каждой вершины v графа H. В этом случае подграф H является называется ретрактом графа G.
A ядро - это граф без гомоморфизма ни одному собственному подграфу. Точно так же ядро можно определить как граф, который не сводится ни к какому собственному подграфу. Каждый граф G гомоморфно эквивалентен единственному ядру (с точностью до изоморфизма), называемому ядром графа G. Примечательно, что в общем случае это неверно для бесконечных графов. Однако те же определения применяются к ориентированным графам, и ориентированный граф также эквивалентен уникальному ядру. Каждый граф и каждый ориентированный граф содержит свое ядро в виде ретракта и индуцированного подграфа.
Например, все полные графы Knи все нечетные циклы (циклические графы нечетных длина) являются стержнями. Каждый 3-раскрашиваемый граф G, содержащий треугольник (т.е. имеющий полный граф K3в качестве подграфа), гомоморфно эквивалентен K 3. Это потому, что, с одной стороны, 3-раскраска G совпадает с гомоморфизмом G → K 3, как объясняется ниже. С другой стороны, каждый подграф графа G тривиально допускает гомоморфизм в G, откуда K 3 → G. Это также означает, что K 3 является ядром любого такого графа G., каждый двудольный граф, имеющий хотя бы одно ребро, эквивалентен K 2.
A k-раскраска для некоторого целого числа k, это присвоение одного из k цветов каждая вершина графа G такая, что концы каждого ребра имеют разные цвета. K-раскраски графа G в точности соответствуют гомоморфизмам из G в полный граф Kk. Действительно, вершины K k соответствуют k цветам, а два цвета являются смежными как вершины K k тогда и только тогда, когда они различны. Следовательно, функция определяет гомоморфизм в K k тогда и только тогда, когда она отображает смежные вершины G в разные цвета (т.е. это k-раскраска). В частности, G является k-раскрашиваемым тогда и только тогда, когда он K k -раскрашиваем.
Если есть два гомоморфизма G → H и H → K k, то их композиция G → K k также является гомоморфизмом. Другими словами, если граф H можно раскрасить в k цветов и существует гомоморфизм из G в H, то G также может быть k-раскрашенным. Следовательно, G → H влечет χ (G) ≤ χ (H), где χ обозначает хроматическое число графа (наименьшее k, для которого он является k-раскрашиваемым).
Общие гомоморфизмы также можно рассматривать как разновидность раскраски: если вершины фиксированного графа H являются доступными цветами, а ребра H описывают, какие цвета совместимы, то H-раскраска графа G является присвоение цветов вершинам графа G таким образом, чтобы смежные вершины получали совместимые цвета. Многие понятия раскраски графов вписываются в этот шаблон и могут быть выражены как гомоморфизмы графов в различные семейства графов. Круговые раскраски могут быть определены с использованием гомоморфизмов в круговых полных графов, уточняя обычное понятие раскраски. Дробное и b-кратное раскрашивание может быть определенным с помощью гомоморфизмов в графы Кнезера. T-раскраски соответствуют гомоморфизмам в некоторые бесконечные графы. ориентированная раскраска ориентированного графа является гомоморфизмом в любой ориентированный граф. L (2,1) -раскраска является гомоморфизмом в дополнение к графу путей, которое является локально инъективным, что означает, что оно должно быть инъективным на окрестность каждой вершины.
Еще одна интересная связь касается ориентации графов. Ориентация неориентированного графа G - это любой ориентированный граф, полученный путем выбора одной из двух возможных ориентаций для каждого ребра. Примером ориентации полного графа K k является транзитивный турнир T→kс вершинами 1,2,…, k и дугами от i до j всякий раз, когда i < j. A homomorphism between orientations of graphs G and H yields a homomorphism between the undirected graphs G and H, simply by disregarding the orientations. On the other hand, given a homomorphism G → H between undirected graphs, any orientation H→графа H можно вернуть назад. в ориентацию G→группы G, так что G→имеет гомоморфизм с H→. Следовательно, граф G является k-раскрашиваемым (имеет гомоморфизм в K k) тогда и только тогда, когда некоторая ориентация G имеет гомоморфизм в T→k.
. Фольклорная теорема утверждает, что для всех k ориентированный граф G имеет гомоморфизм в T→kтогда и только тогда, когда он не допускает гомоморфизма из ориентированного пути P→k + 1. Здесь P→n- ориентированный граф с вершинами 1, 2,…, n и ребрами от i до i + 1, для i = 1, 2,…, n - 1. Следовательно, граф является k-раскрашиваемым тогда и только тогда. если он имеет ориентацию, не допускающую гомоморфизма из P→k + 1. Это утверждение можно немного усилить, чтобы сказать, что граф является k-раскрашиваемым тогда и только тогда, когда некоторая ориентация не содержит ориентированного пути длины k (нет P→k + 1 в качестве подграфа). Это теорема Галлаи-Хассе-Роя-Витавера.
График H непоследовательных дней недели, изоморфный дополнительному графу из C 7 и в круговую клику K 7/2 Некоторые задачи планирования можно смоделировать как вопрос о поиске гомоморфизмов графов. Например, можно назначить курсы семинаров по временным интервалам в календаре, чтобы два курса, которые посещает один и тот же студент, не находились слишком близко друг к другу по времени. Курсы образуют граф G с ребром между любыми двумя курсами, которые посещает какой-нибудь обычный студент. Временные интервалы образуют граф H с ребром между любыми двумя интервалами, достаточно удаленными во времени. Например, если кто-то хочет циклический, еженедельный график, такой, что каждый студент получает свои курсы семинара в непоследовательные дни, то H будет дополнительным графом C 7. Гомоморфизм графа от G к H - это тогда расписание, назначающее курсы по временным интервалам, как указано. Чтобы добавить требование о том, что, например, ни у одного студента нет курсов одновременно в пятницу и понедельник, достаточно удалить соответствующий край из H.
Можно указать простую задачу распределения частот. следующим образом: ряд передатчиков в беспроводной сети должны выбрать частотный канал, по которому они будут передавать данные. Чтобы избежать помех, географически близкие передатчики должны использовать каналы с удаленными друг от друга частотами. Если это условие аппроксимируется одним порогом для определения «географически близко» и «далеко друг от друга», то правильный выбор канала снова соответствует гомоморфизму графа. Он должен идти от графа передатчиков G с ребрами между парами, которые географически близки, к графу каналов H с ребрами между каналами, которые находятся далеко друг от друга. Хотя эта модель довольно упрощена, она допускает некоторую гибкость: пары передатчиков, которые не расположены близко, но могут создавать помехи из-за географических особенностей, могут быть добавлены к краям G. Те, которые не взаимодействуют одновременно, могут быть удалены из нее. Точно так же пары каналов, которые находятся далеко друг от друга, но демонстрируют гармонические помехи, могут быть удалены из граничного набора H.
В каждом случае эти упрощенные модели отображают многие из проблем, которые необходимо устранить. решается на практике. Проблемы удовлетворения ограничений, которые обобщают проблемы гомоморфизма графов, могут выражать различные дополнительные типы условий (такие как индивидуальные предпочтения или границы количества совпадающих назначений). Это позволяет сделать модели более реалистичными и практичными.
Графы и ориентированные графы можно рассматривать как частный случай гораздо более общего понятия, называемого реляционными структурами (определенными как набор с кортежем отношений в теме). Направленные графы - это структуры с одним бинарным отношением (смежностью) в области (наборе вершин). С этой точки зрения гомоморфизмы таких структур являются в точности гомоморфизмами графов. В общем, вопрос о нахождении гомоморфизма одной реляционной структуры в другую - это проблема удовлетворения ограничений (CSP). Случай с графами дает конкретный первый шаг, который помогает понять более сложные CSP. Многие алгоритмические методы поиска гомоморфизмов графов, такие как отслеживание с возвратом, распространение ограничений и локальный поиск, применимы ко всем CSP.
Для графов G и H, вопрос о том, имеет ли G гомоморфизм к H, соответствует экземпляру CSP только с одним видом ограничений, как показано ниже. Переменные - это вершины G, а область определения для каждой переменной - это набор вершин H. Оценка - это функция, которая присваивает каждой переменной элемент области, поэтому функция f от V (G) до V (H). Каждое ребро или дуга (u, v) графа G соответствует ограничению ((u, v), E (H)). Это ограничение, выражающее то, что оценка должна отображать дугу (u, v) в пару (f (u), f (v)), которая находится в отношении E (H), то есть в дугу H. Решение CSP - это оценка, которая учитывает все ограничения, поэтому это в точности гомоморфизм от G к H.
Композиции гомоморфизмов являются гомоморфизмами. В частности, отношение → на графах транзитивно (и тривиально рефлексивно), так что это предпорядок на графах. Пусть класс эквивалентности графа G при гомоморфной эквивалентности равен [G]. Класс эквивалентности также может быть представлен единственным ядром в [G]. Отношение → является частичным порядком на этих классах эквивалентности; он определяет poset.
Пусть G < H denote that there is a homomorphism from G to H, but no homomorphism from H to G. The relation → is a плотный порядок, что означает, что для всех (неориентированных) графов G, H такие, что G < H, there is a graph K such that G < K < H (this holds except for the trivial cases G = K0или K 1). Например, между любыми двумя полными графами (кроме K 0, K 1) существует бесконечно много круговых полных графов, соответствующих рациональные числа между натуральными числами.
Чумом классов эквивалентности графов при гомоморфизмах является дистрибутивная решетка с определенным соединением из [G] и [H] как (класс эквивалентности) дизъюнктного объединения [G ∪ H], а соответствует из [G] и [H], определенному как тензорное произведение [G × H] ( выбор графов G и H, представляющих классы эквивалентности [G] и [H], не имеет значения). неразложимые по соединению элементы этой решетки - это в точности связные графы. Это можно показать, используя тот факт, что гомоморфизм отображает связный граф в одну связную компоненту целевого графа. встречно-неприводимые элементы этой решетки - это в точности мультипликативные графы. Это такие графы K, что произведение G × H имеет гомоморфизм в K только тогда, когда один из G или H. Идентификация мультипликативных графов лежит в основе гипотезы Хедетниеми.
Гомоморфизмы графов также образуют категорию, где графы являются объектами, а гомоморфизмы - стрелками. Начальный объект - это пустой граф, а конечный объект - это граф с одной вершиной и одним циклом в этой вершине. тензорное произведение графов представляет собой теоретико-категориальный продукт, а экспоненциальный граф является экспоненциальным объектом для этой категории. Поскольку эти две операции всегда определены, категория графов является декартовой замкнутой категорией. По той же причине решетка классов эквивалентности графов при гомоморфизмах фактически является алгеброй Гейтинга.
Для ориентированных графов применимы те же определения. В частности → является частичным порядком на классах эквивалентности ориентированных графов. Он отличается от порядка → на классах эквивалентности неориентированных графов, но содержит его как подпорядок. Это связано с тем, что каждый неориентированный граф можно рассматривать как ориентированный граф, в котором каждая дуга (u, v) появляется вместе со своей обратной дугой (v, u), и это не меняет определения гомоморфизма. Порядок → для ориентированных графов снова представляет собой дистрибутивную решетку и алгебру Гейтинга с операциями соединения и встречи, определенными, как и раньше. Однако он не плотный. Также существует категория с ориентированными графами как объектами и гомоморфизмами как стрелками, которая снова является декартовой замкнутой категорией.
Граф Грёча, несравнимый с K 3Есть много несравнимых графов относительно к предпорядку гомоморфизма, то есть парам графов, у которых ни один из них не допускает гомоморфизма в другой. Один из способов их построения - рассмотреть нечетный обхват графа G, длину его кратчайшего цикла нечетной длины. Нечетный обхват эквивалентно наименьшему нечетному числу g, для которого существует гомоморфизм из циклического графа на g вершинах в G. По этой причине, если G → H, то нечетный обхват G больше или равен нечетному обхвату H.
С другой стороны, если G → H, то хроматическое число G меньше или равно хроматическому числу H Следовательно, если G имеет строго больший нечетный обхват, чем H, и строго большее хроматическое число, чем H, то G и H несравнимы. Например, граф Грёча является 4-хроматическим и без треугольников (у него обхват 4 и нечетный обхват 5), поэтому он несравним с треугольным графом K 3.
Примеры графов со сколь угодно большими значениями нечетного обхвата и хроматического числа - это графы Кнезера и обобщенные микельские графы. Последовательность таких графов с одновременным увеличением значений обоих параметров дает бесконечно много несравнимых графов (антицепь в предупорядочении гомоморфизма). Другие свойства, такие как плотность предварительного порядка гомоморфизма, могут быть доказаны с использованием таких семейств. Построение графиков с большими значениями хроматического числа и обхвата, а не только с нечетным обхватом, также возможно, но более сложное (см. Обхват и раскраска графиков ).
Среди ориентированных графов гораздо проще найти несравнимые пары. Например, рассмотрим ориентированные циклические графы C →nс вершинами 1, 2,…, n и ребрами от i до i + 1 (для i = 1, 2,…, n - 1) и от n до 1. Существует гомоморфизм из C →nв C →k(n, k ≥ 3) тогда и только тогда, когда n делится на k. В частности, все ориентированные графы циклов C →nс n простым числом несравнимы.
В проблеме гомоморфизма графов экземпляром является пара графов (G, H) и решение - это гомоморфизм от G к H. Общая проблема решения, спрашивающая, есть ли какое-либо решение, является NP-полной. Однако ограничение допустимых экземпляров порождает множество различных проблем, некоторые из которых гораздо легче решить. Методы, применяемые при ограничении левой стороны G, сильно отличаются от методов, применяемых для правой стороны H, но в каждом случае дихотомия (резкая граница между легким и трудным случаями) известна или предполагается.
Проблема гомоморфизма с фиксированным графом H в правой части каждого экземпляра также называется проблемой H-раскраски. Когда H - полный граф K k, это задача k-раскраски графа, которая разрешима за полиномиальное время для k = 0, 1, 2 и NP -заполнить в противном случае. В частности, K 2 -раскрашиваемость графа G эквивалентна тому, что G является двудольным, что может быть проверено за линейное время. В более общем смысле, когда H является двудольным графом, H-окрашиваемость эквивалентна K 2 -раскрашиваемости (или K 0 / K 1 -раскрашиваемости, когда H является пусто / без ребра), поэтому одинаково легко решить. Павол Хелл и Ярослав Нешетржил доказали, что для неориентированных графов никакой другой случай не поддается обработке:
Это также известно как теорема дихотомии для (неориентированных) гомоморфизмов графов, поскольку она разделяет задачи H-раскраски на NP -полные проблемы или проблемы P, без промежуточных случаев. Для ориентированных графов ситуация более сложная и фактически эквивалентна гораздо более общему вопросу о характеристике сложности задач удовлетворения ограничений. Оказывается, проблемы H-раскраски для ориентированных графов столь же общие и разнообразные, как и задачи CSP с любыми другими видами ограничений. Формально (конечный) язык ограничений (или шаблон) Γ - это конечная область и конечный набор отношений в этой области. CSP (Γ) - это проблема удовлетворения ограничений, когда экземплярам разрешено использовать только ограничения в Γ.
Интуитивно это означает, что любой алгоритм или результат сложности, применимый к задачам H-раскраски для ориентированных графов H, также применим и к общим CSP. В частности, возникает вопрос, можно ли распространить теорему Хелла – Нешетрила на ориентированные графы. По приведенной выше теореме это эквивалентно гипотезе Федера – Варди (также известной как гипотеза CSP, гипотеза дихотомии) о дихотомии CSP, которая утверждает, что для любого языка ограничений Γ, CSP (Γ) является NP-полным или в P.. Эта гипотеза был независимо доказан в 2017 году Дмитрием Жуком и Андреем Булатовым, что привело к следующему следствию:
Проблема гомоморфизма с единственным фиксированным графом G слева от входных экземпляров может быть решена с помощью грубой силы в time | V (H) |, поэтому размер входного графа H полиномиален. Другими словами, проблема тривиальна в P для графов G ограниченного размера. Тогда возникает интересный вопрос, какие еще свойства G, помимо размера, делают возможными полиномиальные алгоритмы.
Ключевым свойством оказывается treewidth, мера того, насколько древовидный граф. Для графа G с шириной не более k и графа H проблема гомоморфизма может быть решена за время | V (H) | со стандартным подходом динамического программирования. Фактически, достаточно предположить, что ядро G имеет ширину дерева не более k. Это верно, даже если ядро неизвестно.
Показатель в алгоритме | V (H) | -время не может быть значительно уменьшен: ни один алгоритм с временем выполнения | V (H) | существует, предполагая гипотезу экспоненциального времени (ETH), даже если входные данные ограничены любым классом графов неограниченной ширины дерева. ETH - это бездоказательное предположение, подобное P ≠ NP, но более сильное. При том же предположении также, по существу, нет других свойств, которые можно было бы использовать для получения алгоритмов с полиномиальным временем. Это формализовано следующим образом:
, проблема гомоморфизма для экземпляров 
с 
находится в P тогда и только тогда, когда графики в имеют ядра с ограниченной шириной дерева (при условии, что ETHМожно спросить, разрешима ли проблема за время, произвольно сильно зависящее от G, но с фиксированной полиномиальной зависимостью от размера H. Ответ снова будет положительным, если мы ограничим G классом графов. с ядрами ограниченной ширины дерева и отрицательными для всех остальных классов. На языке параметризованной сложности это формально утверждает, что проблема гомоморфизма в
Те же утверждения в более общем смысле справедливы для проблем удовлетворения ограничений (или, другими словами, для реляционных структур). Единственное необходимое предположение состоит в том, что ограничения могут включать только ограниченное число переменных (все отношения имеют некоторую ограниченную арность, 2 в случае графов). Тогда релевантным параметром является ширина дерева графа первичных ограничений.
