Введение

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

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

Еще одна интересная связь касается ориентаций графов. Ориентацией ненаправленного графа G является любой ориентированный граф, полученный выбором одной из двух возможных ориентаций для каждого ребра. Примером ориентации полного графа Kk является транзитивный турнир k с вершинами 1, 2, ..., k и дугами от i к j, когда i < j. Гомоморфизм между ориентациями графов G и H порождает гомоморфизм между ненаправленными графами G и H, просто игнорируя ориентации. С другой стороны, при заданном гомоморфизме G → H между ненаправленными графами, любая ориентация H может быть перенесена обратно в ориентацию G так, чтобы существовал гомоморфизм из G в H. Следовательно, граф G является k-окрашиваемым (имеет гомоморфизм в Kk) тогда и только тогда, когда некоторая ориентация G имеет гомоморфизм в k.

Согласно народной теореме, для всех k ориентированный граф G имеет гомоморфизм в k тогда и только тогда, когда он не допускает гомоморфизма из ориентированного пути k+1. Здесь n – ориентированный граф с вершинами 1, 2, ..., n и ребрами от i к i+1 для i = 1, 2, ..., n-1. Следовательно, граф k-окрашиваемый тогда и только тогда, когда у него есть ориентация, которая не допускает гомоморфизма из k+1. Это утверждение можно немного усилить, сказав, что граф k-окрашиваемый тогда и только тогда, когда некоторая ориентация не содержит ориентированного пути длины k (не содержит k+1 в качестве подграфа). Это теорема Галлаи — Хассе — Роя — Витавера.

Примеры

Некоторые задачи планирования могут быть смоделированы как вопрос о поиске гомоморфизмов графа. Например, можно назначить учебные курсы в различные временные слоты в расписании, чтобы два курса, посещаемых одним и тем же студентом, не проводились слишком близко друг к другу по времени. Курсы образуют граф G, с ребром между любыми двумя курсами, которые посещают общие студенты. Временные слоты образуют граф H, с ребром между любыми двумя слотами, достаточно удаленными друг от друга по времени. Например, если требуется составить циклическое, еженедельное расписание, при котором у каждого студента занятия в мастерских проходят в не соседние дни, то H будет графом дополнения к C7. Гомоморфизм графа из G в H – это расписание, назначающее курсы временным слотам, как это определено. Чтобы добавить требование, например, чтобы ни один студент не имел занятий одновременно в пятницу и понедельник, достаточно удалить соответствующее ребро из H.

Простую задачу распределения частот можно сформулировать следующим образом: ряд передатчиков в беспроводной сети должны выбрать частотный канал для передачи данных. Чтобы избежать помех, передатчики, находящиеся в географической близости, должны использовать каналы с существенно различающимися частотами. Если это условие аппроксимировать одним порогом для определения понятий «географически близкий» и «далекий друг от друга», то допустимый выбор канала снова будет соответствовать гомоморфизму графа. Он должен отображать граф передатчиков G, с ребрами между географически близкими парами, в граф каналов H, с ребрами между каналами, частоты которых достаточно далеки друг от друга. Хотя эта модель довольно упрощена, она допускает некоторую гибкость: пары передатчиков, которые не находятся близко, но могут создавать помехи из-за географических особенностей, можно добавить к ребрам G. Пары, которые не обмениваются данными одновременно, можно из него удалить. Аналогично, пары каналов, которые достаточно далеки друг от друга, но подвержены гармоническим помехам, можно исключить из множества ребер H.

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

Формальный вид

Графы и ориентированные графы можно рассматривать как частный случай гораздо более общего понятия, называемого реляционными структурами (определяемыми как множество с набором отношений на нем). Ориентированные графы — это структуры с единственным бинарным отношением (смежностью) в области определения (множестве вершин). С этой точки зрения, гомоморфизмы таких структур являются, по сути, гомоморфизмами графов. В общем случае, вопрос о нахождении гомоморфизма из одной реляционной структуры в другую является задачей удовлетворения ограничениям (CSP). Рассмотрение графов дает конкретный первый шаг, который помогает понять более сложные задачи CSP. Многие алгоритмические методы поиска гомоморфизмов графов, такие как возвратный поиск, распространение ограничений и локальный поиск, применимы ко всем задачам CSP. Для графов G и H вопрос о том, существует ли гомоморфизм из G в H, соответствует экземпляру CSP с единственным типом ограничений, как описано ниже. Переменными являются вершины G, а область значений для каждой переменной — множество вершин H. Оценка — это функция, которая сопоставляет каждой переменной элемент из области значений, то есть функция f из V(G) в V(H). Каждое ребро или дуга (u, v) графа G соответствует ограничению ((u, v), E(H)). Это ограничение выражает, что оценка должна отображать дугу (u, v) в пару (f(u), f(v)), которая принадлежит отношению E(H), то есть является дугой в H. Решением CSP является оценка, удовлетворяющая всем ограничениям, и, следовательно, представляет собой гомоморфизм из G в H.

Комплексность вычислений

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

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

(Стипендии AMSI на летние исследования, отчет о студенческих исследованиях под руководством Брайана Дэйви и Джейн Питкетли, Университет Ла Троб).