Русская Википедия:Гомоморфизм графов

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

Гомоморфизм графов — это отображение между двумя графами, не нарушающее структуру. Более конкретно, это отображение между набором вершин двух графов, которое отображает смежные вершины в смежные.

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

Определения

В этой статье, если не сказано другое, под графами понимаются конечные неориентированные графы с разрешёнными петлями, но кратные рёбра (параллельные) не разрешены. Гомоморфизм графаШаблон:Sfn Шаблон:Sfn Шаблон:Sfn: f из графа <math>G=(V(G), E(G))</math> в граф <math>H=(V(H), E(H))</math>, что записывается как

<math>f : G \to H</math>,

это функция из V(G) в V(H), которая отображает конечные точки каждого ребра из G в конечные точки некоторого ребра из H. Формально, из <math>\{u,v\} \in E(G)</math> следует <math>\{f(u),f(v)\} \in E(H)</math>, для всех пар вершин u, v из V(G). Если существует некоторый гомоморфизм из G в H, то говорят, что граф G гомоморфен графу H, или что он H-раскрашиваем. Это часто обозначается как

<math>G \to H</math>.

Определение выше распространяется на ориентированные графы. Тогда для гомоморфизма <math>f : G \to H, (f(u),f(v))</math> является дугой (ориентированным ребром) графа H, когда (u,v) является дугой графа G.

Существует инъективный гомоморфизм из G в H (то есть отображение, которое никогда не отображает различные вершины в одну) тогда и только тогда, когда G является подграфом графа H. Если гомоморфизм <math>f : G \to H</math> является биекцией (соответствием один-к-одному между вершинами графа G и графа H) обратная функция которого является также гомоморфизм графа, тогда f является изоморфизмом графов Шаблон:Sfn.

Накрывающие отображения являются частым видом гомоморфизмов, который отражает определение и многие свойства накрытия в топологии Шаблон:Sfn. Они определяются как сюръективные гомоморфизмы, которые локально биективны, то есть является биекцией в окрестности каждой вершины. Примером служит двойное покрытие двудольным графом, образованное из графа путём разбиения каждой вершины v на <math>v_0</math> и <math>v_1</math> и заменой каждого ребра u,v на два ребра <math>u_0,v_1</math> и <math>v_0,u_1</math>. Функция, отображающая v₀ и v₁ в v исходного графа, является гомоморфизмом и накрывыающим отображением.

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

Ядра и ретракты

Файл:Complete graph K7.svg

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

Шаблон:Основная статья

Два графа G и H гомоморфно эквивалентны, если <math>G \to H</math> и <math>H \to G</math>Шаблон:Sfn Шаблон:Sfn Шаблон:Sfn.

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

Ядро — это граф, не имеющий гомоморфизма в любой собственный подграф. Эквивалентно, ядро можно определить как граф, который не является ретрактом для любого собственного подграфаШаблон:Sfn. Любой граф G гомоморфно эквивалентен единственному ядру (с точностью до изоморфизма), которое называется ядром графа GШаблон:Sfn Шаблон:Sfn. Заметим, что это неверно для бесконечных графов общего видаШаблон:Sfn. Однако те же определения применимы и к ориентированным графам и ориентированный граф также эквивалентен единственному ядру. Любой неориентированный и ориентированный граф содержит своё ядро и как ретракт, и как порождённый подграф Шаблон:Sfn.

Например, все полные графы K_n и все нечётные циклы (графов-циклов нечётной длины) являются ядрами. Любой 3-раскрашиваемый граф G, содержащий треугольник (то есть имеет полный граф K₃ в качестве подграфа) гомеоморфно эквивалентен K₃. Это потому, с одной стороны, что 3-раскраска графа G, это то же самое, что и гомоморфизм <math>G \to K_3</math>, как объяснено ниже. С другой стороны, любой подграф графа G тривиально допускает гомоморфизм в G, откуда следует, что <math>K_3 \to G</math>. Это также означает, что K₃ является ядром любого такого графа G. Аналогично, любой двудольный граф, который имеет по меньшей мере одно ребро, эквивалентен K₂Шаблон:Sfn.

Связь с раскрасками

