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

Не плутати з гомеоморфізмом графів.

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

Гомоморфізм зі снарку «квітка» ${\displaystyle J_{5}}$ у цикл ${\displaystyle C_{5}}$. Це також ретракція в центральні п'ять вершин. Тоді ${\displaystyle J_{5}}$, фактично, гомоморфно еквівалентний ядру ${\displaystyle C_{5}}$.

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

Визначення

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

${\displaystyle f:G\to H}$,

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

${\displaystyle G\to H}$.

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

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

є частим видом гомоморфізмів, який відбиває визначення і багато властивостей накриття в топології. Вони визначаються як сюр'єктивні гомоморфізми, які локально бієктивні, тобто є бієкція в околі кожної вершини. Прикладом є , утворене з графу розбиттям кожної вершини ${\displaystyle v}$ на ${\displaystyle v_{0}}$ і ${\displaystyle v_{1}}$ і заміною кожного ребра ${\displaystyle u}$, ${\displaystyle v}$ на два ребра ${\displaystyle u_{0},v_{1}}$ і ${\displaystyle v_{0},u_{1}}$. Функція, що відображає ${\displaystyle v_{0}}$ і ${\displaystyle v_{1}}$ у ${\displaystyle v}$ початкового графу, є гомоморфізмом і накривним відображенням.

Гомеоморфізм графу є окремим поняттям, не пов'язаним прямо з гомоморфізми. Грубо кажучи, він вимагає ін'єктивності, але дозволяє відображення ребер у шляхи (а не просто в ребра). Мінори графу залишаються слабшим поняттям.

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

${\displaystyle K_{7}}$, повний граф з 7 вершинами, є ядром.

Два графи ${\displaystyle G}$ і ${\displaystyle H}$ гомоморфно еквівалентні, якщо ${\displaystyle G\to H}$ і ${\displaystyle H\to G}$.

Ретракція — це гомоморфізм r з графу ${\displaystyle G}$ в підграф ${\displaystyle H}$ графу ${\displaystyle G}$, такий, що ${\displaystyle r(v)=v}$ для кожної вершини ${\displaystyle v}$ з ${\displaystyle H}$. У цьому випадку підграф ${\displaystyle H}$ називається ретрактом графу ${\displaystyle G}$.

Ядро — це граф, який не має гомоморфізму в будь-який власний підграф. Еквівалентно, ядро можна визначити як граф, який не є ретрактом для будь-якого власного підграфу. Будь-який граф ${\displaystyle G}$ гомоморфно еквівалентний єдиному ядру (з точністю до ізоморфізму), яке називають ядром графу ${\displaystyle G}$. Зауважимо, що це не так для нескінченних графів загального вигляду. Однак ті ж визначення застосовні і до орієнтованих графів і орієнтований граф також еквівалентний єдиному ядру. Будь-який неорієнтований і орієнтований граф містить своє ядро і як ретракт, і як породжений підграф.

Наприклад, усі повні графи ${\displaystyle K_{n}}$ і всі непарні цикли (циклічні графи непарної довжини) є ядрами. Будь-який 3-розфарбовуваний граф ${\displaystyle G}$, що містить трикутник (тобто має повний граф ${\displaystyle K_{3}}$ як підграф) гомеоморфно еквівалентний ${\displaystyle K_{3}}$. Це тому, з одного боку, що 3-розфарбування графу ${\displaystyle G}$, це те саме, що й гомоморфізм ${\displaystyle G\to K_{3}}$, як пояснено нижче. З іншого боку, будь-який підграф графу ${\displaystyle G}$ тривіально допускає гомоморфізм у ${\displaystyle G}$, звідки випливає, що ${\displaystyle K_{3}\to G}$. Це також означає, що ${\displaystyle K_{3}}$ є ядром будь-якого такого графу ${\displaystyle G}$.'Аналогічно, будь-який двочастковий граф, який має принаймні одне ребро, еквівалентний ${\displaystyle K_{2}}$.

Зв'язок з розфарбуваннями

