Это хорошая статья. Для получения дополнительной информации нажмите здесь.
Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску
Не путать с гомеоморфизмом графов .

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

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

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

Определения [ править ]

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

е  : G → 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 → H .

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

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

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

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

Ядра и ретракты [ править ]

K 7 , полный граф с 7 вершинами, является ядром.
Основная статья: Ядро (теория графов)

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

Ретракция гомоморфизма г из графа G в подграфе H из G , такие , что г ( v ) = v для каждой вершины V из 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 цветов для каждой вершины графа G такой , что концы каждого ребра получают разные цвета. В K -раскраска G точно соответствует гомоморфизмам из G в полном графе K к . [12] Действительно, вершины K k соответствуют k цветам, а два цвета смежны как вершины K k тогда и только тогда, когда они различны. Следовательно, функция определяет гомоморфизм в K kтогда и только тогда, когда он отображает смежные вершины графа G в разные цвета (т. е. это k- раскраска). В частности, G является к -раскрашиваемому тогда и только тогда , когда оно 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] л (2,1) -раскраска гомоморфизм в дополнение на пути графа , локально инъективно, то есть он должен быть однозначен на окрестности каждой вершины. [19]

Ориентация без длинных путей [ править ]

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

Еще одна интересная связь касается ориентации графов. Ориентация неориентированного графа 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 . [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 в качестве подграфа). Это теорема Галлаи – Хассе – Роя – Витавера .

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

Примеры [ править ]

График H непоследовательных дней недели, изоморфный графу дополнений к C 7 и круговой клике K 7/2

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

Простая задача распределения частот может быть определена следующим образом: ряд передатчиков в беспроводной сети должны выбрать частотный канал, по которому они будут передавать данные. Чтобы избежать помех , географически близкие передатчики должны использовать каналы с удаленными друг от друга частотами. Если это условие аппроксимируется одним порогом для определения «географически близко» и «далеко друг от друга», то правильный выбор канала снова соответствует гомоморфизму графа. Он должен идти от графа передатчиков G с географически близкими ребрами между парами к графу каналов H, с краями между каналами, которые далеко друг от друга. Несмотря на то , что эта модель весьма упрощена, она делает некоторые допускают гибкость: пары передатчиков, которые не близки , но могут создавать помехи из - за географических особенностей могут добавлены к краям G . Те, кто не общаются при этом, могут быть удалены из него. Точно так же канальные пары, которые далеки друг от друга , но демонстрируют гармонические помехи могут быть удалены от края набора Н . [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 ( об )) , который в соотношении Е ( Н ), то есть, к дуге Н . Решение СПС является оценка , которая уважает все ограничения, так что это именно гомоморфизм из 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 или К 1 ). [29] [30]Например, между любыми двумя полными графами (кроме K 0 , K 1 ) существует бесконечно много круговых полных графов , соответствующих рациональным числам между натуральными числами. [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 ), и это не меняет определения гомоморфизма. Порядок → для ориентированных графов снова представляет собой дистрибутивную решетку и алгебру Гейтинга с операциями соединения и встречи, определенными, как и раньше. Однако он не плотный. Также существует категория, в которой ориентированные графы являются объектами, а гомоморфизмы - стрелками.декартова закрытая категория . [39] [38]

Несравненные графики [ править ]

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

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

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

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

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

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

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

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

Проблема гомоморфизма с единственным фиксированным графом G слева от входных экземпляров может быть решена методом перебора по времени | V ( H ) | O (| V ( G ) |) , поэтому размер входного графа H полиномиален . [56] Другими словами, проблема тривиальна в P для графов G ограниченного размера. Тогда возникает интересный вопрос, какие еще свойства G , помимо размера, делают возможными полиномиальные алгоритмы.

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

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

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

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

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

См. Также [ править ]

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