k-Раскраска для некоторого целого k — это назначение одного из k цветов каждой вершине графа G так, что конечные вершины каждого ребра имеют различные цвета. k-Раскраски графа G соответствуют в точности гомоморфизмам из G в полный граф K_kШаблон:Sfn Шаблон:Sfn. Более того, вершины графа K_k соответствуют k цветам и два цвета смежны как вершины графа K_k тогда и только тогда, когда они различны. Следовательно, функция определяет гомоморфизм в K_k тогда и только тогда, когда смежные вершины графа G выкрашены в разные цвета. В частности, граф G k-раскрашиваем тогда и только тогда, когда K_k-раскрашиваемШаблон:Sfn Шаблон:Sfn.

Если есть два гомоморфизма <math>G \to H</math> и <math>H \to K_k</math>, то их суперпозиция <math>G \to K_k</math> является также гомоморфизмШаблон:Sfn. Другими словами, если граф H может быть выкрашен в k цветов и существует гомоморфизм G в H, то G может быть также выкрашен в k цветов. Поэтому из <math>G \to H</math> следует <math>\chi(G) \leqslant \chi(H)</math>, где <math>\chi</math> означает хроматическое число графа (наименьшее число цветов k, в которые можно раскрасить граф)Шаблон:Sfn.

Варианты