${\displaystyle k}$-розфарбування для деякого цілого ${\displaystyle k}$ — це призначення одного з ${\displaystyle k}$ кольорів кожній вершині графу ${\displaystyle G}$ так, що кінцеві вершини кожного ребра мають різні кольори. ${\displaystyle k}$-розфарбування графу ${\displaystyle G}$ відповідають точно гомоморфізмам з ${\displaystyle G}$ в повний граф ${\displaystyle K_{k}}$. Більш того, вершини графу ${\displaystyle K_{k}}$ відповідають ${\displaystyle k}$ кольорам і два кольори суміжні як вершини графу ${\displaystyle K_{k}}$ тоді і тільки тоді, коли вони різні. Отже, функція визначає гомоморфізм у ${\displaystyle K_{k}}$ тоді і тільки тоді, коли суміжні вершини графу ${\displaystyle G}$ пофарбовано в різні кольори. Зокрема, граф ${\displaystyle G}$ ${\displaystyle k}$-розфарбовуваний тоді і тільки тоді, коли ${\displaystyle K_{k}}$-розфарбовуваний.

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

Варіанти

Гомоморфізми загального вигляду можна розглядати також як вид розфарбування — якщо вершини фіксованого графу ${\displaystyle H}$ є допустимими кольорами, а ребра графу ${\displaystyle H}$ описують, які кольори сумісні, то ${\displaystyle H}$-розмальовка графу ${\displaystyle G}$ — це призначення кольорів вершин графу ${\displaystyle G}$ так, що суміжні вершини отримують сумісні кольори. Багато понять розфарбовування графів уміщуються в цю схему і можуть бути виражені як гомоморфізм графів у різні сімейства графів. Колові розфарбування можна визначити за допомогою гомоморфізмів у (колові повні графи), уточнюючи звичайне поняття розфарбування. Дробове і b-разове розфарбування можна визначити за допомогою гомоморфізмів у кнезерівські графи. T-розфарбування відповідають гомоморфізмам у деякі нескінченні графи. орієнтованого графу є гомоморфізмом у будь-який орієнтований граф. ^[en] — це локально ін'єктивний гомоморфізм у доповнення шляху, що означає, що він має бути ін'єктивним в околі кожної вершини.

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

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

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

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

Приклади

Граф ${\displaystyle H}$ несусідніх днів тижня ізоморфний доповненню графу ${\displaystyle C_{7}}$ і в (коловій кліці) ${\displaystyle K_{7}/2}$

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

Просту задачу ^[en] можна поставити в такий спосіб. Є кілька передавачів бездротової мережі. Потрібно вибрати на кожному з них частотний канал, яким він буде передавати дані. Щоб уникнути завад, географічно близькі передавачі повинні мати канали з достатньо відмінними частотами. Якщо цю умову обмежено простим порогом для понять «географічно близькі» і «достатньо далекі», допустимий вибір каналів відповідає знову гомоморфізму графу. Тут графом ${\displaystyle G}$ буде набір передавачів з ребрами між ними, якщо вони географічно близькі, а графом ${\displaystyle H}$ буде набір каналів з ребрами між каналами, якщо частоти мало відрізняються. Хоча ця модель дуже спрощена, вона допускає деяку гнучкість — для пари передавачів, які не близькі, але можуть заважати один одному через географічні особливості, можна додати дугу в ${\displaystyle G}$. А дугу між передавачами, які не працюють одночасно, можна з графу видалити. Аналогічно, ребро між парою каналів, які далеко один від одного, але мають завади у вигляді гармонік можна видалити з графу ${\displaystyle H}$.

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

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

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

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

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

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

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

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

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

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

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

Граф Ґрьоча непорівнянний з трикутником ${\displaystyle K_{3}}$

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

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

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

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

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

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

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

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

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

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

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

