Гомоморфізм графів

Гомоморфізм зі снарку «квітка» $J_5$ у цикл $C_5$. Це також ретракція в центральні п'ять вершин. Тоді $J_5$, фактично, гомоморфно еквівалентний ядру $C_5$.

Гомоморфізм графів — це відображення між двома графами, що не порушує структури. Конкретніше, це відображення між наборами вершин двох графів, яке відображає суміжні вершини в суміжні.

Гомоморфізми узагальнюють різні поняття розфарбовування графів і дозволяють формулювати важливі класи задач виконання обмежень, таких як деякі задачі Шаблон:Не перекладено або задачі Шаблон:Не перекладеноШаблон:Sfn. Факт, що гомоморфізми можна використати послідовно, приводить до багатих алгебричних структур — передпорядку на графах, дистрибутивної ґратки і категорій (одна для неорієнтованих графів і одна для орієнтованих графів)Шаблон:Sfn. Обчислювальна складність пошуку гомоморфізму між заданими графами в загальному випадку позамежна, але відомо багато окремих випадків, коли задача здійсненна за поліноміальний час. Межі між розв'язними і нездоланними випадками є галуззю активних дослідженьШаблон:Sfn.

Визначення

У цій статті, якщо не сказано інше, під графами розуміють скінченні неорієнтовані графи з дозволеними петлями, але кратні ребра (паралельні) не дозволені. ГомоморфізмШаблон:SfnШаблон:SfnШаблон:Sfn $f$ з графу $G=(V(G),E(G))$ у граф $H=(V(H),E(H))$, що записується як

$f:G\to H$,

це функція з $V(G)$ у $V(H)$, яка відображає кінцеві точки кожного ребра з $G$ в кінцеві точки деякого ребра з $H$. Формально, з $\{u,v\}\in E(G)$ випливає $\{f(u),f(v)\}\in E(H)$, для всіх пар вершин $u$, $v$ з $V(G)$. Якщо існує деякий гомоморфізм з $G$ в $H$, то кажуть, що граф $G$ гомоморфний графу $H$, або що він $H$-розфарбовуваний. Це часто позначають як

$G\to H$.

Визначення, наведене вище, поширюється на орієнтовані графи. Тоді для гомоморфізму $f:G\to H,(f(u),f(v))$ є дугою (орієнтованим ребром) графу $H$, коли $(u,v)$ є дугою графу $G$.

Існує ін'єктивний гомоморфізм з $G$ в $H$ (тобто відображення, яке ніколи не відображає різні вершини в одну) тоді і тільки тоді, коли $G$ є підграфом графу $H$. Якщо гомоморфізм $f:G\to H$ є бієкцією (відповідністю один-до-одного між вершинами графу $G$ і графу $H$) обернена функція якого є також гомоморфізмом графу, тоді $f$ є ізоморфізмом графівШаблон:Sfn.

Накривні відображення є частим видом гомоморфізмів, який відбиває визначення і багато властивостей накриття в топологіїШаблон:Sfn. Вони визначаються як сюр'єктивні гомоморфізми, які локально бієктивні, тобто є бієкція в околі кожної вершини. Прикладом є подвійне покриття двочастковим графом, утворене з графу розбиттям кожної вершини $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\to H$ і $H\to G$Шаблон: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_3$ як підграф) гомеоморфно еквівалентний $K_3$. Це тому, з одного боку, що 3-розфарбування графу $G$, це те саме, що й гомоморфізм $G\to K_3$, як пояснено нижче. З іншого боку, будь-який підграф графу $G$ тривіально допускає гомоморфізм у $G$, звідки випливає, що $K_3\to G$. Це також означає, що $K_3$ є ядром будь-якого такого графу $G$.'Аналогічно, будь-який двочастковий граф, який має принаймні одне ребро, еквівалентний $K_2$Шаблон: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.

Якщо є два гомоморфізми $G\to H$ і $H\to K_k$, то їх суперпозиція $G\to K_k$ є також гомоморфізмомШаблон:Sfn. Іншими словами, якщо граф $H$ можна розфарбувати в $k$ кольорів і існує гомоморфізм $G$ в $H$, то $G$ можна також розфарбувати в $k$ кольорів. Тому з $G\to H$ випливає $\chi (G)⩽\chi (H)$, де $\chi$ означає хроматичне число графу (найменше число кольорів $k$, в які можна розфарбувати граф)Шаблон:Sfn.

Варіанти

