Гомоморфізм графів — це відображення між двома графами, що не порушує структури. Конкретніше, це відображення між наборами вершин двох графів, яке відображає суміжні вершини в суміжні.
Гомоморфізми узагальнюють різні поняття розфарбовування графів і дозволяють формулювати важливі класи задач виконання обмежень, таких як деякі задачі або задачі . Факт, що гомоморфізми можна використати послідовно, приводить до багатих алгебричних структур — передпорядку на графах, дистрибутивної ґратки і категорій (одна для неорієнтованих графів і одна для орієнтованих графів). Обчислювальна складність пошуку гомоморфізму між заданими графами в загальному випадку позамежна, але відомо багато окремих випадків, коли задача здійсненна за поліноміальний час. Межі між розв'язними і нездоланними випадками є галуззю активних досліджень.
Визначення У цій статті, якщо не сказано інше, під графами розуміють скінченні неорієнтовані графи з дозволеними петлями, але кратні ребра (паралельні) не дозволені. Гомоморфізм з графу у граф , що записується як
,
це функція з у , яка відображає кінцеві точки кожного ребра з в кінцеві точки деякого ребра з . Формально, з випливає , для всіх пар вершин , з . Якщо існує деякий гомоморфізм з в , то кажуть, що граф гомоморфний графу , або що він -розфарбовуваний. Це часто позначають як
.
Визначення, наведене вище, поширюється на орієнтовані графи. Тоді для гомоморфізму є дугою (орієнтованим ребром) графу , коли є дугою графу .Існує ін'єктивний гомоморфізм з в (тобто відображення, яке ніколи не відображає різні вершини в одну) тоді і тільки тоді, коли є підграфом графу . Якщо гомоморфізм є бієкцією (відповідністю один-до-одного між вершинами графу і графу ) обернена функція якого є також гомоморфізмом графу, тоді є ізоморфізмом графів.
Накривні відображення є частим видом гомоморфізмів, який відбиває визначення і багато властивостей накриття в топології. Вони визначаються як сюр'єктивні гомоморфізми, які локально бієктивні, тобто є бієкція в околі кожної вершини. Прикладом є подвійне покриття двочастковим графом, утворене з графу розбиттям кожної вершини на і і заміною кожного ребра , на два ребра і . Функція, що відображає і у початкового графу, є гомоморфізмом і накривним відображенням.
Гомеоморфізм графу є окремим поняттям, не пов'язаним прямо з гомоморфізми. Грубо кажучи, він вимагає ін'єктивності, але дозволяє відображення ребер у шляхи (а не просто в ребра). Мінори графу залишаються слабшим поняттям.
Ядра і ретракти
Два графи і гомоморфно еквівалентні, якщо і .
Ретракція — це гомоморфізм r з графу в підграф графу , такий, що для кожної вершини з . У цьому випадку підграф називається ретрактом графу .
Ядро — це граф, який не має гомоморфізму в будь-який власний підграф. Еквівалентно, ядро можна визначити як граф, який не є ретрактом для будь-якого власного підграфу. Будь-який граф гомоморфно еквівалентний єдиному ядру (з точністю до ізоморфізму), яке називають ядром графу . Зауважимо, що це не так для нескінченних графів загального вигляду. Однак ті ж визначення застосовні і до орієнтованих графів і орієнтований граф також еквівалентний єдиному ядру. Будь-який неорієнтований і орієнтований граф містить своє ядро і як ретракт, і як породжений підграф.
Наприклад, усі повні графи і всі непарні цикли (циклічні графи непарної довжини) є ядрами. Будь-який 3-розфарбовуваний граф , що містить трикутник (тобто має повний граф як підграф) гомеоморфно еквівалентний . Це тому, з одного боку, що 3-розфарбування графу , це те саме, що й гомоморфізм , як пояснено нижче. З іншого боку, будь-який підграф графу тривіально допускає гомоморфізм у , звідки випливає, що . Це також означає, що є ядром будь-якого такого графу .'Аналогічно, будь-який двочастковий граф, який має принаймні одне ребро, еквівалентний .
Зв'язок з розфарбуваннями -розфарбування для деякого цілого — це призначення одного з кольорів кожній вершині графу так, що кінцеві вершини кожного ребра мають різні кольори. -розфарбування графу відповідають точно гомоморфізмам з в повний граф . Більш того, вершини графу відповідають кольорам і два кольори суміжні як вершини графу тоді і тільки тоді, коли вони різні. Отже, функція визначає гомоморфізм у тоді і тільки тоді, коли суміжні вершини графу пофарбовано в різні кольори. Зокрема, граф -розфарбовуваний тоді і тільки тоді, коли -розфарбовуваний.
Якщо є два гомоморфізми і , то їх суперпозиція є також гомоморфізмом. Іншими словами, якщо граф можна розфарбувати в кольорів і існує гомоморфізм в , то можна також розфарбувати в кольорів. Тому з випливає , де означає хроматичне число графу (найменше число кольорів , в які можна розфарбувати граф).
Варіанти Гомоморфізми загального вигляду можна розглядати також як вид розфарбування — якщо вершини фіксованого графу є допустимими кольорами, а ребра графу описують, які кольори сумісні, то -розмальовка графу — це призначення кольорів вершин графу так, що суміжні вершини отримують сумісні кольори. Багато понять розфарбовування графів уміщуються в цю схему і можуть бути виражені як гомоморфізм графів у різні сімейства графів. Колові розфарбування можна визначити за допомогою гомоморфізмів у колові повні графи, уточнюючи звичайне поняття розфарбування. Дробове і b-разове розфарбування можна визначити за допомогою гомоморфізмів у кнезерівські графи. T-розфарбування відповідають гомоморфізмам у деякі нескінченні графи. Орієнтоване розфарбування орієнтованого графу є гомоморфізмом у будь-який орієнтований граф. — це локально ін'єктивний гомоморфізм у доповнення шляху, що означає, що він має бути ін'єктивним в околі кожної вершини.
Орієнтації без довгих шляхів Інший цікавий зв'язок стосується орієнтації графів. Орієнтація неорієнтованого графу — це будь-який орієнтований граф, отриманий вибором із двох можливих орієнтацій кожного ребра. Прикладом орієнтації повного графу є транзитивний турнір з вершинами 1,2, …, і дугами з i в j, коли i < j. Гомоморфізм між орієнтаціями графів і дає гомоморфізм між неорієнтованими графами і , якщо просто нехтувати орієнтації. З іншого боку, якщо дано гомоморфізм між неорієнтованими графами, будь-яку орієнтацію з можна відобразити в орієнтацію графу з , так що має гомоморфізм у . Тому граф -розфарбовуваний (має гомоморфізм у ) тоді і тільки тоді, коли деяка орієнтація має гомоморфізм у .
Фольклорна теорема свідчить, що для будь-яких орієнтований граф має гомоморфізм у тоді і тільки тоді, коли він не допускає гомоморфізму з . Тут — орієнтований шлях з вершинами 1, 2, …, і дугами з i в i + 1 для i = 1, 2, …, — 1. Таким чином, граф -розфарбовуваний тоді і тільки тоді, коли він має орієнтацію, яка не допускає гомоморфізму з . Це твердження можна злегка посилити до твердження, що граф -розфарбовуваний тоді і тільки тоді, коли деяка орієнтація не містить орієнтованого шляху довжини (немає як підграфу). Це теорема Галлаї - Хассе - Роя - Вітавера.
Зв'язок з задачами задоволення обмежень
Приклади
Деякі задачі розкладів можна промоделювати як питання про знаходження гомоморфізмів графу. Як приклад, можна спробувати призначити практичні заняття так, щоб два курси, відвідувані тим самим студентом, не були в часі занадто близькими. Курси утворюють граф , з ребрами між двома курсами, якщо їх відвідує один і той самий студент. Можливий час проведення курсів утворює граф з ребрами між двома часовими вікнами, якщо відстань за часом між ними досить велика. Наприклад, якщо потрібно мати циклічний щотижневий розклад, такий, що кожен студент приходить на практичні заняття через день, то граф має бути доповненням графу . Гомоморфізм графу з в є тоді призначенням курсів за часовими вікнами. Щоб додати вимогу, скажімо, щоб жоден студент не мав заняття як у п'ятницю, так і в понеділок, досить видалити одне ребро з графу .
Просту задачу можна поставити в такий спосіб. Є кілька передавачів бездротової мережі. Потрібно вибрати на кожному з них частотний канал, яким він буде передавати дані. Щоб уникнути завад, географічно близькі передавачі повинні мати канали з достатньо відмінними частотами. Якщо цю умову обмежено простим порогом для понять «географічно близькі» і «достатньо далекі», допустимий вибір каналів відповідає знову гомоморфізму графу. Тут графом буде набір передавачів з ребрами між ними, якщо вони географічно близькі, а графом буде набір каналів з ребрами між каналами, якщо частоти мало відрізняються. Хоча ця модель дуже спрощена, вона допускає деяку гнучкість — для пари передавачів, які не близькі, але можуть заважати один одному через географічні особливості, можна додати дугу в . А дугу між передавачами, які не працюють одночасно, можна з графу видалити. Аналогічно, ребро між парою каналів, які далеко один від одного, але мають завади у вигляді гармонік можна видалити з графу .
У кожному випадку ці спрощені моделі показують багато особливостей, які слід відпрацьовувати на практиці. Задачі виконання обмежень, які узагальнюють задачі гомоморфізму графу, можуть встановлювати додаткові типи умов (такі як індивідуальні переваги або обмеження на число призначень, що збігаються). Це дозволяє зробити моделі реалістичнішими і практичнішими.
Формальна точка зору Неорієнтовані й орієнтовані графи можна розглядати як часті випадки загальнішого поняття — (які визначаються як множина з кортежем відношень на ньому). Орієнтовані графи є структурами з одним бінарним відношенням (суміжність) на області (множині вершин). Зауважимо, що реляційні структури в статті називають реляційними системами.. З цієї точки зору таких структур є точно гомоморфізмами графів. У загальному випадку питання пошуку гомоморфізму з однієї структури в іншу є задачею виконання обмежень. Випадок графів дає конкретний перший крок, який допомагає зрозуміти складніші задачі виконання обмежень. Багато алгоритмічних методів пошуку гомоморфізмів графу, на зразок пошуку з вертанням, поширення обмежень і застосовні до всіх задач виконання обмежень.
Для графів і питання, чи має граф гомоморфізм у граф , відповідає окремому випадку задачі виконання обмежень з одним видом обмежень. У цій задачі змінними будуть вершини графу , а областю значень кожної змінної буде набір вершин графу . Розв'язком є функція, яка призначає кожній змінній елемент з області значень, так що функція f відображає у . Кожне ребро або дугаНагадаємо, зазвичай ребра орієнтованого графу називають дугами. графу тоді відповідає обмеженню . Це обмеження означає, що розв'язок має відображати дугу в пару , яка є відношенням , тобто, в дугу графу . Розв'язком задачі є розв'язок, який задовольняє всім обмеженням, тобто це в точно гомоморфізм з в .
Структура гомоморфізмів Суперпозиції гомоморфізмів є гомоморфізмами. Зокрема, відношення на графах транзитивне (і, тривіально, рефлексивне), так що це відношення є передпорядком на графах. Будемо позначати клас еквівалентності графу за гомоморфізмом через . Клас еквівалентності можожна подати єдиним ядром у . Відношення частково впорядковане на цих класах еквівалентності. Воно визначає частково впорядковану множину.
Нехай означає, що існує гомоморфізм з в , але немає гомоморфізму з у . Відношення є щільним порядком, це означає, що для всіх (неорієнтованих) графів , таких, що , існує граф , такий, що (це виконується у всіх випадках, за винятком тривіальних випадків або ). Наприклад, між будь-якими двома повними графами (за винятком ) є нескінченно багато колових повних графів, відповідних раціональним числам.