Інтуїтивно це означає, що будь-яка алгоритмічна техніка або результат про складність, застосовні до задач ${\displaystyle H}$-розфарбовування для орієнтованих графів ${\displaystyle H}$, застосовні також і для загальних задач дотримання обмежень. Зокрема, можна запитати, чи можна теорему Гелла — Нешетріла поширити на орієнтовані графи. За теоремою вище це еквівалентно гіпотезі Федера — Варді про дихотомію задач дотримання обмежень, яка стверджує, що для будь-якої мови обмежень ${\displaystyle \Gamma }$ задача ${\displaystyle CSP(\Gamma )}$ або NP-повна, або належить до класу P.

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

Задачу про гомоморфізм з одним фіксованим графом ${\displaystyle G}$ ліворуч можна розв'язати повним перебором за час |V(${\displaystyle H}$)|^{O(|V(${\displaystyle G}$)|)}, тобто поліноміально від розміру вхідного графу ${\displaystyle H}$. Іншими словами, задача тривіальна в P для графів ${\displaystyle G}$ обмеженого розміру. Цікаве питання по те, які інші властивості графу ${\displaystyle G}$, крім розміру, уможливлюють поліноміальні алгоритми.

Ключовою властивістю виявляється деревна ширина, міра, наскільки граф схожий на дерево. Для графу ${\displaystyle G}$ з деревною шириною, що не перевищує ${\displaystyle k}$, і графу ${\displaystyle H}$ задачу про гомоморфізм можна розв'язати за час |V(${\displaystyle H}$)|^{O(${\displaystyle k}$)} стандартними методами динамічного програмування. Фактично, досить припустити, що ядро графу ${\displaystyle G}$ має деревну ширину, яка не перевищує k. Це так навіть у разі, коли ядро не відоме.

Показник в алгоритмі з часом роботи |V(${\displaystyle H}$)|^{O(${\displaystyle k}$)} не можна знизити істотно — не існує алгоритму, який працює за час |V(${\displaystyle H}$)|^{o(tw(${\displaystyle G}$)/log tw(${\displaystyle G}$))} при істинності (англ. exponential time hypothesis, ETH), навіть якщо вхід обмежено будь-яким класом графів необмеженої деревної ширини. ETH є недоведеним припущенням, аналогічним припущенню P ≠ NP, але більш строгим. За тих самих припущень немає інших властивостей, які можна використати для отримання алгоритмів поліноміального часу. Це формалізує теорема:

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

Можна поставити питання, чи розв'язна задача з довільно високою залежністю від ${\displaystyle G}$, але з фіксованою поліноміальною залежністю від розміру графу ${\displaystyle H}$. Відповідь позитивна, якщо ми обмежимо граф ${\displaystyle G}$ класом з ядрами обмеженої деревної ширини, і негативна для всіх інших класів. Мовою ^[en] складності це твердження формально свідчить, що задача про гомоморфізм з графом ${\displaystyle {\mathcal {G}}}$, параметризована за розміром (кількістю ребер) графу ${\displaystyle G}$, показує дихотомію. Вона ^[en], якщо графи в класі ${\displaystyle {\mathcal {G}}}$ мають ядра обмеженої деревної ширини, і ^[en] в іншому випадку.

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

Див. також

• ^[ru]

Примітки

