Перегляд вихідного коду сторінки Гомоморфізм графів

{{не плутати|Гомеоморфізм графів|гомеоморфізмом графів}}
[[Файл:Graph_homomorphism_into_C5.svg|міні| Гомоморфізм зі [[Снарк «Квітка»|снарку «квітка»]] <math>J_5</math> у цикл <math>C_5</math>. Це також ретракція в центральні п'ять вершин. Тоді <math>J_5</math>, фактично, гомоморфно еквівалентний [[Ядро (теорія графів)|ядру]] <math>C_5</math>.]]
'''Гомоморфізм графів'''&nbsp;— це відображення між двома [[Граф (математика)|графами]], що не порушує структури. Конкретніше, це відображення між наборами вершин двох графів, яке відображає суміжні [[Вершина (теорія графів)|вершини]] в суміжні.

Гомоморфізми узагальнюють різні поняття [[розфарбовування графів]] і дозволяють формулювати важливі класи [[Задача виконання обмежень|задач виконання обмежень]], таких як деякі задачі {{Не перекладено|Розклад (технологічні процеси)|складання розкладів|en|Scheduling (production processes)}} або задачі {{Не перекладено|Розподіл радіочастот|розподілу радіочастот|en|frequency assignment}}{{Sfn|Hell, Nešetřil|2004|с=27}}. Факт, що гомоморфізми можна використати послідовно, приводить до багатих алгебричних структур&nbsp;— [[Передпорядок|передпорядку]] на графах, [[Дистрибутивна ґратка|дистрибутивної ґратки]] і [[Теорія категорій|категорій]] (одна для неорієнтованих графів і одна для орієнтованих графів){{Sfn|Hell, Nešetřil|2004|с=109}}. [[Обчислювальна складність]] пошуку гомоморфізму між заданими графами в загальному випадку позамежна, але відомо багато окремих випадків, коли задача здійсненна за [[Часова складність|поліноміальний час]]. Межі між розв'язними і нездоланними випадками є галуззю активних досліджень{{Sfn|Hell, Nešetřil|2008}}.

== Визначення ==
У цій статті, якщо не сказано інше, під ''графами'' розуміють скінченні [[Граф (математика)|неорієнтовані графи]] з дозволеними [[Петля (теорія графів)|петлями]], але [[кратні ребра]] (паралельні) не дозволені. '''Гомоморфізм'''{{Sfn|Cameron|2006}}{{Sfn|Geňa, Tardif|1997}}{{Sfn|Hell, Nešetřil|2004}} <math>f</math>&nbsp;з графу <math>G=(V(G), E(G))</math> у граф <math>H=(V(H), E(H))</math>, що записується як

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

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

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

Визначення, наведене вище, поширюється на орієнтовані графи. Тоді для гомоморфізму <math>f : G \to H, (f(u),f(v))</math> є [[Орієнтований граф|дугою]] (орієнтованим ребром) графу <math>H</math>, коли <math>(u,v)</math> є дугою графу <math>G</math>.''

Існує [[Ін'єкція (математика)|ін'єктивний]] гомоморфізм з <math>G</math> в <math>H</math> (тобто відображення, яке ніколи не відображає різні вершини в одну) [[Тоді й лише тоді|тоді і тільки тоді]], коли <math>G</math> є [[Словник термінів теорії графів|підграфом]] графу <math>H</math>.'' Якщо гомоморфізм <math>f : G \to H</math> є [[Бієкція|бієкцією]] (відповідністю один-до-одного між вершинами графу <math>G</math> і графу <math>H</math>) [[обернена функція]] якого є також гомоморфізмом графу, тоді <math>f</math> є [[Ізоморфізм графів|ізоморфізмом графів]]{{Sfn|Geňa, Tardif|1997|с=Observation 2.3}}.

[[Накривний граф|Накривні відображення]] є частим видом гомоморфізмів, який відбиває визначення і багато властивостей [[Накриття (топологія)|накриття в топології]]{{Sfn|Godsil, Royle|2001|с=115}}. Вони визначаються як [[Сюр'єкція|сюр'єктивні]] гомоморфізми, які локально бієктивні, тобто є бієкція в [[Окіл (теорія графів)|околі]] кожної вершини. Прикладом є [[подвійне покриття двочастковим графом]], утворене з графу розбиттям кожної вершини <math>v</math> на <math>v_0</math> і <math>v_1</math> і заміною кожного ребра <math>u</math>, <math>v</math> на два ребра <math>u_0,v_1</math> і <math>v_0,u_1</math>. Функція, що відображає <math>v_0</math> і <math>v_1</math> у <math>v</math> початкового графу, є гомоморфізмом і накривним відображенням.

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

=== Ядра і ретракти ===
[[Файл:Complete_graph_K7.svg|праворуч|міні| <math>K_7</math>, повний граф з 7 вершинами, є ядром.]]
Два графи <math>G</math> і <math>H</math> '''гомоморфно еквівалентні''', якщо <math>G \to H</math> і <math>H \to G</math>{{Sfn|Cameron|2006}}{{Sfn|Geňa, Tardif|1997}}{{Sfn|Hell, Nešetřil|2004}}.

Ретракція&nbsp;— це гомоморфізм ''r'' з графу <math>G</math> в [[Словник термінів теорії графів|підграф]] <math>H</math> графу <math>G</math>, такий, що <math>r(v)=v</math> для кожної вершини <math>v</math> з <math>H</math>. У цьому випадку підграф <math>H</math> називається '''ретрактом''' графу <math>G</math>{{Sfn|Hell, Nešetřil|2004|с=19}}.

'''Ядро'''&nbsp;— це граф, який не має гомоморфізму в будь-який власний підграф. Еквівалентно, ядро можна визначити як граф, який не є ретрактом для будь-якого власного підграфу{{Sfn|Hell, Nešetřil|2004|с=Proposition 1.31}}. Будь-який граф <math>G</math> гомоморфно еквівалентний єдиному ядру (з точністю до ізоморфізму), яке називають ''ядром'' графу <math>G</math>{{Sfn|Cameron|2006|с=Proposition 2.3}}{{Sfn|Hell, Nešetřil|2004|с=Corollary 1.32}}. Зауважимо, що це не так для нескінченних графів загального вигляду{{Sfn|Hell, Nešetřil|2004|с=34}}. Однак ті ж визначення застосовні і до орієнтованих графів і орієнтований граф також еквівалентний єдиному ядру. Будь-який неорієнтований і орієнтований граф містить своє ядро і як ретракт, і як [[породжений підграф]]{{Sfn|Hell, Nešetřil|2004|с=19}}.

Наприклад, усі [[Повний граф|повні графи]] <math>K_n</math> і всі непарні цикли ([[Циклічний граф|циклічні графи]] непарної довжини) є ядрами. Будь-який [[Розфарбовування графів|3-розфарбовуваний]] граф <math>G</math>, що містить трикутник (тобто має [[повний граф]] <math>K_3</math> як підграф) гомеоморфно еквівалентний <math>K_3</math>. Це тому, з одного боку, що 3-розфарбування графу <math>G</math>, це те саме, що й гомоморфізм <math>G \to K_3</math>, як пояснено нижче. З іншого боку, будь-який підграф графу <math>G</math> тривіально допускає гомоморфізм у <math>G</math>, звідки випливає, що <math>K_3 \to G</math>. Це також означає, що <math>K_3</math> є ядром будь-якого такого графу <math>G</math>.'Аналогічно, будь-який [[двочастковий граф]], який має принаймні одне ребро, еквівалентний <math>K_2</math>{{Sfn|Cameron|2006|с=4 (Proposition 2.5)}}.

== Зв'язок з розфарбуваннями ==
[[Розфарбовування графів|<math>k</math>-розфарбування]] для деякого цілого <math>k</math>&nbsp;— це призначення одного з <math>k</math> кольорів кожній вершині графу <math>G</math> так, що кінцеві вершини кожного ребра мають різні кольори. <math>k</math>-розфарбування графу <math>G</math> відповідають точно гомоморфізмам з <math>G</math> в [[повний граф]] <math>K_k</math>{{Sfn|Cameron|2006|с=1}}{{Sfn|Hell, Nešetřil|2004|с=Proposition 1.7}}. Більш того, вершини графу <math>K_k</math> відповідають <math>k</math> кольорам і два кольори суміжні як вершини графу <math>K_k</math> тоді і тільки тоді, коли вони різні. Отже, функція визначає гомоморфізм у <math>K_k</math> тоді і тільки тоді, коли суміжні вершини графу <math>G</math> пофарбовано в різні кольори. Зокрема, граф <math>G</math> <math>k</math>-розфарбовуваний тоді і тільки тоді, коли <math>K_k</math>-розфарбовуваний{{Sfn|Cameron|2006|с=1}}{{Sfn|Hell, Nešetřil|2004|с=Proposition 1.7}}.

Якщо є два гомоморфізми <math>G \to H</math> і <math>H \to K_k</math>, то їх суперпозиція <math>G \to K_k</math> є також гомоморфізмом{{Sfn|Hell, Nešetřil|2004|с=§1.7}}. Іншими словами, якщо граф <math>H</math> можна розфарбувати в <math>k</math> кольорів і існує гомоморфізм <math>G</math> в <math>H</math>, то <math>G</math> можна також розфарбувати в <math>k</math> кольорів. Тому з <math>G \to H</math> випливає <math>\chi(G) \leqslant \chi(H)</math>, де <math>\chi</math> означає [[хроматичне число]] графу (найменше число кольорів <math>k</math>, в які можна розфарбувати граф){{Sfn|Hell, Nešetřil|2004|с. Corollary 1.8}}.

=== Варіанти ===
Гомоморфізми загального вигляду можна розглядати також як вид розфарбування&nbsp;— якщо вершини фіксованого графу <math>H</math> є допустимими ''кольорами'', а ребра графу <math>H</math> описують, які кольори ''сумісні'', то <math>H</math>-розмальовка графу <math>G</math>&nbsp;— це призначення кольорів вершин графу <math>G</math> так, що суміжні вершини отримують сумісні кольори. Багато понять розфарбовування графів уміщуються в цю схему і можуть бути виражені як гомоморфізм графів у різні сімейства графів. [[Колове розфарбовування|Колові розфарбування]] можна визначити за допомогою гомоморфізмів у [[Колове розфарбовування#Колові повні графи|колові повні графи]], уточнюючи звичайне поняття розфарбування{{Sfn|Hell, Nešetřil|2004|с=§6.1}}{{Sfn|Geňa, Tardif|1997|с=§4.4}}. [[Дробове розфарбування|Дробове]] і [[Дробове розфарбування|''b-разове'' розфарбування]] можна визначити за допомогою гомоморфізмів у [[Кнезерів граф|кнезерівські графи]].{{Sfn|Hell, Nešetřil|2004|с=§6.2}}{{Sfn|Geňa, Tardif|1997|с=§4.5}} [[Т-розфарбування|T-розфарбування]] відповідають гомоморфізмам у деякі нескінченні графи{{Sfn|Hell, Nešetřil|2004|с=§6.3}}. [[Орієнтоване розфарбування графу|Орієнтоване розфарбування]] орієнтованого графу є гомоморфізмом у будь-який [[орієнтований граф]]{{Sfn|Hell, Nešetřil|2004|с=§6.4}}. {{Не перекладено|L(2,1)-розфарбування||en|L(2,1)-coloring}}&nbsp;— це локально ін'єктивний гомоморфізм у [[Доповнення графу|доповнення]] [[Шлях (граф)|шляху]], що означає, що він має бути ін'єктивним в околі кожної вершини{{R|Fiala02}}.

=== Орієнтації без довгих шляхів ===
Інший цікавий зв'язок стосується [[Орієнтація (теорія графів)|орієнтації графів]]. Орієнтація неорієнтованого графу <math>G</math>&nbsp;— це будь-який орієнтований граф, отриманий вибором із двох можливих орієнтацій кожного ребра. Прикладом орієнтації повного графу <math>K_k</math> є [[Турнір (теорія графів)|транзитивний турнір]] <math>\vec{T}_k</math> з вершинами 1,2, …, <math>k</math> і дугами з ''i'' в ''j'', коли ''i'' < ''j''. Гомоморфізм між орієнтаціями графів <math>G</math> і <math>H</math> дає гомоморфізм між неорієнтованими графами <math>G</math> і <math>H</math>, якщо просто нехтувати орієнтації. З іншого боку, якщо дано гомоморфізм <math>G \to H</math> між неорієнтованими графами, будь-яку орієнтацію <math>\vec{H}</math> з <math>H</math> можна відобразити в орієнтацію графу <math>\vec{G}</math> з <math>G</math>, так що <math>\vec{G}</math> має гомоморфізм у <math>\vec{H}</math>. Тому граф <math>G</math> <math>k</math>-розфарбовуваний (має гомоморфізм у <math>K_k</math>) тоді і тільки тоді, коли деяка орієнтація <math>G</math> має гомоморфізм у <math>\vec{T}_k</math>{{Sfn|Hell, Nešetřil|2004|с=13–14}}.

Фольклорна теорема свідчить, що для будь-яких <math>k</math> орієнтований граф <math>G</math> має гомоморфізм у <math>\vec{T}_k</math> тоді і тільки тоді, коли він не допускає гомоморфізму з <math>\vec{P}_{k+1}</math>{{Sfn|Hell, Nešetřil|2004|с=Proposition 1.20}}. Тут <math>\vec{P}_n</math>&nbsp;— орієнтований шлях з вершинами 1, 2, …, <math>n</math> і дугами з ''i'' в ''i'' + 1 для ''i'' = 1, 2, …, <math>n</math>&nbsp;— 1. Таким чином, граф <math>k</math>-розфарбовуваний тоді і тільки тоді, коли він має орієнтацію, яка не допускає гомоморфізму з <math>\vec{P}_{k+1}</math>. Це твердження можна злегка посилити до твердження, що граф <math>k</math>-розфарбовуваний тоді і тільки тоді, коли деяка орієнтація не містить орієнтованого шляху довжини <math>k</math> (немає <math>\vec{P}_{k+1}</math> як підграфу). Це [[теорема Галлаї - Хассе - Роя - Вітавера]].

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

=== Приклади ===
[[Файл:Graph_of_non-adjacent_weekdays.svg|міні| Граф <math>H</math> несусідніх днів тижня ізоморфний [[Доповнення графу|доповненню графу]] <math>C_7</math> і в [[Колове розфарбовування#Колові повні графи|коловій кліці]] <math>K_7/2</math>]]
Деякі задачі розкладів можна промоделювати як питання про знаходження гомоморфізмів графу{{Sfn|Cameron|2006|с=1}}{{Sfn|Hell, Nešetřil|2004|с=§1.8}}. Як приклад, можна спробувати призначити практичні заняття так, щоб два курси, відвідувані тим самим студентом, не були в часі занадто близькими. Курси утворюють граф <math>G</math>, з ребрами між двома курсами, якщо їх відвідує один і той самий студент. Можливий час проведення курсів утворює граф <math>H</math> з ребрами між двома часовими вікнами, якщо відстань за часом між ними досить велика. Наприклад, якщо потрібно мати циклічний щотижневий розклад, такий, що кожен студент приходить на практичні заняття через день, то граф <math>H</math> має бути [[Доповнення графу|доповненням графу]] <math>C_7</math>. Гомоморфізм графу з <math>G</math> в <math>H</math> є тоді призначенням курсів за часовими вікнами{{Sfn|Cameron|2006|с=1}}. Щоб додати вимогу, скажімо, щоб жоден студент не мав заняття як у п'ятницю, так і в понеділок, досить видалити одне ребро з графу <math>H</math>.

Просту задачу {{Не перекладено|Розподіл частот|розподілу частот|en|frequency allocation}} можна поставити в такий спосіб. Є кілька передавачів [[Бездротова мережа|бездротової мережі]]. Потрібно вибрати на кожному з них частотний канал, яким він буде передавати дані. Щоб уникнути [[Електромагнітна завада|завад]], географічно близькі передавачі повинні мати канали з достатньо відмінними частотами. Якщо цю умову обмежено простим порогом для понять «географічно близькі» і «достатньо далекі», допустимий вибір каналів відповідає знову гомоморфізму графу. Тут графом <math>G</math> буде набір передавачів з ребрами між ними, якщо вони географічно близькі, а графом <math>H</math> буде набір каналів з ребрами між каналами, якщо частоти мало відрізняються. Хоча ця модель дуже спрощена, вона допускає деяку гнучкість&nbsp;— для пари передавачів, які не близькі, але можуть заважати один одному через географічні особливості, можна додати дугу в <math>G</math>. А дугу між передавачами, які не працюють одночасно, можна з графу видалити. Аналогічно, ребро між парою каналів, які далеко один від одного, але мають завади у вигляді [[Гармоніки|гармонік]] можна видалити з графу <math>H</math>{{Sfn|Hell, Nešetřil|2004|с=30–31}}.

У кожному випадку ці спрощені моделі показують багато особливостей, які слід відпрацьовувати на практиці{{Sfn|Hell, Nešetřil|2004|с=31–32}}. [[Задача виконання обмежень|Задачі виконання обмежень]], які узагальнюють задачі гомоморфізму графу, можуть встановлювати додаткові типи умов (такі як індивідуальні переваги або обмеження на число призначень, що збігаються). Це дозволяє зробити моделі реалістичнішими і практичнішими.

=== Формальна точка зору ===
Неорієнтовані й орієнтовані графи можна розглядати як часті випадки загальнішого поняття&nbsp;— {{Не перекладено|Структура (математична логіка)|реляційні структури|en|Structure (mathematical logic)}} (які визначаються як множина з кортежем відношень на ньому). Орієнтовані графи є структурами з одним бінарним відношенням (суміжність) на області (множині вершин)<ref name="HN-csp">{{Harvnb|Hell|Nešetřil|2004}}. Зауважимо, що ''реляційні структури'' в статті називають ''реляційними системами''.</ref>{{Sfn|Hell, Nešetřil|2008}}. З цієї точки зору {{Не перекладено|Структура (математична логіка)|гомоморфізми|en|Structure (mathematical logic)}} таких структур є точно гомоморфізмами графів. У загальному випадку питання пошуку гомоморфізму з однієї структури в іншу є [[Задача виконання обмежень|задачею виконання обмежень]]. Випадок графів дає конкретний перший крок, який допомагає зрозуміти складніші задачі виконання обмежень. Багато алгоритмічних методів пошуку гомоморфізмів графу, на зразок [[Пошук з вертанням|пошуку з вертанням]], {{Не перекладено|Локальна несуперечливість|поширення обмежень|en|constraint propagation}}<!-- Проблема вікіфікації: Сторінка [[:en:constraint propagation]] (→ [[:en:Local consistency]]) перекладена як [[Локальна сумісність]], хоча хотіли [[Локальна несуперечливість]] (SashkoR0B0T)--> і {{Не перекладено|Локальний пошук (виконання обмежень)|локального пошуку|en|Local search (constraint satisfaction)}} застосовні до всіх задач виконання обмежень{{Sfn|Hell, Nešetřil|2008}}.

Для графів <math>G</math> і <math>H</math> питання, чи має граф <math>G</math> гомоморфізм у граф <math>H</math>, відповідає окремому випадку задачі виконання обмежень з одним видом обмежень{{Sfn|Hell, Nešetřil|2008}}. У цій задачі ''змінними'' будуть вершини графу <math>G</math>, а ''областю значень'' кожної змінної буде набір вершин графу <math>H</math>. ''Розв'язком'' є функція, яка призначає кожній змінній елемент з області значень, так що функція ''f'' відображає <math>V(G)</math> у <math>V(G)</math>.'' Кожне ребро або дуга<ref>Нагадаємо, зазвичай ребра орієнтованого графу називають дугами.</ref> <math>(u, v)</math> графу <math>G</math> тоді відповідає ''обмеженню'' <math>((u,v), E(H))</math>. Це обмеження означає, що розв'язок має відображати дугу <math>(u, v)</math> в пару <math>(f(u), f(v))</math>, яка є відношенням <math>E(H)</math>, тобто, в дугу графу <math>H</math>. Розв'язком задачі є розв'язок, який задовольняє всім обмеженням, тобто це в точно гомоморфізм з <math>G</math> в <math>H</math>.

== Структура гомоморфізмів ==
Суперпозиції гомоморфізмів є гомоморфізмами{{Sfn|Hell, Nešetřil|2004|с=§1.7}}. Зокрема, відношення <math>\to</math> на графах транзитивне (і, тривіально, рефлексивне), так що це відношення є [[Передпорядок|передпорядком]] на графах{{Sfn|Hell, Nešetřil|2004|с=§3.1}}. Будемо позначати [[Відношення еквівалентності|клас еквівалентності]] графу <math>G</math> за гомоморфізмом через <math>[G]</math>. Клас еквівалентності можожна подати єдиним ядром у <math>[G]</math>.'' Відношення <math>\to</math> [[Частково впорядкована множина|частково впорядковане]] на цих класах еквівалентності. Воно визначає [[Частково впорядкована множина|частково впорядковану множину]]{{Sfn|Hell, Nešetřil|2004|с=Theorem 3.1}}.

Нехай <math>G<H</math> означає, що існує гомоморфізм з <math>G</math> в <math>H</math>, але немає гомоморфізму з <math>H</math> у <math>G</math>. Відношення <math>\to</math> є [[щільний порядок|щільним порядком]], це означає, що для всіх (неорієнтованих) графів <math>G</math>, <math>H</math> таких, що <math>G<H</math>, існує граф <math>K</math>, такий, що <math>G<H</math> (це виконується у всіх випадках, за винятком тривіальних випадків <math>G=K_0</math> або <math>K_1</math>){{Sfn|Hell, Nešetřil|2004|с=Theorem 3.30}}{{Sfn|Geňa, Tardif|1997|с=Theorem 2.33}}{{Sfn|Welzl|1982|с=29–41}}. Наприклад, між будь-якими двома [[Повний граф|повними графами]] (за винятком <math>K_0, K_1</math>) є нескінченно багато [[Колове розфарбовування#Колові повні графи|колових повних графів]], відповідних раціональним числам{{Sfn|Hell, Nešetřil|2004|с=192}}{{Sfn|Geňa, Tardif|1997|с=127}}.

Частково впорядкована множина класів еквівалентності графів за гомоморфізмом є [[Дистрибутивна ґратка|дистрибутивною ґраткою]], з [[Об'єднання і перетин|об'єднанням]] <math>[G]</math> і <math>[H]</math>, визначеним як (клас еквівалентності) [[диз'юнктне об'єднання]] <math>[G \cup H]</math>, і [[Об'єднання і перетин|перетином]] <math>[G]</math> і <math>[H]</math> визначеним як [[Тензорний добуток графів|тензорний добуток]] <math>[G \times H]</math> (вибір графів <math>G</math> і <math>H</math> як представників класів еквівалентності <math>[ G ]</math> і <math>[H]</math> не має значення){{Sfn|Hell, Nešetřil|2004|с=Proposition 3.2, distributivity is stated in Proposition 2.4}}{{Sfn|Geňa, Tardif|1997|с=Theorem 2.37}}. {{Не перекладено|Незвідні в об'єднанні||en|join-irreducible}}<!-- Проблема вікіфікації: Сторінка [[:en:join-irreducible]] (→ [[:en:Lattice (order)#Important lattice-theoretic notions]]) перекладена як [[Ґратка (порядок)]], хоча хотіли [[Незвідні в об'єднанні]] (SashkoR0B0T)--> елементи цієї ґратки&nbsp;— це точно [[Зв'язний граф|зв'язні]] графи. Це можна показати, використовуючи факт, що гомоморфізм відображає зв'язний граф у зв'язну компоненту цільового графу{{Sfn|Kwuida, Lehtonen|2011|с=251–265}}{{Sfn|Gray|2014}}. [[Ґратка (порядок)|Незвідні в перетині]] елементи цієї ґратки&nbsp;— це точно [[Гіпотеза Гедетніємі|мультиплікативні графи]]. Це графи <math>K</math>, такі, що добуток <math>G \times H</math> має гомоморфізм у <math>K</math> тільки тоді, коли один із графів <math>G</math> або <math>H</math> має такий гомоморфізм. Виявлення мультиплікативних графів є серцевиною [[Гіпотеза Гедетніємі|гіпотези Гедетніємі]]{{Sfn|Tardif|2008|с=46–57}}{{Sfn|Dwight, Sauer|1996|с=125–139}}.

Гомоморфізми графів утворюють також [[Теорія категорій|категорію]] з графами як об'єкти і гомоморфізмами як стрілками{{Sfn|Hell, Nešetřil|2004|с=125}}. [[Початковий та термінальний об'єкти|Початковим об'єктом]] є порожній граф, тоді як [[Початковий та термінальний об'єкти|термінальним об'єктом]] є граф із однією вершиною і однією [[Петля (теорія графів)|петлею]] в цій вершині. [[Тензорний добуток графів]] є [[Добуток (теорія категорій)|добутком у теорії категорій]] і [[Гіпотеза Гедетніемі|експоненційний граф]] є [[Експоненційний об'єкт|експоненційним]] об'єктом для категорії{{Sfn|Dwight, Sauer|1996|с=125–139}}{{Sfn|Gray|2014}}. Оскільки ці дві операції завжди визначені, категорія графів є [[Декартово замкнута категорія|декартово замкнутою категорією]]. З тієї ж причини ґратка класів еквівалентності графів за гомоморфізмами, фактично, є [[Алгебра Гейтинга|алгеброю Гейтинга]]{{Sfn|Dwight, Sauer|1996|с=125–139}}{{Sfn|Gray|2014}}.

Для орієнтованих графів застосовуються ті самі визначення. Зокрема, <math>\to</math> [[Частково впорядкована множина|частково впорядковане]] на класах еквівалентності орієнтованих графів. Цей порядок відрізняється від порядку <math>\to</math> на класах еквівалентності неорієнтованих графів, але містить його в як підпорядок. Це тому, що будь-який неорієнтований граф можна розглядати як орієнтований, в якому будь-яка дуга <math>(u, v)</math> з'являється разом зі зворотною дугою <math>(v, u)</math>, а це не змінює визначення гомоморфізму. Порядок <math>\to</math> для орієнтованих графів знову є дистрибутивною ґраткою і алгеброю Гейтинга з операціями об'єднання і перетину, визначених як раніше. Однак цей порядок не щільний. Існує також категорія з орієнтованими графами як об'єктами і гомоморфізмами як стрілками, яка також є [[Декартово замкнута категорія|декартово замкнутою категорією]]{{Sfn|Brown, Morris, Shrimpton, Wensley|2008}}{{Sfn|Gray|2014}}.

=== Непорівнянні графи ===
[[Файл:Groetzsch-graph.svg|праворуч|міні| [[Граф Ґрьоча]] непорівнянний з трикутником <math>K_3</math>]]
Є багато непорівнянних графів за предпорядком гомоморфізмів, тобто пари графів, таких, що немає гомоморфізмів з одного в інший{{Sfn|Hell, Nešetřil|2004|с=7}}. Один зі шляхів побудови таких графів&nbsp;— розгляд [[Обхват (теорія графів)|непарного обхвату]] графу <math>G</math>, тобто довжини його найкоротшого циклу непарної довжини. Непарний обхват, еквівалентно, є найменшим непарним числом <math>g</math>, для якого існує гомоморфізм з [[Циклічний граф|графу-циклу]] з <math>g</math> вершинами в <math>G</math>. З цієї причини, якщо <math>G \to H</math>, То непарний обхват графу <math>G</math> більший або дорівнює непарному обхвату графу <math>H</math>{{Sfn|Geňa, Tardif|1997|с=Observation 2.6}}.

З іншого боку, якщо <math>G \to H</math>, То хроматичне число графу <math>G</math> менше або дорівнює хроматичному числу графу <math>H</math>. Тому, якщо граф <math>G</math> має строго більший непарний обхват, ніж <math>H</math> і строго більше хроматичне число, ніж <math>H</math>, то <math>G</math> і <math>H</math> непорівнянні.{{Sfn|Hell, Nešetřil|2004|с=7}} Наприклад, [[граф Ґрьоча]] є 4-хроматичним (розфарбовується в 4 кольори) і вільним від трикутників (він має обхват 4 і непарний обхват 5){{R|MWGG}}, так що він несумісний з трикутником <math>K_3</math>.

Прикладами графів з довільно великими значеннями непарного обхвату і хроматичного числа є [[Кнезерів граф|кнезерові графи]]{{Sfn|Geňa, Tardif|1997|с=Proposition 3.14}} й [[Мичельськіан|узагальнені мичельськіани]]{{Sfn|Gyárfás, Jensen, Stiebitz|2004|с=1–14}}. Послідовність таких графів з одночасним збільшенням значень обох параметрів дає нескінченне число непорівнянних графів ([[антиланцюг]] у предпорядку гомоморфізмів){{Sfn|Hell, Nešetřil|2004|с=Proposition 3.4}}. Інші властивості, такі як [[Щільний порядок|щільність]] передпорядку гомоморфізмів, можна довести за допомогою таких родин{{Sfn|Hell, Nešetřil|2004|с=96}}. Побудови графів з більшими значеннями хроматичного числа і обхвату, а не просто непарного обхвату, також можливі, але складніші (див. [[Обхват (теорія графів)|Обхват і розфарбування графів]]).

Серед орієнтованих графів знайти непорівнянні пари значно простіше. Наприклад, розглянемо орієнтовані графи-цикли <math>\vec{C}_n</math> з вершинами 1, 2, …, <math>n</math> і ребрами з ''i'' в ''i'' + 1 (для ''i'' = 1, 2, …, <math>n</math>&nbsp;— 1) і з <math>n</math> в 1. Існує гомоморфізм із <math>\vec{C}_n</math> в <math>\vec{C}_k (n, k \geqslant 3)</math> [[Тоді й лише тоді|тоді і тільки тоді]], коли <math>n</math> кратне <math>k</math>. Зокрема орієнтовані графи-цикли <math>\vec{C}_n</math> з простими <math>n</math> усі непорівнянні{{Sfn|Hell, Nešetřil|2004|с=35}}.

== Обчислювальна складність ==
У задачі про гомоморфізм графу примірник задачі складається з пари графів (<math>G</math>, <math>H</math>), а розв'язком є гомоморфізм із <math>G</math> в <math>H</math>. Загальна [[Проблема вибору|задача розв'язності]], яка питає, чи має ця задача розв'язок, [[NP-повна задача|NP-повна]]{{Sfn|Bodirsky|2007|с=§1.3}}. Однак обмеження на графи дають низку різних задач, деякі з яких розв'язати легше. Методи, які використовують обмеження на лівий граф <math>G</math>, дуже відрізняються від методів, що використовуються на правий граф <math>H</math>, але в кожному разі дихотомія (строгі межі між простими і складними випадками) відома або передбачається.

=== Гомоморфізми у фіксований граф ===
Задача про гомоморфізм із фіксованим графом <math>H</math> з правого боку кожного примірника називається задачею <math>H</math>-розфарбування. Коли <math>H</math> є повним графом <math>K_k</math>, це [[Розфарбовування графів|задача <math>k</math>-розфарбовування графу]], яка розв'язна за поліноміальний час для <math>k</math> = 0, 1, 2 і [[NP-повна задача|NP-повна]] в інших випадках{{Sfn|Hell, Nešetřil|2004|с=§5.1}}. Зокрема, можливість <math>K_2</math>-розфарбування графу <math>G</math> еквівалентна [[Двочастковий граф|двочастковості]] графу <math>G</math>, що можна перевірити за лінійний час. Загальніше, коли <math>H</math> є двочастковим графом, можливість <math>H</math>-розфарбування еквівалентна можливості <math>K_2</math>-розфарбування (або <math>K_0</math> / <math>K_1</math>-розфарбовуваності, коли <math>H</math> порожнє або не має ребер), а отже, так само легко розв'язується{{Sfn|Hell, Nešetřil|2004|с=Proposition 5.1}}. Павол Хелл і Ярослав Нешетріл довели, що для неорієнтованих графів ніякий інший випадок не є легким:

: '''Теорема Гелла&nbsp;— Нешетріла''' (1990): Задача <math>H</math>-розфарбовування належить класу P, якщо <math>H</math> двочастковий і NP-складна в іншому випадку{{Sfn|Hell, Nešetřil|2004|с=§5.2}}{{Sfn|Hell, Nešetřil|1990|с=92–110}}.

Теорема відома також як ''теорема про дихотомію'' для гомоморфізму (неорієнтованого) графу, оскільки вона ділить задачі <math>H</math>-розфарбовування на NP-повні і задачі класу P без {{Не перекладено|NP-проміжна складність|проміжних|en|NP-intermediate}} випадків. Для орієнтованих графів ситуація складніша і, фактично, еквівалентна загальнішому питанню опису {{Не перекладено|складність дотримання обмежень|складності дотримання обмежень|en|Complexity of constraint satisfaction}}{{Sfn|Hell, Nešetřil|2004|с=§5.3}}. Виявляється, що задачі <math>H</math>-розфарбовування для орієнтованих графів настільки ж загальні і настільки ж різноманітні, як і задачі дотримання обмежень з будь-якими іншими видами обмежень{{Sfn|Hell, Nešetřil|2004|с=Theorem 5.14}}{{Sfn|Feder, Vardi|1998|с=57–104}}. Формально, (скінченна) ''мова обмежень'' <math>\Gamma</math> є скінченною областю і скінченним набором відношень у цій області. <math>CSP(\Gamma)</math> є задачею дотримання обмежень, де примірникам дозволяється використання тільки обмежень з <math>\Gamma</math>.

: '''Теорема''' (Федер, [[Моше Варді|Варді]] 1998): Для будь-якої мови обмежень <math>\Gamma</math> задача <math>CSP(\Gamma)</math> еквівалентна після [[Поліноміальна звідність|поліноміального зведення]] деякій задачі <math>H</math>-розфарбовування для деякого орієнтованого графу <math>H</math>{{Sfn|Feder, Vardi|1998|с=57–104}}.

Інтуїтивно це означає, що будь-яка алгоритмічна техніка або результат про складність, застосовні до задач <math>H</math>-розфарбовування для орієнтованих графів <math>H</math>, застосовні також і для загальних задач дотримання обмежень. Зокрема, можна запитати, чи можна теорему Гелла&nbsp;— Нешетріла поширити на орієнтовані графи. За теоремою вище це еквівалентно гіпотезі Федера&nbsp;— Варді про дихотомію задач дотримання обмежень, яка стверджує, що для будь-якої мови обмежень <math>\Gamma</math> задача <math>CSP(\Gamma)</math> або NP-повна, або належить до класу P{{Sfn|Bodirsky|2007|с=§1.3}}.

=== Гомоморфізми з фіксованого сімейства графів ===
Задачу про гомоморфізм з одним фіксованим графом <math>G</math> ліворуч можна розв'язати [[Пошук грубою силою|повним перебором]] за час |''V''(<math>H</math>)|<sup>O(|''V''(<math>G</math>)|)</sup>, тобто поліноміально від розміру вхідного графу <math>H</math>{{Sfn|Cygan, Fomin, Golovnev и др.|2016|с=1643–1649}}. Іншими словами, задача тривіальна в P для графів <math>G</math> обмеженого розміру. Цікаве питання по те, які інші властивості графу <math>G</math>, крім розміру, уможливлюють поліноміальні алгоритми.

Ключовою властивістю виявляється [[Деревна ширина (теорія графів)|деревна ширина]], міра, наскільки граф схожий на дерево. Для графу <math>G</math> з деревною шириною, що не перевищує <math>k</math>, і графу <math>H</math> задачу про гомоморфізм можна розв'язати за час |''V''(<math>H</math>)|<sup>O(<math>k</math>)</sup> стандартними методами [[Динамічне програмування|динамічного програмування]]. Фактично, досить припустити, що ядро графу <math>G</math> має деревну ширину, яка не перевищує ''k.'' Це так навіть у разі, коли ядро не відоме{{Sfn|Dalmau, Kolaitis, Vardi|2002|с=310–326}}{{Sfn|Grohe|2007}}.

Показник в алгоритмі з часом роботи |''V''(<math>H</math>)|<sup>O(<math>k</math>)</sup> не можна знизити істотно&nbsp;— не існує алгоритму, який працює за час |''V''(<math>H</math>)|<sup>o(tw(<math>G</math>)/log tw(<math>G</math>))</sup> при істинності [[Гіпотеза про експоненційний час|гіпотези про експоненційному часу]] ({{Lang-en|exponential time hypothesis}}, ETH), навіть якщо вхід обмежено будь-яким класом графів необмеженої деревної ширини{{Sfn|Marx|2010|с=85–112}}. ETH є недоведеним припущенням, аналогічним припущенню [[Рівність класів P і NP|P ≠ NP]], але більш строгим. За тих самих припущень немає інших властивостей, які можна використати для отримання алгоритмів поліноміального часу. Це формалізує теорема:

: '''Теорема''' (Мартін Грое): Для [[Рекурсивна множина|обчисле́нного]] класу графів <math>\mathcal{G}</math>, задача про гомоморфізм для <math>(G,H)</math> з <math>G \in \mathcal{G}</math> належить P [[Тоді й лише тоді|тоді і тільки тоді]], коли графи <math>\mathcal{G}</math> мають ядра обмеженої деревної ширини (в допущенні ETH){{Sfn|Grohe|2007}}.

Можна поставити питання, чи розв'язна задача з довільно високою залежністю від <math>G</math>, але з фіксованою поліноміальною залежністю від розміру графу <math>H</math>. Відповідь позитивна, якщо ми обмежимо граф <math>G</math> класом з ядрами обмеженої деревної ширини, і негативна для всіх інших класів{{Sfn|Grohe|2007}}. Мовою {{Не перекладено|Параметризована складність|параметризованої|en|Parameterized complexity}} складності це твердження формально свідчить, що задача про гомоморфізм з графом <math>\mathcal{G}</math>, параметризована за розміром (кількістю ребер) графу <math>G</math>, показує дихотомію. Вона {{Не перекладено|Параметризована складність|фіксовано-параметрично розв'язна|en|fixed-parameter tractable}}, якщо графи в класі <math>\mathcal{G}</math> мають ядра обмеженої деревної ширини, і {{Не перекладено|Параметризована складність|W[1]-повна|en|Parameterized complexity}} в іншому випадку.

Те ж твердження істинне для загальніших задач дотримання обмежень (або, іншими словами, для реляційних структур). Потрібно єдине припущення, що обмеження можуть залучати лиш обмежене число змінних. Параметром тоді є деревна ширина {{Не перекладено|Граф обмежень|основного графу обмежень|en|primal constraint graph}}{{Sfn|Marx|2010|с=85–112}}.

== Див. також ==

* {{Нп|Гіпотеза Сидоренка|3=ru|4=Гипотеза Сидоренко}}

== Примітки ==
{{Reflist|2|refs=<ref name=MWGG>{{mathworld|title=Grötzsch Graph|urlname=GroetzschGraph}}</ref>
<ref name=Fiala02>*{{статья
|автор=Fiala J., Kratochvíl J.
|заглавие=Partial covers of graphs
|год=2002
|издание=Discussiones Mathematicae Graph Theory
|том=22
|выпуск=1
|страницы=89–99
|doi=10.7151/dmgt.1159
}}</ref>}}

== Література ==
{{Refbegin|colwidth=30em}}
* {{Стаття|author=Welzl E.|ref=Welzl|title=Color-families are dense|date=1982|видання=[[Theoretical Computer Science|Theoret. Comput. Sci.]]|том=17|pages=29–41|doi=10.1016/0304-3975(82)90129-3}}
* {{Стаття|ref=Hell, Nešetřil|author=Pavol Hell, Jaroslav Nešetřil|title=On the complexity of H-coloring|date=1990|видання=[[Journal of Combinatorial Theory, Series B|JCTB]]|том=48|issue=1|pages=92–110|doi=10.1016/0095-8956(90)90132-J}}
* {{Стаття|title=On Graphs With Strongly Independent Color-Classes|author=Gyárfás A., Jensen T., Stiebitz M.|ref=Gyárfás, Jensen, Stiebitz|date=2004|doi=10.1002/jgt.10165|видання=[[Journal of Graph Theory|J. Graph Theory]]|том=46|issue=1|pages=1–14}}

* {{Стаття|author=Léonard Kwuida, Erkko Lehtonen|ref=Kwuida, Lehtonen|title=On the Homomorphism Order of Labeled Posets|doi=10.1007/s11083-010-9169-x|date=2011|arxiv=0911.0200|видання=[[Order (journal)|Order]]|том=28|issue=2|pages=251–265|publisher=Springer}}
* {{Стаття|author=Tardif C.|ref=Tardif|title=Hedetniemi's conjecture, 40 years later|url=http://www.mast.queensu.ca/~ctardif/articles/gtn5406rp.pdf|pages=46–57|том=54|видання=Graph Theory Notes of New York|date=2008|accessdate=30 червня 2021|archivedate=12 липня 2021|archiveurl=https://web.archive.org/web/20210712104609/https://mast.queensu.ca/~ctardif/articles/gtn5406rp.pdf}}
* {{Стаття|author=Dwight D., Sauer N.|ref=Dwight, Sauer|title=Lattices arising in categorial investigations of Hedetniemi's conjecture|видання=[[Discrete Mathematics|Discrete Math.]]|том=152|issue=1—3|date=1996|pages=125–139|doi=10.1016/0012-365X(94)00298-W}}
* {{Стаття|author=Dániel Marx|ref=Marx|title=Can You Beat Treewidth?|видання=[[Theory of Computing]]|date=2010|том=6|pages=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.
|ref = Cygan, Fomin, Golovnev и др.
|видавництво = [[Society for Industrial and Applied Mathematics|SIAM]]
|рік = 2016
|ISBN = 978-1-611974-33-1
|bibcode = 2015arXiv150703738F
|назва = Tight bounds for graph homomorphism and subgraph isomorphism
}}
* {{Книга
|автор = Víctor Dalmau, Phokion G. Kolaitis, Moshe Y. Vardi
|ref = Dalmau, Kolaitis, Vardi
|заголовок = 
|сторінки = 310–326
|рік = 2002
|doi = 10.1007/3-540-46135-3_21
|назва = Constraint Satisfaction, Bounded Treewidth, and Finite-Variable Logics
}}
* {{Стаття|ref=Grohe|author=Martin Grohe|title=The complexity of homomorphism and constraint satisfaction problems seen from the other side|том=54|issue=1|date=2007|видання=[[Journal of the ACM|J. ACM]]|doi=10.1145/1206035.1206036}}
* {{Стаття|author=Tomás Feder, [[Моше Варді|Moshe Y. Vardi]]|ref=Feder, Vardi|title=The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory|date=1998|видання=[[SIAM Journal on Computing|SIAM J. Comput.]]|том=28|issue=1|pages=57–104|doi=10.1137/S0097539794266766|url=http://theory.stanford.edu/~tomas/constraint.ps|accessdate=30 червня 2021|archivedate=6 лютого 2022|archiveurl=https://web.archive.org/web/20220206173456/http://theory.stanford.edu/~tomas/constraint.ps}}
{{Refend}}

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

* {{Стаття|ref=Cameron|author=Peter Cameron|title=Graph Homomorphisms, Combinatorics Study Group Notes|date=2006|url=http://www.maths.qmul.ac.uk/~pjc/csgnotes/hom1.pdf|accessdate=30 червня 2021|archivedate=7 травня 2021|archiveurl=https://web.archive.org/web/20210507001500/http://www.maths.qmul.ac.uk/~pjc/csgnotes/hom1.pdf}}
* {{Стаття|ref=Hell, Nešetřil|author=Pavol Hell, Jaroslav Nešetřil|publisher=Oxford University Press|title=Graphs and Homomorphisms|серія=Oxford Lecture Series in Mathematics and Its Applications|том=28|date=2004|isbn=0-19-852817-5|url=http://www.cs.sfu.ca/~pavol/hombook.html|accessdate=30 червня 2021|archivedate=6 травня 2021|archiveurl=https://web.archive.org/web/20210506175223/https://www2.cs.sfu.ca/~pavol/hombook.html}}
* {{Книга
|автор = Geňa H., Tardif C.
|ref = Geňa, Tardif
|частина = Graph homomorphisms: structure and symmetry
|заголовок = Graph Symmetry: Algebraic Methods and Applications
|видавництво = Springer
|рік = 1997
|сторінки = 107–166
|doi = 10.1007/978-94-015-8937-6_4
|посилання = http://www.mast.queensu.ca/~ctardif/articles/ghss.pdf
|назва = 
|archivedate = 11 липня 2021
|archiveurl = https://web.archive.org/web/20210711070549/https://mast.queensu.ca/~ctardif/articles/ghss.pdf
}}
* {{Книга
|ref = Godsil, Royle
|автор = Chris Godsil, Gordon Royle
|заголовок = Algebraic Graph Theory
|doi = 10.1007/978-1-4613-0163-9
|ISBN = 978-1-4613-0163-9
|рік = 2001
|видавництво = Springer–Verlag New York
|серія = Graduate Texts in Mathematics
|том = 207
|частина = 6. Homomorphisms
}}

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

* {{Стаття|author=Bodirsky M.|ref=Bodirsky|title=Graph Homomorphisms and Universal Algebra, Course Notes|url=http://www.math.tu-dresden.de/~bodirsky/Graph-Homomorphisms.pdf|date=2007|accessdate=30 червня 2021|archivedate=1 грудня 2020|archiveurl=https://web.archive.org/web/20201201154324/http://www.math.tu-dresden.de/~bodirsky/Graph-Homomorphisms.pdf}}
* {{Стаття|ref=Hell, Nešetřil|author=Pavol Hell, Jaroslav Nešetřil|title=Colouring, constraint satisfaction, and complexity|date=2008|видання=Computer Science Review|том=2|issue=2|pages=143–163|doi=10.1016/j.cosrev.2008.10.003|url=http://www.cs.sfu.ca/~pavol/cspCCC.pdf|accessdate=30 червня 2021|archivedate=6 липня 2017|archiveurl=https://web.archive.org/web/20170706115247/http://www.cs.sfu.ca/~pavol/cspCCC.pdf}}

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

* {{Стаття|author=Brown R., Morris I., Shrimpton J., Wensley C. D.|ref=Brown, Morris, Shrimpton, Wensley|title=Graphs of morphisms of graphs|видання=[[Electronic Journal of Combinatorics]]|date=2008|том=15|issue=1|pages=A1|url=http://www.combinatorics.org/ojs/index.php/eljc/article/view/v15i1a1|accessdate=30 червня 2021|archivedate=11 липня 2021|archiveurl=https://web.archive.org/web/20210711045636/https://www.combinatorics.org/ojs/index.php/eljc/article/view/v15i1a1}}
* {{Стаття|ref=Gray|author=Gray C. T.|title=The Digraph Lattice|date=2014|url=http://vrs.amsi.org.au/wp-content/uploads/sites/6/2014/09/CORRECTED-digraph-lattice-Gray-updated.pdf|accessdate=30 червня 2021|archivedate=20 січня 2022|archiveurl=https://web.archive.org/web/20220120165848/http://vrs.amsi.org.au/wp-content/uploads/sites/6/2014/09/CORRECTED-digraph-lattice-Gray-updated.pdf}} ([[Australian Mathematical Sciences Institute|AMSI]] [http://vrs.amsi.org.au/projects/ Vacation Research Scholarships] {{Webarchive|url=https://web.archive.org/web/20180814235547/http://vrs.amsi.org.au/projects/ |date=14 серпня 2018 }}, студентський звіт про дослідження під керівництвом Brian Davey і Jane Pitkethly, {{Нп|Університет Ла Троба|3=en|4=La Trobe University}}).

[[Категорія:Теорія графів]]
[[Категорія:Морфізми]]
[[Категорія:NP-повні задачі]]