Гомоморфизм графов - Graph homomorphism

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

В математической области теории графов , А граф гомоморфизм является отображением между двумя графиками , что уважает их структуру. Более конкретно, это функция между наборами вершин двух графов, которая отображает смежные вершины на соседние вершины.

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

Определения

В этой статье, если не указано иное, графы - это конечные неориентированные графы, в которых разрешены петли , но запрещены множественные ребра (параллельные ребра). Графа гомоморфизм F из графа G = ( V ( G ), Е ( О )) в графе H = ( V ( H ), Е ( Н )), написанной

е : G \to 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 -раскрашиваемым . Это часто обозначается так:

G \to H .

Приведенное выше определение распространяется на ориентированные графы. Тогда для гомоморфизма F : G → H , ( F ( U ), F ( v )) представляет собой дуга (направленное ребро) из Н , когда ( у , v ) представляет собой дуга G .

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

Покрывающие карты - это особый вид гомоморфизмов, которые отражают определение и многие свойства покрывающих карт в топологии . Они определяются как сюръективные гомоморфизмы (т. Е. Что-то отображается в каждую вершину), которые также являются локально биективными, то есть биекцией в окрестности каждой вершины. Примером может служить двудольное двойное покрытие , образованное из графа путем разбиения каждой вершины v на v ₀ и v ₁ и замены каждого ребра u , v ребрами u ₀ , v ₁ и v ₀ , u ₁ . Функциональное отображение v ₀ и v ₁ в покрытии в v в исходном графе является гомоморфизмом и покрывающим отображением.

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

Сердечники и ретракты

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

Два графа G и H являются гомоморфно эквивалентны , если G → H и H → G . Карты не обязательно сюръективны или инъективны. Например, полные двудольные графы K _2,2 и K _3,3 гомоморфно эквивалентны: каждое отображение можно определить как взятие левой (соответственно правой) половины графа области и отображение только одной вершины в левой (соответственно . справа) половина изображения графа.

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

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

Например, все полные графы K _n и все нечетные циклы ( графы циклов нечетной длины) являются ядрами. Каждый 3-раскрашиваемый граф G , содержащий треугольник (т.е. имеющий полный граф K ₃ в качестве подграфа), гомоморфно эквивалентен K ₃ . Это потому, что, с одной стороны, 3-раскраска G - это то же самое, что гомоморфизм G → K ₃ , как объясняется ниже. С другой стороны, каждый подграф G тривиально допускает гомоморфизм в G , подразумевая K ₃ → G . Это также означает , что K ₃ является ядром любого такого графа G . Аналогично, любой двудольный граф , имеющий хотя бы одно ребро, эквивалентен K ₂ .

Подключение к раскраскам

К -раскраска , для некоторого целого числа к , является назначение одного из K цветов для каждой вершины графа G такой , что концы каждого ребра получают разные цвета. В K -раскраска G точно соответствует гомоморфизмам из G в полном графе K _к . Действительно, вершины K _k соответствуют k цветам, а два цвета смежны как вершины K _k тогда и только тогда, когда они различны. Следовательно, функция определяет гомоморфизм в K _k тогда и только тогда, когда она отображает смежные вершины G в разные цвета (т. Е. Это k -раскраска). В частности, G является к -раскрашиваемому тогда и только тогда , когда оно 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 . Гомоморфизм между ориентациями графов G и H дает гомоморфизм между неориентированными графами G и H , просто игнорируя ориентации. С другой стороны, учитывая гомоморфизм G → 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 ₇ и круговой клике K _7/2

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

Простая задача распределения частот может быть определена следующим образом: ряд передатчиков в беспроводной сети должны выбрать частотный канал, по которому они будут передавать данные. Чтобы избежать помех , географически близкие передатчики должны использовать каналы с удаленными друг от друга частотами. Если это условие аппроксимируется одним порогом для определения «географически близко» и «далеко друг от друга», то правильный выбор канала снова соответствует гомоморфизму графа. Он должен идти от графа передатчиков G с ребрами между парами, которые географически близки, к графу каналов H , с ребрами между каналами, которые находятся далеко друг от друга. Несмотря на то , что эта модель весьма упрощена, она делает некоторые допускают гибкость: пары передатчиков, которые не близки , но могут создавать помехи из - за географических особенностей могут добавлены к краям G . Те, кто не общаются при этом, могут быть удалены из него. Точно так же канальные пары, которые далеки друг от друга , но демонстрируют гармонические помехи могут быть удалены от края набора Н .

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

Формальный вид