1. Hell, Nešetřil, 2004, с. 27.
2. Hell, Nešetřil, 2004, с. 109.
3. Hell, Nešetřil, 2008.
4. Cameron, 2006.
5. Geňa, Tardif, 1997.
6. Hell, Nešetřil, 2004.
7. Geňa, Tardif, 1997, с. Observation 2.3.
8. Godsil, Royle, 2001, с. 115.
9. Hell, Nešetřil, 2004, с. 19.
10. Hell, Nešetřil, 2004, с. Proposition 1.31.
11. Cameron, 2006, с. Proposition 2.3.
12. Hell, Nešetřil, 2004, с. Corollary 1.32.
13. Hell, Nešetřil, 2004, с. 34.
14. Cameron, 2006, с. 4 (Proposition 2.5).
15. Cameron, 2006, с. 1.
16. Hell, Nešetřil, 2004, с. Proposition 1.7.
17. Hell, Nešetřil, 2004, с. §1.7.
18. Hell, Nešetřil, 2004 та с. Corollary 1.8.
19. Hell, Nešetřil, 2004, с. §6.1.
20. Geňa, Tardif, 1997, с. §4.4.
21. Hell, Nešetřil, 2004, с. §6.2.
22. Geňa, Tardif, 1997, с. §4.5.
23. Hell, Nešetřil, 2004, с. §6.3.
24. Hell, Nešetřil, 2004, с. §6.4.
25. *Fiala J., Kratochvíl J. Partial covers of graphs // Discussiones Mathematicae Graph Theory. — 2002. — Т. 22, вип. 1. — С. 89–99. — DOI:10.7151/dmgt.1159.
26. Hell, Nešetřil, 2004, с. 13–14.
27. Hell, Nešetřil, 2004, с. Proposition 1.20.
28. Hell, Nešetřil, 2004, с. §1.8.
29. Hell, Nešetřil, 2004, с. 30–31.
30. Hell, Nešetřil, 2004, с. 31–32.
31. Hell та Nešetřil, 2004. Зауважимо, що реляційні структури в статті називають реляційними системами.
32. Нагадаємо, зазвичай ребра орієнтованого графу називають дугами.
33. Hell, Nešetřil, 2004, с. §3.1.
34. Hell, Nešetřil, 2004, с. Theorem 3.1.
35. Hell, Nešetřil, 2004, с. Theorem 3.30.
36. Geňa, Tardif, 1997, с. Theorem 2.33.
37. Welzl, 1982, с. 29–41.
38. Hell, Nešetřil, 2004, с. 192.
39. Geňa, Tardif, 1997, с. 127.
40. Hell, Nešetřil, 2004, с. Proposition 3.2, distributivity is stated in Proposition 2.4.
41. Geňa, Tardif, 1997, с. Theorem 2.37.
42. Kwuida, Lehtonen, 2011, с. 251–265.
43. Gray, 2014.
44. Tardif, 2008, с. 46–57.
45. Dwight, Sauer, 1996, с. 125–139.
46. Hell, Nešetřil, 2004, с. 125.
47. Brown, Morris, Shrimpton, Wensley, 2008.
48. Hell, Nešetřil, 2004, с. 7.
49. Geňa, Tardif, 1997, с. Observation 2.6.
50. Weisstein, Eric W. Grötzsch Graph(англ.) на сайті Wolfram MathWorld.
51. Geňa, Tardif, 1997, с. Proposition 3.14.
52. Gyárfás, Jensen, Stiebitz, 2004, с. 1–14.
53. Hell, Nešetřil, 2004, с. Proposition 3.4.
54. Hell, Nešetřil, 2004, с. 96.
55. Hell, Nešetřil, 2004, с. 35.
56. Bodirsky, 2007, с. §1.3.
57. Hell, Nešetřil, 2004, с. §5.1.
58. Hell, Nešetřil, 2004, с. Proposition 5.1.
59. Hell, Nešetřil, 2004, с. §5.2.
60. Hell, Nešetřil, 1990, с. 92–110.
61. Hell, Nešetřil, 2004, с. §5.3.
62. Hell, Nešetřil, 2004, с. Theorem 5.14.
63. Feder, Vardi, 1998, с. 57–104.
64. Cygan, Fomin, Golovnev и др., 2016, с. 1643–1649.
65. Dalmau, Kolaitis, Vardi, 2002, с. 310–326.
66. Grohe, 2007.
67. Marx, 2010, с. 85–112.

Література

• Welzl E. Color-families are dense // Theoret. Comput. Sci.. — 1982. — Т. 17 (17 червня). — С. 29–41. — DOI:10.1016/0304-3975(82)90129-3.
• Pavol Hell, Jaroslav Nešetřil. On the complexity of H-coloring // . — 1990. — Т. 48, вип. 1 (17 червня). — С. 92–110. — DOI:10.1016/0095-8956(90)90132-J.
• Gyárfás A., Jensen T., Stiebitz M. On Graphs With Strongly Independent Color-Classes // . — 2004. — Т. 46, вип. 1 (17 червня). — С. 1–14. — DOI:10.1002/jgt.10165.