Гомоморфізми загального вигляду можна розглядати також як вид розфарбування — якщо вершини фіксованого графу $H$ є допустимими кольорами, а ребра графу $H$ описують, які кольори сумісні, то $H$-розмальовка графу $G$ — це призначення кольорів вершин графу $G$ так, що суміжні вершини отримують сумісні кольори. Багато понять розфарбовування графів уміщуються в цю схему і можуть бути виражені як гомоморфізм графів у різні сімейства графів. Колові розфарбування можна визначити за допомогою гомоморфізмів у колові повні графи, уточнюючи звичайне поняття розфарбуванняШаблон:SfnШаблон:Sfn. Дробове і b-разове розфарбування можна визначити за допомогою гомоморфізмів у кнезерівські графи.Шаблон:SfnШаблон:Sfn T-розфарбування відповідають гомоморфізмам у деякі нескінченні графиШаблон:Sfn. Орієнтоване розфарбування орієнтованого графу є гомоморфізмом у будь-який орієнтований графШаблон:Sfn. Шаблон:Не перекладено — це локально ін'єктивний гомоморфізм у доповнення шляху, що означає, що він має бути ін'єктивним в околі кожної вершиниШаблон:R.

Орієнтації без довгих шляхів

Інший цікавий зв'язок стосується орієнтації графів. Орієнтація неорієнтованого графу $G$ — це будь-який орієнтований граф, отриманий вибором із двох можливих орієнтацій кожного ребра. Прикладом орієнтації повного графу $K_k$ є транзитивний турнір ${\overrightarrow{T}}_k$ з вершинами 1,2, …, $k$ і дугами з i в j, коли i < j. Гомоморфізм між орієнтаціями графів $G$ і $H$ дає гомоморфізм між неорієнтованими графами $G$ і $H$, якщо просто нехтувати орієнтації. З іншого боку, якщо дано гомоморфізм $G\to H$ між неорієнтованими графами, будь-яку орієнтацію $\overrightarrow{H}$ з $H$ можна відобразити в орієнтацію графу $\overrightarrow{G}$ з $G$, так що $\overrightarrow{G}$ має гомоморфізм у $\overrightarrow{H}$. Тому граф $G$ $k$-розфарбовуваний (має гомоморфізм у $K_k$) тоді і тільки тоді, коли деяка орієнтація $G$ має гомоморфізм у ${\overrightarrow{T}}_k$Шаблон:Sfn.

Фольклорна теорема свідчить, що для будь-яких $k$ орієнтований граф $G$ має гомоморфізм у ${\overrightarrow{T}}_k$ тоді і тільки тоді, коли він не допускає гомоморфізму з ${\overrightarrow{P}}_{k+1}$Шаблон:Sfn. Тут ${\overrightarrow{P}}_n$ — орієнтований шлях з вершинами 1, 2, …, $n$ і дугами з i в i + 1 для i = 1, 2, …, $n$ — 1. Таким чином, граф $k$-розфарбовуваний тоді і тільки тоді, коли він має орієнтацію, яка не допускає гомоморфізму з ${\overrightarrow{P}}_{k+1}$. Це твердження можна злегка посилити до твердження, що граф $k$-розфарбовуваний тоді і тільки тоді, коли деяка орієнтація не містить орієнтованого шляху довжини $k$ (немає ${\overrightarrow{P}}_{k+1}$ як підграфу). Це теорема Галлаї - Хассе - Роя - Вітавера.

Зв'язок з задачами задоволення обмежень

Приклади

Граф $H$ несусідніх днів тижня ізоморфний доповненню графу $C_7$ і в коловій кліці $K_7/2$

Деякі задачі розкладів можна промоделювати як питання про знаходження гомоморфізмів графуШаблон:SfnШаблон:Sfn. Як приклад, можна спробувати призначити практичні заняття так, щоб два курси, відвідувані тим самим студентом, не були в часі занадто близькими. Курси утворюють граф $G$, з ребрами між двома курсами, якщо їх відвідує один і той самий студент. Можливий час проведення курсів утворює граф $H$ з ребрами між двома часовими вікнами, якщо відстань за часом між ними досить велика. Наприклад, якщо потрібно мати циклічний щотижневий розклад, такий, що кожен студент приходить на практичні заняття через день, то граф $H$ має бути доповненням графу $C_7$. Гомоморфізм графу з $G$ в $H$ є тоді призначенням курсів за часовими вікнамиШаблон:Sfn. Щоб додати вимогу, скажімо, щоб жоден студент не мав заняття як у п'ятницю, так і в понеділок, досить видалити одне ребро з графу $H$.