Графы и ориентированные графы можно рассматривать как частный случай гораздо более общего понятия, называемого реляционными структурами (определяемого как набор с кортежем отношений на нем). Направленные графы - это структуры с одним бинарным отношением (смежностью) в области (наборе вершин). С этой точки зрения гомоморфизмы таких структур являются в точности гомоморфизмами графов. В общем, вопрос о нахождении гомоморфизма от одной реляционной структуры к другой - это проблема удовлетворения ограничений (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 ( об )) , который в соотношении Е ( Н ), то есть, к дуге Н . Решение СПС является оценка , которая уважает все ограничения, так что это именно гомоморфизм из G в H .

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

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

Пусть G < H означает , что существует гомоморфизм из G в H , но не гомоморфизм из H в G . Отношение → является плотным порядком , что означает, что для всех (неориентированных) графов G , H таких, что G < H , существует граф K такой, что G < K < H (это верно, за исключением тривиальных случаев G = K ₀ или К ₁ ). Например, между любыми двумя полными графами (кроме K ₀ , K ₁ ) существует бесконечно много круговых полных графов , соответствующих рациональным числам между натуральными числами.

Ч.у. классов эквивалентности графов при гомоморфизмах является дистрибутивной решеткой , где соединение [ G ] и [ H ] определяется как (класс эквивалентности) дизъюнктного объединения [ G ∪ H ], а пересечение [ G ] и [ H ] определяется как тензорное произведение [ G × H ] (выбор графов G и H, представляющих классы эквивалентности [ G ] и [ H ], не имеет значения). В нарисуй неприводимые элементы этой решетки точно подключены графики. Это можно показать, используя тот факт, что гомоморфизм отображает связный граф в одну связную компоненту целевого графа. В Meet-неприводимые элементы этой решетки в точности мультипликативные графики . Это графы K такие, что произведение G × H имеет гомоморфизм в K только тогда, когда один из G или H также имеет гомоморфизм . Идентификация мультипликативных графов лежит в основе гипотезы Хедетниеми .

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

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

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

Граф Грёча, несравнимый с K ₃

Существует много несравнимых графов относительно предпорядка гомоморфизма, то есть таких пар графов, что ни один из них не допускает гомоморфизма в другой. Один из способов их построения - рассмотреть нечетный обхват графа G , длину его кратчайшего цикла нечетной длины. Нечетное обхват, что то же самое, наименьшее нечетное число г , для которого существует гомоморфизм из графа цикла на г вершин в G . По этой причине, если G → H , то нечетное обхват G больше или равна нечетному обхват H .

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

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

Среди ориентированных графов гораздо проще найти несравнимые пары. Например, рассмотрим ориентированные циклические графы 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-полна в противном случае. В частности, К ₂ -colorability графа G эквивалентна G существо двудольному , которые могут быть испытаны в линейное время. В более общем смысле, когда H является двудольным графом, H -раскрашиваемость эквивалентна K ₂ -раскрашиваемости (или K ₀ / K ₁ -раскрашиваемости, когда H пуста / без ребра), следовательно, такое же простое решение. Павол Хелл и Ярослав Нешетржил доказали, что для неориентированных графов никакой другой случай недопустим:

Теорема Hell – Nešetřil (1990): проблема H -раскраски находится в P, когда H двудольна, и NP-полна в противном случае.

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

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

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

Следствие (Булатов, 2017; Жук, 2017): проблема H -раскраски ориентированных графов при фиксированном H либо в P, либо в NP-полной.

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

Проблема гомоморфизма с единственным фиксированным графом 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 ))} существует, исходя из гипотезы экспоненциального времени (ETH), даже если входные данные ограничены любым классом графов неограниченной ширины дерева. ETH - это недоказанное предположение, подобное P ≠ NP , но более сильное. При том же предположении также, по сути, нет других свойств, которые можно было бы использовать для получения алгоритмов с полиномиальным временем. Это оформляется следующим образом:

Теорема ( Grohe ): для вычислимого класса графов проблема гомоморфизма для экземпляров с находится в P тогда и только тогда, когда графы в имеют ядра ограниченной ширины дерева (при условии ETH).

{\ Displaystyle {\ mathcal {G}}}

{\ displaystyle (G, H)}

{\ displaystyle G \ in {\ mathcal {G}}}

{\ Displaystyle {\ mathcal {G}}}

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

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

Смотрите также

Глоссарий терминов теории графов
Гомоморфизм для одного и того же понятия на разных алгебраических структурах
Переписывание графа
Медианные графы , определяемые как ретракты гиперкубов
Гипотеза Сидоренко

Languages

In other projects