• Léonard Kwuida, Erkko Lehtonen. On the Homomorphism Order of Labeled Posets // . — Springer, 2011. — Т. 28, вип. 2 (17 червня). — С. 251–265. — arXiv:0911.0200. — DOI:10.1007/s11083-010-9169-x.
• Tardif C. Hedetniemi's conjecture, 40 years later // Graph Theory Notes of New York. — 2008. — Т. 54 (17 червня). — С. 46–57. з джерела 12 липня 2021. Процитовано 30 червня 2021.
• Dwight D., Sauer N. Lattices arising in categorial investigations of Hedetniemi's conjecture // . — 1996. — Т. 152, вип. 1—3 (17 червня). — С. 125–139. — DOI:10.1016/0012-365X(94)00298-W.
• Dániel Marx. Can You Beat Treewidth? // . — 2010. — Т. 6 (17 червня). — С. 85–112. — DOI:10.4086/toc.2010.v006a005.
• Cygan M., Fomin F. V., Golovnev A., Kulikov A. S., Mihajlin I., Pachocki J., Socała A. Tight bounds for graph homomorphism and subgraph isomorphism. — SIAM, 2016. — . — Bibcode:2015arXiv150703738F.
• Víctor Dalmau, Phokion G. Kolaitis, Moshe Y. Vardi. Constraint Satisfaction, Bounded Treewidth, and Finite-Variable Logics. — 2002. — С. 310–326. — DOI:10.1007/3-540-46135-3_21.
• Martin Grohe. The complexity of homomorphism and constraint satisfaction problems seen from the other side // . — 2007. — Т. 54, вип. 1 (17 червня). — DOI:10.1145/1206035.1206036.
• Tomás Feder, Moshe Y. Vardi. The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory // . — 1998. — Т. 28, вип. 1 (17 червня). — С. 57–104. — DOI:10.1137/S0097539794266766. з джерела 6 лютого 2022. Процитовано 30 червня 2021.

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

• Peter Cameron. Graph Homomorphisms, Combinatorics Study Group Notes. — 2006. — 17 червня. з джерела 7 травня 2021. Процитовано 30 червня 2021.
• Pavol Hell, Jaroslav Nešetřil. Graphs and Homomorphisms. — Oxford University Press, 2004. — Т. 28 (17 червня). — . з джерела 6 травня 2021. Процитовано 30 червня 2021.
• Geňa H., Tardif C. Graph homomorphisms: structure and symmetry // [1] — Springer, 1997. — С. 107–166. — DOI:10.1007/978-94-015-8937-6_4. з джерела 11 липня 2021
• Chris Godsil, Gordon Royle. 6. Homomorphisms // Algebraic Graph Theory. — Springer–Verlag New York, 2001. — Т. 207. — (Graduate Texts in Mathematics) — . — DOI:10.1007/978-1-4613-0163-9.

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

• Bodirsky M. Graph Homomorphisms and Universal Algebra, Course Notes. — 2007. — 17 червня. з джерела 1 грудня 2020. Процитовано 30 червня 2021.
• Pavol Hell, Jaroslav Nešetřil. Colouring, constraint satisfaction, and complexity // Computer Science Review. — 2008. — Т. 2, вип. 2 (17 червня). — С. 143–163. — DOI:10.1016/j.cosrev.2008.10.003. з джерела 6 липня 2017. Процитовано 30 червня 2021.

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

• Brown R., Morris I., Shrimpton J., Wensley C. D. Graphs of morphisms of graphs // . — 2008. — Т. 15, вип. 1 (17 червня). — С. A1. з джерела 11 липня 2021. Процитовано 30 червня 2021.
• Gray C. T. The Digraph Lattice. — 2014. — 17 червня. з джерела 20 січня 2022. Процитовано 30 червня 2021. ( Vacation Research Scholarships [ 14 серпня 2018 у Wayback Machine.], студентський звіт про дослідження під керівництвом Brian Davey і Jane Pitkethly, ^[en]).