Просту задачу Шаблон:Не перекладено можна поставити в такий спосіб. Є кілька передавачів бездротової мережі. Потрібно вибрати на кожному з них частотний канал, яким він буде передавати дані. Щоб уникнути завад, географічно близькі передавачі повинні мати канали з достатньо відмінними частотами. Якщо цю умову обмежено простим порогом для понять «географічно близькі» і «достатньо далекі», допустимий вибір каналів відповідає знову гомоморфізму графу. Тут графом $G$ буде набір передавачів з ребрами між ними, якщо вони географічно близькі, а графом $H$ буде набір каналів з ребрами між каналами, якщо частоти мало відрізняються. Хоча ця модель дуже спрощена, вона допускає деяку гнучкість — для пари передавачів, які не близькі, але можуть заважати один одному через географічні особливості, можна додати дугу в $G$. А дугу між передавачами, які не працюють одночасно, можна з графу видалити. Аналогічно, ребро між парою каналів, які далеко один від одного, але мають завади у вигляді гармонік можна видалити з графу $H$Шаблон:Sfn.

У кожному випадку ці спрощені моделі показують багато особливостей, які слід відпрацьовувати на практиціШаблон:Sfn. Задачі виконання обмежень, які узагальнюють задачі гомоморфізму графу, можуть встановлювати додаткові типи умов (такі як індивідуальні переваги або обмеження на число призначень, що збігаються). Це дозволяє зробити моделі реалістичнішими і практичнішими.

Формальна точка зору

Неорієнтовані й орієнтовані графи можна розглядати як часті випадки загальнішого поняття — Шаблон:Не перекладено (які визначаються як множина з кортежем відношень на ньому). Орієнтовані графи є структурами з одним бінарним відношенням (суміжність) на області (множині вершин)Шаблон:Sfn. З цієї точки зору Шаблон:Не перекладено таких структур є точно гомоморфізмами графів. У загальному випадку питання пошуку гомоморфізму з однієї структури в іншу є задачею виконання обмежень. Випадок графів дає конкретний перший крок, який допомагає зрозуміти складніші задачі виконання обмежень. Багато алгоритмічних методів пошуку гомоморфізмів графу, на зразок пошуку з вертанням, Шаблон:Не перекладено і Шаблон:Не перекладено застосовні до всіх задач виконання обмеженьШаблон:Sfn.

Для графів $G$ і $H$ питання, чи має граф $G$ гомоморфізм у граф $H$, відповідає окремому випадку задачі виконання обмежень з одним видом обмеженьШаблон:Sfn. У цій задачі змінними будуть вершини графу $G$, а областю значень кожної змінної буде набір вершин графу $H$. Розв'язком є функція, яка призначає кожній змінній елемент з області значень, так що функція f відображає $V(G)$ у $V(G)$. Кожне ребро або дуга $(u,v)$ графу $G$ тоді відповідає обмеженню $((u,v),E(H))$. Це обмеження означає, що розв'язок має відображати дугу $(u,v)$ в пару $(f(u),f(v))$, яка є відношенням $E(H)$, тобто, в дугу графу $H$. Розв'язком задачі є розв'язок, який задовольняє всім обмеженням, тобто це в точно гомоморфізм з $G$ в $H$.

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

Суперпозиції гомоморфізмів є гомоморфізмамиШаблон:Sfn. Зокрема, відношення $\to$ на графах транзитивне (і, тривіально, рефлексивне), так що це відношення є передпорядком на графахШаблон:Sfn. Будемо позначати клас еквівалентності графу $G$ за гомоморфізмом через $[G]$. Клас еквівалентності можожна подати єдиним ядром у $[G]$. Відношення $\to$ частково впорядковане на цих класах еквівалентності. Воно визначає частково впорядковану множинуШаблон:Sfn.

Нехай $G<H$ означає, що існує гомоморфізм з $G$ в $H$, але немає гомоморфізму з $H$ у $G$. Відношення $\to$ є щільним порядком, це означає, що для всіх (неорієнтованих) графів $G$, $H$ таких, що $G<H$, існує граф $K$, такий, що $G<H$ (це виконується у всіх випадках, за винятком тривіальних випадків $G=K_0$ або $K_1$)Шаблон:SfnШаблон:SfnШаблон:Sfn. Наприклад, між будь-якими двома повними графами (за винятком $K_0,K_1$) є нескінченно багато колових повних графів, відповідних раціональним числамШаблон:SfnШаблон:Sfn.