Заметки [ править ]

  1. ↑ Hell & Nešetřil 2004 , стр. 27.
  2. ↑ Hell & Nešetřil 2004 , стр. 109.
  3. ^ а б в г Ад и Нешетржил 2008 .
  4. ^ a b Введение см. (в порядке увеличения длины): Cameron (2006) ; Гена и Тардиф (1997) ; Ад и Нешетржил (2004) .
  5. ^ Гена & Tardif 1997 , Наблюдение 2,3.
  6. ^ Godsil & Royle 2001 , стр. 115.
  7. ^ a b Hell & Nešetřil 2004 , стр. 19.
  8. ↑ Hell & Nešetřil 2004 , Предложение 1.31.
  9. ^ Кэмерон 2006 , Предложение 2.3; Hell & Nešetřil 2004 , следствие 1.32.
  10. ↑ Hell & Nešetřil 2004 , стр. 34.
  11. Перейти ↑ Cameron 2006 , p. 4, предложение 2.5.
  12. ^ a b Кэмерон 2006 , стр. 1; Hell & Nešetřil 2004 , Предложение 1.7.
  13. ^ a b Hell & Nešetřil 2004 , §1.7.
  14. ↑ Hell & Nešetřil 2004 , Следствие 1.8.
  15. ^ Ад & Nešetřil 2004 , §6.1; Geňa & Tardif 1997 , §4.4.
  16. ^ Ад & Nešetřil 2004 , §6.2; Geňa & Tardif 1997 , §4.5.
  17. ^ Ад & Nešetřil 2004 , §6.3.
  18. ^ Ад & Nešetřil 2004 , §6.4.
  19. ^ Fiala, J .; Kratochvíl, J. (2002), "Частичные покрытия графов", Discussiones Mathematicae Теория графов , 22 (1): 89-99, DOI : 10,7151 / dmgt.1159 , S2CID  17507393
  20. ↑ Hell & Nešetřil 2004 , стр. 13–14.
  21. ↑ Hell & Nešetřil 2004 , Предложение 1.20.
  22. ^ a b Кэмерон 2006 , стр. 1.
  23. ^ Ад & Nešetřil 2004 , пункте 1.8.
  24. ↑ Hell & Nešetřil 2004 , стр. 30–31.
  25. ↑ Hell & Nešetřil 2004 , стр. 31–32.
  26. ↑ Hell & Nešetřil 2004 , стр. 28, обратите внимание, что реляционные структуры там называются реляционными системами .
  27. ↑ Hell & Nešetřil 2004 , §3.1.
  28. ^ Hell & Nešetřil 2004 , Теорема 3.1.
  29. ^ Hell & Nešetřil 2004 , теорема 3.30; Geňa & Tardif 1997 , теорема 2.33.
  30. ^ Welzl, E. (1982), "Цветные семьи плотны", Теоретическая информатика , 17 : 29-41, DOI : 10,1016 / 0304-3975 (82) 90129-3
  31. ↑ Hell & Nešetřil 2004 , стр. 192; Gea & Tardif 1997 , стр. 127.
  32. ^ Hell & Nešetřil 2004 , Предложение 3.2, дистрибутивность указана в предложении 2.4; Гена и Тардиф 1997 , теорема 2.37.
  33. ^ Kwuida, Леонар; Лехтонен, Эркко (2011), «О порядке гомоморфизма помеченных позиций », Order , 28 (2): 251–265, arXiv : 0911.0200 , doi : 10.1007 / s11083-010-9169-x , S2CID 14920600 
  34. ^ Грей 2014 , лемма 3.7.
  35. ^ Tardif, C. (2008), "гипотеза Hedetniemi, в 40 лет спустя" (PDF) , теории графов Примечания Нью - Йорк , 54 : 46-57, MR 2445666  .
  36. ^ a b c Дуайт, Д .; Sauer, Н. (1996), "Решетка , возникающая в категориальном исследовании гипотезы Hedetniemi в", дискретной математике , 152 (1-3): 125-139, DOI : 10.1016 / 0012-365X (94) 00298-W
  37. ↑ Hell & Nešetřil 2004 , стр. 125.
  38. ^ a b c Серый 2014 .
  39. ^ Браун и др. 2008 .
  40. ^ a b Hell & Nešetřil 2004 , стр. 7.
  41. ^ Гена & Tardif 1997 , Наблюдение 2,6.
  42. ^ Вайсштейн, Эрик В. "График Грётча" . MathWorld .
  43. ^ Гена & Tardif 1997 , предложение 3.14.
  44. ^ Gyárfás, A .; Jensen, T .; Stiebitz, M. (2004), "О графах с сильно независимых колор-классов", Журнал теории графов , 46 (1): 1-14, DOI : 10.1002 / jgt.10165
  45. ↑ Hell & Nešetřil 2004 , Предложение 3.4.
  46. ↑ Hell & Nešetřil 2004 , стр. 96.
  47. ↑ Hell & Nešetřil 2004 , стр. 35.
  48. ^ a b Бодирский 2007 , §1.3 .
  49. ^ Ад & Nešetřil 2004 , §5.1.
  50. ↑ Hell & Nešetřil 2004 , Предложение 5.1.
  51. ^ Ад & Nešetřil 2004 , §5.2.
  52. ^ Ад, Павол ; Нешетржил, Ярослав (1990), «О сложности H-раскраски», Журнал комбинаторной теории, серия B , 48 (1): 92–110, DOI : 10.1016 / 0095-8956 (90) 90132-J
  53. ^ Ад & Nešetřil 2004 , §5.3.
  54. ↑ Hell & Nešetřil 2004 , Теорема 5.14.
  55. ^ a b Федер, Томас; Варди, Моше Y. (1998), "Счетная структура монотонной монадических SNP и Constraint Satisfaction: исследование через Datalog и теории групп" , SIAM журнал по вычислениям , 28 (1): 57-104, DOI : 10,1137 / S0097539794266766
  56. ^ Cygan, M .; Фомин Ф.В. Головнев, А .; Куликов АС; Михайлин, И .; Pachocki, J .; Socała, A. (2016). Точные оценки гомоморфизма графов и изоморфизма подграфов . 28-й ежегодный симпозиум ACM-SIAM по дискретным алгоритмам (SODA 2016). СИАМ . С. 1643–1649. arXiv : 1507.03738 . Bibcode : 2015arXiv150703738F . ISBN 978-1-611974-33-1.CS1 maint: использует параметр авторов ( ссылка )
  57. ^ Далмау, Виктор; Колайтис, Phokion G .; Варди, Моше Ю. (2002). Удовлетворение ограничений, ограниченная ширина дерева и логика с конечными переменными . 8-я Международная конференция по принципам и практике программирования с ограничениями (CP 2002). С. 310–326. DOI : 10.1007 / 3-540-46135-3_21 .
  58. ^ a b c Grohe, Мартин (2007), «Сложность проблемы гомоморфизма и удовлетворения ограничений с другой стороны», Журнал ACM , 54 (1): 1 – es, doi : 10.1145 / 1206035.1206036 , S2CID 11797906 
  59. ^ Б Маркс, Даниель (2010), "Можно ли бить древесная ширина?", Теория вычислений , 6 : 85-112, DOI : 10,4086 / toc.2010.v006a005

