В математической области теории графов гомоморфизм графов — это отображение между двумя графами , которое учитывает их структуру. Более конкретно, это функция между множествами вершин двух графов, которая отображает смежные вершины в смежные вершины.
Гомоморфизмы обобщают различные понятия раскрасок графов и позволяют выразить важный класс проблем удовлетворения ограничений , таких как определенные задачи планирования или назначения частот . [1] Тот факт, что гомоморфизмы могут быть составлены, приводит к богатым алгебраическим структурам: предпорядку на графах, дистрибутивной решетке и категории (одной для неориентированных графов и одной для ориентированных графов). [2] Вычислительная сложность нахождения гомоморфизма между заданными графами в общем случае непомерно высока, но много известно о специальных случаях, которые разрешимы за полиномиальное время . Границы между разрешимыми и неразрешимыми случаями были активной областью исследований. [3]
В этой статье, если не указано иное, графы являются конечными, неориентированными графами с разрешенными петлями , но запрещенными кратными ребрами (параллельными ребрами). Гомоморфизм графа [4] f из графа в граф , записанный
— функция из в , которая сохраняет ребра. Формально, подразумевает , для всех пар вершин в . Если существует какой-либо гомоморфизм из G в H , то говорят, что G гомоморфен H или H -раскрашиваем . Это часто обозначается просто как
Приведенное выше определение распространяется на направленные графы. Тогда для гомоморфизма f : G → H , ( f ( u ), f ( v )) является дугой (направленным ребром) H всякий раз, когда ( u , v ) является дугой G .
Существует инъективный гомоморфизм из G в H (т. е. такой, который отображает различные вершины в G в различные вершины в H ) тогда и только тогда, когда G изоморфен подграфу H . Если гомоморфизм f : G → H является биекцией , а его обратная функция f −1 также является гомоморфизмом графа , то f является изоморфизмом графа. [5]
Покрывающие карты — это особый вид гомоморфизмов, которые отражают определение и многие свойства покрывающих карт в топологии . [6] Они определяются как сюръективные гомоморфизмы (т. е. что-то отображается в каждую вершину), которые также локально биективны, то есть являются биекцией на окрестности каждой вершины. Примером является двудольное двойное покрытие , образованное из графа путем разбиения каждой вершины v на v 0 и v 1 и замены каждого ребра u , v ребрами u 0 , v 1 и v 0 , u 1 . Функция, отображающая v 0 и v 1 в покрытии в v в исходном графе, является гомоморфизмом и покрывающим отображением.
Гомеоморфизм графа — это другое понятие, не связанное напрямую с гомоморфизмами. Грубо говоря, он требует инъективности, но позволяет отображать ребра в пути (а не только в ребра). Миноры графа — это еще более расслабленное понятие.
Два графа G и H гомоморфно эквивалентны , если G → H и H → G . [4] Карты не обязательно сюръективны или инъективны. Например, полные двудольные графы K 2,2 и K 3,3 гомоморфно эквивалентны: каждая карта может быть определена как взятие левой (соответственно правой) половины графа домена и отображение только одной вершины в левой (соответственно правой) половине графа изображения.
Ретракция — это гомоморфизм r из графа G в подграф H графа G такой, что r ( v ) = v для каждой вершины v графа H. В этом случае подграф H называется ретрактом графа G . [7]
Ядро — это граф без гомоморфизма ни к какому собственному подграфу. Эквивалентно, ядро можно определить как граф, который не стягивается ни к какому собственному подграфу. [ 8] Каждый граф G гомоморфно эквивалентен уникальному ядру (с точностью до изоморфизма), называемому ядром G. [9] Примечательно, что это неверно в общем случае для бесконечных графов. [ 10] Однако те же определения применимы к направленным графам, и направленный граф также эквивалентен уникальному ядру. Каждый граф и каждый направленный граф содержат свое ядро как ретракт и как индуцированный подграф . [7]
Например, все полные графы K n и все нечетные циклы ( графы циклов нечетной длины) являются ядрами. Каждый 3-раскрашиваемый граф G , содержащий треугольник (то есть имеющий полный граф K 3 в качестве подграфа), гомоморфно эквивалентен K 3 . Это происходит потому, что, с одной стороны, 3-раскраска графа G совпадает с гомоморфизмом G → K 3 , как объясняется ниже. С другой стороны, каждый подграф графа G тривиально допускает гомоморфизм в G , подразумевая K 3 → G . Это также означает, что K 3 является ядром любого такого графа G . Аналогично, каждый двудольный граф , имеющий хотя бы одно ребро, эквивалентен K 2 . [11]
k -раскраска для некоторого целого числа k - это назначение одного из k цветов каждой вершине графа G таким образом , что конечные точки каждого ребра получают разные цвета. k -раскраски графа G в точности соответствуют гомоморфизмам из G в полный граф K k . [12] Действительно, вершины графа K k соответствуют k цветам, и два цвета являются смежными как вершины графа K k тогда и только тогда, когда они различны. Следовательно, функция определяет гомоморфизм графа K k тогда и только тогда, когда она отображает смежные вершины графа G в разные цвета (т. е. является k -раскраской). В частности, граф G является k -раскрашиваемым тогда и только тогда, когда он является K k -раскрашиваемым. [12]
Если есть два гомоморфизма G → H и H → K k , то их композиция G → K k также является гомоморфизмом. [13] Другими словами, если граф H можно раскрасить в k цветов, и существует гомоморфизм из G в H , то G также можно раскрасить в k цветов. Следовательно, G → H подразумевает χ( G ) ≤ χ( H ), где χ обозначает хроматическое число графа (наименьшее k , для которого он является k -раскрашиваемым). [14]
Общие гомоморфизмы также можно рассматривать как своего рода раскраску: если вершины фиксированного графа H являются доступными цветами , а ребра H описывают, какие цвета совместимы , то H -раскраска графа G представляет собой назначение цветов вершинам G таким образом, что смежные вершины получают совместимые цвета. Многие понятия раскраски графа укладываются в этот шаблон и могут быть выражены как гомоморфизмы графа в различные семейства графов. Круговые раскраски могут быть определены с помощью гомоморфизмов в круговые полные графы , уточняя обычное понятие раскраски. [15] Дробная и b -кратная раскраска может быть определена с помощью гомоморфизмов в графы Кнезера . [16] T-раскраски соответствуют гомоморфизмам в некоторые бесконечные графы. [17] Ориентированная раскраска ориентированного графа является гомоморфизмом в любой ориентированный граф . [18] L (2,1)-раскраска — это гомоморфизм в дополнение к графу путей , который локально инъективен, то есть он должен быть инъективен в окрестности каждой вершины. [19]
Другая интересная связь касается ориентаций графов. Ориентация неориентированного графа G — это любой ориентированный граф, полученный выбором одной из двух возможных ориентаций для каждого ребра. Примером ориентации полного графа K k является транзитивный турнир T → k с вершинами 1,2,…, k и дугами от i до j всякий раз, когда i < j . Гомоморфизм между ориентациями графов G и H дает гомоморфизм между неориентированными графами G и H , просто игнорируя ориентации. С другой стороны, если задан гомоморфизм G → H между неориентированными графами, любая ориентация H → графа H может быть возвращена к ориентации G → графа G так, что G → имеет гомоморфизм в H → . Следовательно, граф G является k -раскрашиваемым (имеет гомоморфизм в K k ) тогда и только тогда, когда некоторая ориентация графа G имеет гомоморфизм в T → k . [20]
Фольклорная теорема утверждает, что для всех k ориентированный граф G имеет гомоморфизм в T → k тогда и только тогда, когда он не допускает гомоморфизма из направленного пути P → k +1 . [21] Здесь P → n — ориентированный граф с вершинами 1, 2, …, n и ребрами от i до i + 1, для i = 1, 2, …, n − 1. Следовательно, граф является k -раскрашиваемым тогда и только тогда, когда он имеет ориентацию, которая не допускает гомоморфизма из P → k +1 . Это утверждение можно немного усилить, сказав, что граф является k -раскрашиваемым тогда и только тогда, когда некоторая ориентация не содержит направленного пути длины k (никакого P → k +1 как подграфа). Это теорема Галлаи–Хассе–Роя–Витавера .
Некоторые проблемы планирования можно смоделировать как вопрос о поиске гомоморфизмов графов. [22] [23] Например, можно захотеть назначить курсы семинаров временным интервалам в календаре так, чтобы два курса, которые посещает один и тот же студент, не были слишком близки друг к другу по времени. Курсы образуют граф G с ребром между любыми двумя курсами, которые посещает какой-то общий студент. Временные интервалы образуют граф H с ребром между любыми двумя интервалами, которые достаточно далеки во времени. Например, если требуется циклическое еженедельное расписание, такое, что каждый студент получает свои курсы семинаров в непоследовательные дни, то H будет дополнительным графом C 7 . Тогда гомоморфизм графа из G в H является расписанием, назначающим курсы временным интервалам, как указано. [22] Чтобы добавить требование, гласящее, например, что ни один студент не имеет курсов и в пятницу, и в понедельник, достаточно удалить соответствующее ребро из H .
Простая задача распределения частот может быть определена следующим образом: несколько передатчиков в беспроводной сети должны выбрать частотный канал, на котором они будут передавать данные. Чтобы избежать помех , передатчики, которые географически близки, должны использовать каналы с частотами, которые находятся далеко друг от друга. Если это условие аппроксимировать одним порогом для определения «географически близко» и «далеко друг от друга», то допустимый выбор канала снова соответствует гомоморфизму графа. Он должен идти от графа передатчиков G с ребрами между парами, которые находятся географически близко, к графу каналов H с ребрами между каналами, которые находятся далеко друг от друга. Хотя эта модель довольно упрощена, она допускает некоторую гибкость: пары передатчиков, которые не находятся близко, но могут мешать из-за географических особенностей, могут быть добавлены к ребрам G. Те, которые не взаимодействуют одновременно, могут быть удалены из него. Аналогично пары каналов, которые находятся далеко друг от друга, но демонстрируют гармонические помехи , могут быть удалены из набора ребер H. [24]
В каждом случае эти упрощенные модели отображают множество проблем, которые приходится решать на практике. [25] Задачи удовлетворения ограничений , которые обобщают задачи гомоморфизма графов, могут выражать различные дополнительные типы условий (такие как индивидуальные предпочтения или ограничения на количество совпадающих назначений). Это позволяет сделать модели более реалистичными и практичными.
Графы и направленные графы можно рассматривать как частный случай гораздо более общего понятия, называемого реляционными структурами (определяемыми как множество с кортежем отношений на нем). Направленные графы — это структуры с одним бинарным отношением (смежностью) на домене (множестве вершин). [26] [3] Согласно этой точке зрения, гомоморфизмы таких структур являются именно гомоморфизмами графов. В общем случае вопрос о нахождении гомоморфизма из одной реляционной структуры в другую является проблемой удовлетворения ограничений (CSP). Случай графов дает конкретный первый шаг, который помогает понять более сложные CSP. Многие алгоритмические методы для нахождения гомоморфизмов графов, такие как откат , распространение ограничений и локальный поиск , применимы ко всем CSP. [3]
Для графов G и H вопрос о том, имеет ли G гомоморфизм в H, соответствует экземпляру CSP с единственным видом ограничения, [3] как указано ниже. Переменные являются вершинами 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 .
Композиции гомоморфизмов являются гомоморфизмами. [13] В частности, отношение → на графах транзитивно (и рефлексивно, тривиально), поэтому оно является предпорядком на графах. [27] Пусть класс эквивалентности графа G при гомоморфной эквивалентности будет [ G ]. Класс эквивалентности также может быть представлен уникальным ядром в [ G ]. Отношение → является частичным порядком на этих классах эквивалентности; оно определяет частично упорядоченное множество . [28]
Пусть G < H обозначает, что существует гомоморфизм из G в H , но нет гомоморфизма из H в G. Отношение → является плотным порядком , что означает, что для всех (неориентированных) графов G , H, таких что G < H , существует граф K, такой что G < K < H (это справедливо, за исключением тривиальных случаев G = K 0 или K 1 ). [29] [30] Например, между любыми двумя полными графами (за исключением K 0 , K 1 , K 2 ) существует бесконечно много круговых полных графов , соответствующих рациональным числам между натуральными числами. [31]
ЧУМ классов эквивалентности графов при гомоморфизмах является дистрибутивной решеткой , в которой объединение [ G ] и [ H ] определяется как (класс эквивалентности) несвязного объединения [ G ∪ H ], а пересечение [ G ] и [ H ] определяется как тензорное произведение [ G × H ] (выбор графов G и H, представляющих классы эквивалентности [ G ] и [ H ], не имеет значения). [32] Неприводимые к объединению элементы этой решетки являются в точности связными графами. Это можно показать, используя тот факт, что гомоморфизм отображает связный граф в одну связную компоненту целевого графа. [33] [34] Неприводимые к объединению элементы этой решетки являются в точности мультипликативными графами . Это графы K, такие что произведение G × H имеет гомоморфизм в K только тогда, когда один из G или H также имеет. Выявление мультипликативных графов лежит в основе гипотезы Хедетниеми . [35] [36]
Гомоморфизмы графов также образуют категорию , с графами в качестве объектов и гомоморфизмами в качестве стрелок. [37] Начальный объект — пустой граф, в то время как конечный объект — граф с одной вершиной и одной петлей в этой вершине. Тензорное произведение графов — это теоретико-категорное произведение , а экспоненциальный граф — это экспоненциальный объект для этой категории. [36] [38] Поскольку эти две операции всегда определены, категория графов является декартово замкнутой категорией . По той же причине решетка классов эквивалентности графов относительно гомоморфизмов фактически является алгеброй Гейтинга . [36] [38]
Для ориентированных графов применяются те же определения. В частности, → — это частичный порядок на классах эквивалентности ориентированных графов. Он отличается от порядка → на классах эквивалентности неориентированных графов, но содержит его как подпорядок. Это потому, что каждый неориентированный граф можно рассматривать как ориентированный граф, где каждая дуга ( u , v ) появляется вместе со своей обратной дугой ( v , u ), и это не меняет определения гомоморфизма. Порядок → для ориентированных графов снова является дистрибутивной решеткой и алгеброй Гейтинга с операциями join и meet, определенными как и раньше. Однако он не является плотным. Существует также категория с ориентированными графами в качестве объектов и гомоморфизмами в качестве стрелок, которая снова является декартово замкнутой категорией . [39] [38]
Существует много несравнимых графов относительно предпорядка гомоморфизма, то есть пар графов, ни один из которых не допускает гомоморфизма в другой. [40] Один из способов их построения — рассмотреть нечетный обхват графа G , длину его кратчайшего цикла нечетной длины. Нечетный обхват — это, что эквивалентно, наименьшее нечетное число g, для которого существует гомоморфизм из графа-цикла на g вершинах в G. По этой причине, если G → H , то нечетный обхват G больше или равен нечетному обхвату H. [41 ]
С другой стороны, если G → H , то хроматическое число G меньше или равно хроматическому числу H . Следовательно, если G имеет строго больший нечетный обхват, чем H , и строго большее хроматическое число, чем H , то G и H несравнимы. [40] Например, граф Грётша является 4-хроматическим и не содержит треугольников (его обхват равен 4, а нечетный — 5), [42] поэтому он несравним с треугольным графом K 3 .
Примерами графов с произвольно большими значениями нечетного обхвата и хроматического числа являются графы Кнезера [43] и обобщенные графы Мыцельскиана . [44] Последовательность таких графов с одновременно увеличивающимися значениями обоих параметров дает бесконечно много несравнимых графов ( антицепь в предпорядке гомоморфизма). [45] Другие свойства, такие как плотность предпорядка гомоморфизма, могут быть доказаны с использованием таких семейств. [46] Построения графов с большими значениями хроматического числа и обхвата, не только нечетного обхвата, также возможны, но более сложные (см. Обхват и раскраска графа ).
Среди ориентированных графов гораздо проще найти несравнимые пары. Например, рассмотрим ориентированные графы циклов 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 простым числом все несравнимы. [47]
В задаче гомоморфизма графов экземпляр — это пара графов ( G , H ), а решение — гомоморфизм из G в H. Общая задача принятия решений , спрашивающая, существует ли какое-либо решение, является NP-полной . [48] Однако ограничение допустимых экземпляров приводит к появлению множества различных проблем, некоторые из которых гораздо проще решить. Методы, применяемые при ограничении левой стороны G, сильно отличаются от методов для правой стороны H , но в каждом случае известна или предполагается дихотомия (резкая граница между легкими и сложными случаями).
Проблема гомоморфизма с фиксированным графом H в правой части каждого примера также называется проблемой H -раскраски. Когда H является полным графом K k , это проблема k -раскраски графа , которая разрешима за полиномиальное время для k = 0, 1, 2 и NP-полная в противном случае. [49] В частности, K 2 -раскрашиваемость графа G эквивалентна тому, что G является двудольным , что можно проверить за линейное время. В более общем случае, когда H является двудольным графом, H -раскрашиваемость эквивалентна K 2 -раскрашиваемости (или K 0 / K 1 -раскрашиваемости, когда H пуст/без рёбер), поэтому ее одинаково легко решить. [50] Павол Хелл и Ярослав Нешетржил доказали, что для неориентированных графов никакой другой случай не поддается решению:
Это также известно как теорема о дихотомии для (неориентированных) гомоморфизмов графов, поскольку она делит проблемы H -раскраски на NP-полные или P-проблемы без промежуточных случаев. Для ориентированных графов ситуация более сложная и фактически эквивалентна гораздо более общему вопросу характеристики сложности проблем удовлетворения ограничений . [53] Оказывается, что проблемы H -раскраски для ориентированных графов столь же общие и разнообразные, как и CSP с любыми другими видами ограничений. [54] [55] Формально, (конечный) язык ограничений (или шаблон ) Γ представляет собой конечную область и конечное множество отношений над этой областью. CSP( Γ ) представляет собой проблему удовлетворения ограничений, где экземплярам разрешено использовать только ограничения в Γ .
Интуитивно это означает, что каждый алгоритмический прием или результат сложности, применимый к задачам H -раскраски для ориентированных графов H, применим также и к общим CSP. В частности, можно спросить, можно ли теорему Хелла–Нешетрила распространить на ориентированные графы. Согласно приведенной выше теореме, это эквивалентно гипотезе Федера–Варди (также известной как гипотеза CSP, гипотеза дихотомии) о дихотомии CSP, которая утверждает, что для каждого языка ограничений Γ , CSP( Γ ) является NP-полным или находится в P. [48] Эта гипотеза была доказана в 2017 году независимо Дмитрием Жуком и Андреем Булатовым, что привело к следующему следствию:
Проблема гомоморфизма с одним фиксированным графом G слева от входных экземпляров может быть решена методом грубой силы за время | V ( H )| O(| V ( G )|) , то есть полиномиально по размеру входного графа H . [56] Другими словами, проблема тривиальна по P для графов G ограниченного размера. Тогда интересный вопрос заключается в том, какие другие свойства G , помимо размера, делают полиномиальные алгоритмы возможными.
Ключевым свойством оказывается treewidth , мера того, насколько граф похож на дерево. Для графа G с treewidth не более k и графа H проблема гомоморфизма может быть решена за время | V ( H )| O( k ) с помощью стандартного подхода динамического программирования . Фактически, достаточно предположить, что ядро G имеет treewidth не более k . Это справедливо, даже если ядро неизвестно. [57] [58]
Экспонента в алгоритме | V ( H )| O( k ) -времени не может быть значительно снижена: не существует алгоритма со временем выполнения | V ( H )| o(tw( G ) /log tw( G )) при условии гипотезы экспоненциального времени (ETH), даже если входные данные ограничены любым классом графов неограниченной древовидной ширины. [59] ETH является недоказанным предположением, аналогичным P ≠ NP , но более сильным. При том же предположении также по существу нет других свойств, которые можно использовать для получения алгоритмов с полиномиальным временем. Это формализуется следующим образом:
Можно спросить, разрешима ли проблема по крайней мере за время, произвольно сильно зависящее от G , но с фиксированной полиномиальной зависимостью от размера H . Ответ снова положительный, если мы ограничим G классом графов с ядрами ограниченной древесной ширины, и отрицательный для любого другого класса. [58] На языке параметризованной сложности это формально утверждает, что проблема гомоморфизма в , параметризованная размером (количеством ребер) G , демонстрирует дихотомию. Она является фиксированно-параметрически разрешимой, если графы в имеют ядра ограниченной древесной ширины, и W[1] -полной в противном случае.
Те же утверждения справедливы в более общем смысле для проблем удовлетворения ограничений (или для реляционных структур, другими словами). Единственное необходимое предположение заключается в том, что ограничения могут включать только ограниченное число переменных (все отношения имеют некоторую ограниченную арность, 2 в случае графов). Соответствующим параметром тогда является ширина дерева первичного графа ограничений . [59]