Частково впорядкована множина класів еквівалентності графів за гомоморфізмом є дистрибутивною ґраткою, з об'єднанням $[G]$ і $[H]$, визначеним як (клас еквівалентності) диз'юнктне об'єднання $[G\cup H]$, і перетином $[G]$ і $[H]$ визначеним як тензорний добуток $[G\times H]$ (вибір графів $G$ і $H$ як представників класів еквівалентності $[G]$ і $[H]$ не має значення)Шаблон:SfnШаблон:Sfn. Шаблон:Не перекладено елементи цієї ґратки — це точно зв'язні графи. Це можна показати, використовуючи факт, що гомоморфізм відображає зв'язний граф у зв'язну компоненту цільового графуШаблон:SfnШаблон:Sfn. Незвідні в перетині елементи цієї ґратки — це точно мультиплікативні графи. Це графи $K$, такі, що добуток $G\times H$ має гомоморфізм у $K$ тільки тоді, коли один із графів $G$ або $H$ має такий гомоморфізм. Виявлення мультиплікативних графів є серцевиною гіпотези ГедетнієміШаблон:SfnШаблон:Sfn.

Гомоморфізми графів утворюють також категорію з графами як об'єкти і гомоморфізмами як стрілкамиШаблон:Sfn. Початковим об'єктом є порожній граф, тоді як термінальним об'єктом є граф із однією вершиною і однією петлею в цій вершині. Тензорний добуток графів є добутком у теорії категорій і експоненційний граф є експоненційним об'єктом для категоріїШаблон:SfnШаблон:Sfn. Оскільки ці дві операції завжди визначені, категорія графів є декартово замкнутою категорією. З тієї ж причини ґратка класів еквівалентності графів за гомоморфізмами, фактично, є алгеброю ГейтингаШаблон:SfnШаблон:Sfn.

Для орієнтованих графів застосовуються ті самі визначення. Зокрема, $\to$ частково впорядковане на класах еквівалентності орієнтованих графів. Цей порядок відрізняється від порядку $\to$ на класах еквівалентності неорієнтованих графів, але містить його в як підпорядок. Це тому, що будь-який неорієнтований граф можна розглядати як орієнтований, в якому будь-яка дуга $(u,v)$ з'являється разом зі зворотною дугою $(v,u)$, а це не змінює визначення гомоморфізму. Порядок $\to$ для орієнтованих графів знову є дистрибутивною ґраткою і алгеброю Гейтинга з операціями об'єднання і перетину, визначених як раніше. Однак цей порядок не щільний. Існує також категорія з орієнтованими графами як об'єктами і гомоморфізмами як стрілками, яка також є декартово замкнутою категорієюШаблон:SfnШаблон:Sfn.

Непорівнянні графи

Граф Ґрьоча непорівнянний з трикутником $K_3$

Є багато непорівнянних графів за предпорядком гомоморфізмів, тобто пари графів, таких, що немає гомоморфізмів з одного в іншийШаблон:Sfn. Один зі шляхів побудови таких графів — розгляд непарного обхвату графу $G$, тобто довжини його найкоротшого циклу непарної довжини. Непарний обхват, еквівалентно, є найменшим непарним числом $g$, для якого існує гомоморфізм з графу-циклу з $g$ вершинами в $G$. З цієї причини, якщо $G\to H$, То непарний обхват графу $G$ більший або дорівнює непарному обхвату графу $H$Шаблон:Sfn.

З іншого боку, якщо $G\to H$, То хроматичне число графу $G$ менше або дорівнює хроматичному числу графу $H$. Тому, якщо граф $G$ має строго більший непарний обхват, ніж $H$ і строго більше хроматичне число, ніж $H$, то $G$ і $H$ непорівнянні.Шаблон:Sfn Наприклад, граф Ґрьоча є 4-хроматичним (розфарбовується в 4 кольори) і вільним від трикутників (він має обхват 4 і непарний обхват 5)Шаблон:R, так що він несумісний з трикутником $K_3$.

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

Серед орієнтованих графів знайти непорівнянні пари значно простіше. Наприклад, розглянемо орієнтовані графи-цикли ${\overrightarrow{C}}_n$ з вершинами 1, 2, …, $n$ і ребрами з i в i + 1 (для i = 1, 2, …, $n$ — 1) і з $n$ в 1. Існує гомоморфізм із ${\overrightarrow{C}}_n$ в ${\overrightarrow{C}}_k(n,k⩾3)$ тоді і тільки тоді, коли $n$ кратне $k$. Зокрема орієнтовані графи-цикли ${\overrightarrow{C}}_n$ з простими $n$ усі непорівнянніШаблон:Sfn.

Обчислювальна складність

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

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