Ссылки [ править ]

Общие книги и экспозиции [ править ]

  • Кэмерон, П. (2006), Гомоморфизмы графов, Заметки исследовательской группы по комбинаторике (PDF)
  • Ад, Павол ; Нешетржил, Ярослав (2004), Графы и гомоморфизмы , Оксфордская серия лекций по математике и ее приложениям, 28 , Oxford University Press, ISBN 0-19-852817-5
  • Geňa, H .; Tardif, С. (1997), "График гомоморфизмы: структура и симметрия", Graph симметрии: Алгебраические методы и приложения (PDF) , Springer, стр 107-166,. DOI : 10.1007 / 978-94-015-8937-6_4
  • Годсил, К .; Ройл, Г. (2001), «6. Гомоморфизмы», алгебраическая теория графов , «Тексты для выпускников по математике», 207 , Springer – Verlag New York, DOI : 10.1007 / 978-1-4613-0163-9 , ISBN 978-1-4613-0163-9

В удовлетворении ограничений и универсальной алгебре [ править ]

  • Бодирский М. (2007), Гомоморфизмы графов и универсальная алгебра, Заметки к курсу (PDF)
  • Ад, Павол ; Nešetřil, Ярослав (2008), "раскраски, ограничение удовлетворения, и сложность" (PDF) , Computer Science Review , 2 (3): 143-163, DOI : 10.1016 / j.cosrev.2008.10.003

В теории решеток и теории категорий [ править ]

  • Brown, R .; Моррис, I .; Shrimpton, J .; Уэнз, CD (2008), "Графики морфизмов графов" , Электронный журнал комбинаторики , 15 (1): A1, DOI : 10,37236 / 919
  • Грей, CT (2014), Решетка диграфов (PDF)( Стипендии AMSI Vacation Research Scholarship , отчет об исследовании студентов под руководством Брайана Дэви и Джейн Питкетли, Университет Ла Троб ).