Гомоморфизмы общего вида можно рассматривать также как вид раскраски — если вершины фиксированного графа H являются допустимыми цветами, а рёбра графа H описывают, какие цвета совместимы, то H-раскраска графа G — это назначение цветов вершинам графа G так, что смежные вершины получают совместимые цвета. Многие понятия раскраски графов вмещаются в эту схему и могут быть выражены как гомоморфизмы графов в различные семейства графов. Цикловые раскраски можно определить с помощью гомоморфизмов в цикловые полные графы, уточняя обычное понятие раскраскиШаблон:Sfn Шаблон:Sfn. Дробная и b-кратная раскраска могут быть определены с помощью гомоморфизмов в кнезеровские графы Шаблон:Sfn Шаблон:Sfn T-раскраски соответствуют гомоморфизмам в некоторые бесконечные графыШаблон:Sfn. {Ориентированная раскраска ориентированного графа является гомоморфизмом в любой ориентированный граф Шаблон:Sfn. Шаблон:Не переведено 5 — это локально инъективный гомоморфизм в дополнение пути, что означает, что он должен быть инъективным в окрестности каждой вершиныШаблон:R.

Ориентации без длинных путей

Шаблон:Основная статья Другая интересная связь касается ориентации графов. Ориентация неориентированного графа G — это любой ориентированный граф, полученный выбором из двух возможных ориентаций каждого ребра. Примером ориентации полного графа K_k служит транзитивный турнир <math>\vec{T}_k</math> с вершинами 1,2,…,k и дугами из i в j, когда i < j. Гомоморфизм между ориентациями графов G и H даёт гомоморфизм между неориентированными графами G и H, если просто игнорировать ориентации. С другой стороны, если дан гомоморфизм <math>G \to H</math> между неориентированными графами, любая ориентация <math>\vec{H}</math> of H может быть отражена в ориентацию графа <math>\vec{G}</math> of G, так что <math>\vec{G}</math> имеет гомоморфизм в <math>\vec{H}</math>. Поэтому граф G k-раскрашиваем (имеет гомоморфизм в K_k) тогда и только тогда, когда некоторая ориентация G имеет гомоморфизм в <math>\vec{T}_k</math>Шаблон:Sfn.

Фольклорная теорема гласит, что для любых k ориентированный граф G имеет гомоморфизм в <math>\vec{T}_k</math> тогда и только тогда, когда он не допускает гомоморфизма из <math>\vec{P}_{k+1}</math>Шаблон:Sfn. Здесь <math>\vec{P}_n</math> — ориентированный путь с вершинами 1, 2, …, n и дугами из i в i + 1 для i=1, 2, …, n − 1. Таким образом, граф k-раскрашиваем тогда и только тогда, когда он имеет ориентацию, которая не допускает гомоморфизма из <math>\vec{P}_{k+1}</math>. Это утверждение может быть слегка усилено до утверждения, что граф k-раскрашиваем тогда и только тогда, когда некоторая ориентация не содержит ориентированного пути длины k (нет <math>\vec{P}_{k+1}</math> в качестве подграфа). Это Теорема Галлаи — Хассе — Роя — Витавера.

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

Примеры

Файл:Graph of non-adjacent weekdays.svg

Граф H несоседних дней недели изоморфен дополнению графа C₇ и в цикловой клике K_7/2

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

Простая задача Шаблон:Не переведено 5 может быть поставлена следующим образом. Имеется несколько передатчиков беспроводной сети. Нужно выбрать на каждом из них частотный канал, по которому он будет передавать данные. Чтобы избежать помех, географически близкие передатчики должны иметь каналы с достаточно отличающимися частотами. Если это условие ограничено простым порогом для понятия «географически близки» и «доствточно далеки», допустимый выбор каналов соответствует снова гомоморфизму графа. Здесь графом G будет набор передатчиков с рёбрами между ними, если они географически близки, а графом H будет набор каналов с рёбрами между каналами, если частоты достаточно отличаются. Хотя эта модель сильно упрощена, она допускает некоторую гибкость — для пары передатчиков, которые не близки, но могут мешать друг другу ввиду географических особенностей, может быть добавлена дуга в G. А дуга между передатчиками, которые не работают в одно и то же время, может быть из графа удалена. Аналогично, ребро между парой каналов, которые далеко друг от друга, но имеют помехи в виде гармоник может быть удалено из графа HШаблон:Sfn.

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

Формальная точка зрения

Ориентированные и ориентированные графы можно рассматривать как частые случаи более общего понятия, называемого Шаблон:Не переведено 5 (которые определяются как множество с кортежем отношений на нём). Ориентированные графы являются структурами с одним бинарным отношением (смежность) на области (множестве вершин)^[1]Шаблон:Sfn. С этой точки зрения Шаблон:Не переведено 5 таких структур являются в точности гомоморфизмами графов. В общем случае вопрос поиска гомоморфизма из одной структуры в другую является задачей удовлетворения ограничений (Шаблон:Lang-en, CSP). Случай графов даёт конкретный первый шаг, который помогает понять более сложные задачи удовлетворения ограничений. Многие алгоритмические методы поиска гомоморфизмов графа, наподобие поиска с возвратом, Шаблон:Не переведено 5 и Шаблон:Не переведено 5 применимы ко всем задачам удовлетворения ограниченийШаблон:Sfn.

Для графов G и H вопрос, имеет ли граф G гомоморфизм в граф H, соответствует частному случаю задачи удовлетворения ограничений с только одним видом ограниченийШаблон:Sfn. В этой задаче переменными будут вершины графа G, а областью значений каждой переменной будет набор вершин графа H. Решением является функция, которая назначает каждой переменной элемент из области значений, так что функция f отображает V(G) в V(H). Каждое ребро или дуга^[2] (u,v) графа G тогда соответствует ограничению ((u,v), E(H)). Это ограничение выражает, что решение должно отображать дугу (u,v) в пару (f(u),f(v)), которая является отношением E(H), то есть, в дугу графа H. Решением задачи является решение, которое удовлетворяет всем ограничениям, то есть это в точности гомоморфизм из G в H.

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

Суперпозиции гомоморфизмов являются гомоморфизмамиШаблон:Sfn. В частности, отношение <math>\to</math> на графах транзитивно (и, тривиально, рефлексивно), так что это отношение является предпорядком на графахШаблон:Sfn. Будем обозначать класс эквивалентности графа G по гомоморфизму через [G]. Класс эквивалентности может быть представлен единственным ядром в [G]. Отношение <math>\to</math> частично упорядочено на этих классах эквивалентности. Оно определяет частично упорядоченное множество Шаблон:Sfn.

Пусть G < H означает, что существует гомоморфизм из G в H, но нет гомоморфизма из H в G. Отношение <math>\to</math> является плотным порядком, это означает, что для всех (неориентированных) графов G, H таких, что G < H, существует граф K, такой, что G < K < H (это выполняется во всех случаях, за исключением тривиальных случаев <math>G=K_0</math> или <math>K_1</math>)Шаблон:Sfn Шаблон:Sfn Шаблон:Sfn. Например, между любыми двумя полными графами (за исключением <math>K_0, K_1</math>) есть бесконечно много цикловых полных графов, соответствующих рациональным числамШаблон:Sfn Шаблон:Sfn.

Частично упорядоченное множество классов эквивалентности графов по гомоморфизму является Шаблон:Не переведено 5, с Шаблон:Не переведено 5 [G] и [H], определённым как (класс эквивалентности) дизъюнктное объединение <math>[G \cup H]</math> и Шаблон:Не переведено 5 [G] и [H] определяется как тензорное произведение <math>[G \times H]</math> (выбор графов G и H в качестве представителей классов эквивалентности [G] и [H] не имеет значения)Шаблон:Sfn Шаблон:Sfn. Шаблон:Не переведено 5 элементы этой решётки — это в точности связные графы. Это можно показать, используя факт, что гомоморфизм отображает связный граф в связную компоненту целевого графаШаблон:Sfn Шаблон:Sfn. Неприводимые в пересечении элементы этой решётки — это в точности мультипликативные графы. Это графы K, такие, что произведение <math>G \times H</math> имеет гомоморфизм в K только тогда, когда один из графов G или H имеет такой гомоморфизм. Выявление мультипликативных графов является сердцевиной гипотезы Хедетниеми Шаблон:Sfn Шаблон:Sfn.

Гомоморфизмы графов образуют также категорию с графами в качестве объектов и гомоморфизмами в качестве стрелокШаблон:Sfn. Начальным объектом является пустой граф, в то время как терминальным объектом является граф с одной вершиной и одной петлёй в этой вершине. Тензорное произведение графов является произведением в теории категорий и экспоненциальный граф является экспоненциальным объектом для категорииШаблон:Sfn Шаблон:Sfn. Поскольку эти две операции всегда определены, категория графов является декартово замкнутой категорией. По тем же причинам решётка классов эквивалентности графов по гомоморфизмам, фактически, является Шаблон:Не переведено 5 Шаблон:Sfn Шаблон:Sfn.

Для ориентированных графов применимы те же определения. В частности, <math>\to</math> частично упорядочено на классах эквивалентности ориентированных графов. Этот порядок отличается от порядка <math>\to</math> на классах эквивалентности неориентированных графов, но содержит его в качестве подпорядка. Это потому, что любой неориентированный граф можно рассматривать как ориентированный, в котором любая дуга (u,v) появляется вместе с обратной дугой (v,u), а это не меняет определение гомоморфизма. Порядок <math>\to</math> для ориентированных графов снова является дистрибутивной решёткой и алгеброй Гейтинга с операциями объединения и пересечения, определённых как ранее. Однако этот порядок не плотный. Существует также категория с ориентированными графами в качестве объектов и гомоморфизмами в качестве стрелок, которая снова является декартово замкнутой категорией Шаблон:Sfn Шаблон:Sfn.

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

Файл:Groetzsch-graph.svg

Граф Грёча несравним с треугольником K₃

Имеется много несравнимых графов согласно предпорядку гомоморфизмов, то есть пары графов, таких, что нет гомоморфизмов из одного в другойШаблон:Sfn. Один из путей построения таковых графов — рассмотрение нечётного обхвата графа G, то есть длины его самого короткого цикла нечётной длины. Нечётный обхват, эквивалентно, является наименьшим нечётным числом g, для которого существует гомоморфизм из графа-цикла с g вершинами в G. По этой причине, если <math>G \to H</math>, то нечётный обхват графа G больше либо равен нечётного обхвата графа HШаблон:Sfn.

С другой стороны, если <math>G \to H</math>, то хроматическое число графа G меньше либо равно хроматическому числу графа H. Поэтому, если граф G имеет строго больший нечётный обхват, чем H и строго большее хроматическое число, чем H, то G и H несравнимыШаблон:Sfn Например, граф Грёча является 4-хроматичным (раскрашивается в 4 цвета) и свободным от треугольников (он имеет обхват 4 и нечётный обхват 5)Шаблон:R, так что он несовместим с треугольником K₃.

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

Среди ориентированных графов найти несравнимые пары много проще. Например, рассмотрим ориентированные графы-циклы <math>\vec{C}_n</math> с вершинами 1, 2, …, n и рёбрами из i в i + 1 (для i=1, 2, …, n − 1) и из n в 1. Существует гомоморфизм из <math>\vec{C}_n</math> в <math>\vec{C}_k (n, k \geqslant 3)</math> тогда и только тогда, когда n кратно k. В частности ориентированные графы-циклы <math>\vec{C}_n</math> с простыми n все несравнимыШаблон:Sfn.

Вычислительная сложность

В задаче о гомоморфизме графа экземпляр задачи состоит из пары графов (G,H), а решением является гомоморфизм из G в H. Общая задача разрешимости, спрашивающая, имеется ли решение этой задачи, NP-полна Шаблон:Sfn. Однако ограничения на графы дают ряд различных задач, некоторые из которых решить легче. Методы, которые используют ограничения на левый граф G, сильно отличаются от методов, использующихся на правый граф H, но в каждом случае дихотомия (строгие границы между простыми и сложными случаями) известна или предполагается.

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

Задача о гомоморфизме с фиксированным графом H с правой стороны каждого экземпляра называется задачей H-раскраски. Когда H является полным графом K_k, это задача k-раскраски графа, которая разрешима за полиномиальное время для k=0, 1, 2 и NP-полна в других случаяхШаблон:Sfn. В частности, возможность K₂-раскраски графа G эквивалентна двудольности графа G, что можно проверить за линейное время. Более обще, когда H является двудольным графом, возможность H-раскраски эквивалентна возможности K₂-раскраски (или K₀ / K₁ -раскрашиваемости, когда H пусто или не имеет рёбер), а следовательно, равным образом легко решаетсяШаблон:Sfn. Павол Хелл и Ярослав Нешетрил доказали, что для неориентированных графов никакой другой случай не является лёгким:

Теорема Хелла — Нешетрила (1990): Задача H-раскраски лежит в классе P, если H двудолен и NP-сложна в противном случаеШаблон:Sfn Шаблон:Sfn.

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

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

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

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

Задача о гомоморфизме с одним фиксированным графом G в левой стороне может быть решена полным перебором за время |V(H)|^O(|V(G)|), то есть полиномиально от размера входного графа HШаблон:Sfn. Другими словами, задача тривиальна в P для графов G ограниченного размера. Интересный вопрос тогда, какие другие свойства графа G, кроме размера, делают возможными полиномиальные алгоритмы.

Ключевым свойством оказывается древесная ширина, мера, насколько граф похож на дерево. Для графа G с древесной шириной, не превосходящей k, и графа H задача о гомоморфизме может быть решена за время|V(H)|^O(k) стандартными методами динамического программирования. Фактически, достаточно предположить, что ядро графа G имеет древесную ширину, не превосходящую k. Это верно даже в случае, когда ядро не известноШаблон:Sfn Шаблон:Sfn.

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

Теорема (Мартин Гроэ): Для вычислимого класса графов <math>\mathcal{G}</math>, задача о гомоморфизме для <math>(G,H)</math> с <math>G \in \mathcal{G}</math> принадлежит P тогда и только тогда, когда графы <math>\mathcal{G}</math> имеют ядра ограниченной древесной ширины (в допущении ETH) Шаблон:Sfn.

Можно задать вопрос, разрешима ли задача с произвольно высокой зависимостью от G, но с фиксированной полиномиальной зависимостью от размера графа H. Ответ положительный, если мы ограничим граф G классом с ядрами ограниченной древесной ширины, и отрицательный для всех других классовШаблон:Sfn. На языке Шаблон:Не переведено 5 сложности это утверждение формально гласит, что задача о гомоморфизме с графом <math>\mathcal{G}</math>, параметризованная по размеру (числу рёбер) графа G, показывает дихотомию. Она Шаблон:Не переведено 5, если графы в классе <math>\mathcal{G}</math> имеют ядра ограниченной древесной ширины, и Шаблон:Не переведено 5 в противном случае.

То же утверждение верно для более общих задач удовлетворения ограничений (или, другими словами, для реляционных структур). Требуется единственное предположение, что ограничения могут вовлекать лишь ограниченное количество переменных. Параметром тогда является древесная ширина Шаблон:Не переведено 5 Шаблон:Sfn.

См. также

Гипотеза Сидоренко

Примечания

Шаблон:Примечания

Литература

Шаблон:Refbegin

Шаблон:Refend

Книги общего характера

В универсальной алгебре и с учётом ограничений

В теории решёток и теории категорий

Шаблон:Статья
Шаблон:Статья (AMSI Vacation Research Scholarships, student research report supervised by Brian Davey and Jane Pitkethly, La Trobe University).

Шаблон:Rq

↑ Шаблон:Harvnb. Заметим, что реляционные структуры в статье называются реляционными системами.
↑ Напомним, обычно рёбра ориентированного графа называются дугами.

[HN-csp-1] Шаблон:Harvnb. Заметим, что реляционные структуры в статье называются реляционными системами.

[2] Напомним, обычно рёбра ориентированного графа называются дугами.

[1]

[2]

Партнерские ресурсы
Криптовалюты	Обмен криптовалют - www.bestchange.ru Криптовалютная биржа CoinEx Криптовалютная биржа Binance HIVE OS - операционная система для майнинга e4pool - Мультивалютный пул для майнинга.
Магазины	AliExpress — глобальная виртуальная (в Интернете) торговая площадка, предоставляющая возможность покупать товары производителей из КНР; computeruniverse.net - Интернет-магазин компьютеров(Промо код 5 Евро на первую покупку:FWWC3ZKQ);
Хостинг	DigitalOcean - американский провайдер облачных инфраструктур, с главным офисом в Нью-Йорке и с центрами обработки данных по всему миру;
Разное	Викиум - Онлайн-тренажер для мозга Like Центр - Центр поддержки и развития предпринимательства. Gamersbay - лучший магазин по бустингу для World of Warcraft. Ноотропы OmniMind N°1 - Усиливает мозговую активность. Повышает мотивацию. Улучшает память. Санкт-Петербургская школа телевидения - это федеральная сеть образовательных центров, которая имеет филиалы в 37 городах России. Lingualeo.com — интерактивный онлайн-сервис для изучения и практики английского языка в увлекательной игровой форме. Junyschool (Джунискул) – международная школа программирования и дизайна для детей и подростков от 5 до 17 лет, где ученики осваивают компьютерную грамотность, развивают алгоритмическое и креативное мышление, изучают основы программирования и компьютерной графики, создают собственные проекты: игры, сайты, программы, приложения, анимации, 3D-модели, монтируют видео. Умназия - Интерактивные онлайн-курсы и тренажеры для развития мышления детей 6-13 лет SkillBox - это один из лидеров российского рынка онлайн-образования. Среди партнеров Skillbox ведущий разработчик сервисного дизайна AIC, медиа-компания Yoola, первое и самое крупное русскоязычное аналитическое агентство Tagline, онлайн-школа дизайна и иллюстрации Bang! Bang! Education, оператор PR-рынка PACO, студия рисования Draw&Go, агентство performance-маркетинга Ingate, scrum-студия Sibirix, имидж-лаборатория Персона. «Нетология» — это университет по подготовке и дополнительному обучению специалистов в области интернет-маркетинга, управления проектами и продуктами, дизайна, Data Science и разработки. В рамках Нетологии студенты получают ценные теоретические знания от лучших экспертов Рунета, выполняют практические задания на отработку полученных навыков, общаются с экспертами и единомышленниками. Познакомиться со всеми продуктами подробнее можно на сайте https://netology.ru, линейка курсов и профессий постоянно обновляется. StudyBay Brazil – это онлайн биржа для португалоговорящих студентов и авторов! Студент получает уникальную работу любого уровня сложности и больше свободного времени, в то время как у автора появляется дополнительный заработок и бесценный опыт. Автор24 — самая большая в России площадка по написанию учебных работ: контрольные и курсовые работы, дипломы, рефераты, решение задач, отчеты по практике, а так же любой другой вид работы. Сервис сотрудничает с более 70 000 авторов. Более 1 000 000 работ уже выполнено. StudyBay – это онлайн биржа для англоязычных студентов и авторов! Студент получает уникальную работу любого уровня сложности и больше свободного времени, в то время как у автора появляется дополнительный заработок и бесценный опыт.