Задача про гомоморфізм із фіксованим графом $H$ з правого боку кожного примірника називається задачею $H$-розфарбування. Коли $H$ є повним графом $K_k$, це задача $k$-розфарбовування графу, яка розв'язна за поліноміальний час для $k$ = 0, 1, 2 і NP-повна в інших випадкахШаблон:Sfn. Зокрема, можливість $K_2$-розфарбування графу $G$ еквівалентна двочастковості графу $G$, що можна перевірити за лінійний час. Загальніше, коли $H$ є двочастковим графом, можливість $H$-розфарбування еквівалентна можливості $K_2$-розфарбування (або $K_0$ / $K_1$-розфарбовуваності, коли $H$ порожнє або не має ребер), а отже, так само легко розв'язуєтьсяШаблон:Sfn. Павол Хелл і Ярослав Нешетріл довели, що для неорієнтованих графів ніякий інший випадок не є легким:

Теорема Гелла — Нешетріла (1990): Задача $H$-розфарбовування належить класу P, якщо $H$ двочастковий і NP-складна в іншому випадкуШаблон:SfnШаблон:Sfn.

Теорема відома також як теорема про дихотомію для гомоморфізму (неорієнтованого) графу, оскільки вона ділить задачі $H$-розфарбовування на NP-повні і задачі класу P без Шаблон:Не перекладено випадків. Для орієнтованих графів ситуація складніша і, фактично, еквівалентна загальнішому питанню опису Шаблон:Не перекладеноШаблон:Sfn. Виявляється, що задачі $H$-розфарбовування для орієнтованих графів настільки ж загальні і настільки ж різноманітні, як і задачі дотримання обмежень з будь-якими іншими видами обмеженьШаблон:SfnШаблон:Sfn. Формально, (скінченна) мова обмежень $\mathrm{\Gamma }$ є скінченною областю і скінченним набором відношень у цій області. $CSP(\mathrm{\Gamma })$ є задачею дотримання обмежень, де примірникам дозволяється використання тільки обмежень з $\mathrm{\Gamma }$.

Теорема (Федер, Варді 1998): Для будь-якої мови обмежень $\mathrm{\Gamma }$ задача $CSP(\mathrm{\Gamma })$ еквівалентна після поліноміального зведення деякій задачі $H$-розфарбовування для деякого орієнтованого графу $H$Шаблон:Sfn.

Інтуїтивно це означає, що будь-яка алгоритмічна техніка або результат про складність, застосовні до задач $H$-розфарбовування для орієнтованих графів $H$, застосовні також і для загальних задач дотримання обмежень. Зокрема, можна запитати, чи можна теорему Гелла — Нешетріла поширити на орієнтовані графи. За теоремою вище це еквівалентно гіпотезі Федера — Варді про дихотомію задач дотримання обмежень, яка стверджує, що для будь-якої мови обмежень $\mathrm{\Gamma }$ задача $CSP(\mathrm{\Gamma })$ або 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, але більш строгим. За тих самих припущень немає інших властивостей, які можна використати для отримання алгоритмів поліноміального часу. Це формалізує теорема:

Теорема (Мартін Грое): Для обчисле́нного класу графів $𝒢$, задача про гомоморфізм для $(G,H)$ з $G\in 𝒢$ належить P тоді і тільки тоді, коли графи $𝒢$ мають ядра обмеженої деревної ширини (в допущенні ETH)Шаблон:Sfn.

Можна поставити питання, чи розв'язна задача з довільно високою залежністю від $G$, але з фіксованою поліноміальною залежністю від розміру графу $H$. Відповідь позитивна, якщо ми обмежимо граф $G$ класом з ядрами обмеженої деревної ширини, і негативна для всіх інших класівШаблон:Sfn. Мовою Шаблон:Не перекладено складності це твердження формально свідчить, що задача про гомоморфізм з графом $𝒢$, параметризована за розміром (кількістю ребер) графу $G$, показує дихотомію. Вона Шаблон:Не перекладено, якщо графи в класі $𝒢$ мають ядра обмеженої деревної ширини, і Шаблон:Не перекладено в іншому випадку.

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

Див. також

• Шаблон:Нп

Література

• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття

• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Стаття
• Шаблон:Стаття

Книги загального характеру

• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Книга
• Шаблон:Книга

В універсальній алгебрі та з урахуванням обмежень

• Шаблон:Стаття
• Шаблон:Стаття

У теорії ґраток і теорії категорій

• Шаблон:Стаття
• Шаблон:Стаття (AMSI Vacation Research Scholarships Шаблон:Webarchive, студентський звіт про дослідження під керівництвом Brian Davey і Jane Pitkethly, Шаблон:Нп).