Гомоморфизм графов: различия между версиями
| [непроверенная версия] | [непроверенная версия] |
Содержимое удалено Содержимое добавлено
орфография |
|||
Строка 2:
'''Гомоморфизм графов''' — это отображение между двумя [[Граф (математика)|графами]], не нарушающее структуру. Более конкретно, это отображение между набором вершин двух графов, которое отображает смежные [[Вершина (теория графов)|вершины]] в смежные.
Гомоморфизмы обобщают различные понятия [[Раскраска графов|раскрасок графов]] и
Факт, что гомоморфизмы могут быть использованы последовательно, приводит к богатым алгебраическим структурам — [[Предпорядок|предпорядку]] на графах, {{не переведено 5|Дистрибутивная решётка|дистрибутивной решётке||distributive lattice}} и [[Категория (математика)|категориям]] (одна для неориентированных графов и одна для ориентированных графов){{sfn|Hell, Nešetřil|2004|с=109}}.
[[Вычислительная сложность]] поиска гомоморфизма между заданными графами в общем случае запредельная, но известно много частных случаев, когда задача выполнима за [[Временная сложность|полиномиальное время]]. Границы между решаемыми и непреодолимыми случаями находятся в области активных исследований{{sfn|Hell, Nešetřil|2008}}.
Строка 21:
[[накрывающий граф|Накрывающие отображения]] являются частым видом гомоморфизмов, который отражает определение и многие свойства [[Накрытие|накрытия в топологии]]{{sfn|Godsil, Royle|2001|с=115}}.
Они определяются как [[Сюръекция|сюръективные]] гомоморфизмы, которые локально биективны, то есть является биекцией в [[Окрестность (теория графов)|окрестности]] каждой вершины.
Примером служит [[двойное покрытие двудольным графом]], образованное из графа путём разбиения каждой вершины ''v'' на <math>v_0</math> и <math>v_1</math> и заменой каждого ребра ''u'',''v'' на два ребра <math>u_0,v_1</math> и <math>v_0,u_1</math>. Функция, отображающая ''v<sub>0</sub>'' и ''v<sub>1</sub>'' в ''v'' исходного графа, является гомоморфизмом и
[[Гомеоморфизм графов|Гомеоморфизм]] графа является отдельным понятием, не связанным прямо с гомоморфизмами. Грубо говоря, он требует инъективности, но позволяет отображение ребер в пути (а не просто в рёбра). [[Минор графа|Миноры графа]] остаются более слабым понятием.
Строка 45:
[[Раскраска графов|''k''-Раскраска]] для некоторого целого ''k'' — это назначение одного из ''k'' цветов каждой вершине графа ''G'' так, что конечные вершины каждого ребра имеют различные цвета. ''k''-Раскраски графа ''G'' соответствуют в точности гомоморфизмам из ''G'' в [[полный граф]] ''K''<sub>''k''</sub>{{sfn|Cameron|2006|с=1}}{{sfn|Hell, Nešetřil|2004|loc=Proposition 1.7}}. Более того, вершины графа ''K''<sub>''k''</sub> соответствуют ''k'' цветам и два цвета смежны как вершины графа ''K''<sub>''k''</sub> тогда и только тогда, когда они различны. Следовательно, функция определяет гомоморфизм в ''K''<sub>''k''</sub> тогда и только тогда, когда смежные вершины графа ''G'' выкрашены в разные цвета. В частности, граф ''G'' ''k''-раскрашиваем тогда и только тогда, когда ''K''<sub>''k''</sub>-раскрашиваем{{sfn|Cameron|2006|с=1}}{{sfn|Hell, Nešetřil|2004|loc=Proposition 1.7}}.
Если есть два гомоморфизма <math>G \to H</math> и <math>H \to K_k</math>, то их суперпозиция <math>G \to K_k</math> является также
=== Варианты ===
Строка 53:
[[Дробная раскраска|Дробная]] и [[Дробная раскраска#Определения|''b''-кратная раскраска]] могут быть определены с помощью гомоморфизмов в [[Кнезеровский граф|кнезеровские графы]]{{sfn|Hell, Nešetřil|2004|loc=§6.2}}{{sfn|Geňa, Tardif|1997|loc=§4.5}}
[[T-раскраска|T-раскраски]] соответствуют гомоморфизмам в некоторые бесконечные графы{{sfn|Hell, Nešetřil|2004|loc=§6.3}}.
{{не переведено 5|L(2,1)-раскраска|||L(2,1)-coloring}} — это локально инъективный гомоморфизм в [[Дополнение графа|дополнение]] [[Путь (теория графов)|пути]], что означает, что он должен быть инъективным в окрестности каждой вершины{{r|Fiala02}}.
Строка 77:
Некоторые задачи расписаний можно промоделировать как вопрос о нахождении гомоморфизмов графа{{sfn|Cameron|2006|с=1}}{{sfn|Hell, Nešetřil|2004|loc=§1.8}}. Как пример, можно попробовать назначить практические занятия так, чтобы два курса, посещаемые тем же студентом, не были по времени слишком близки. Курсы образуют граф ''G'', с рёбрами между двумя курсами, если их посещает один и тот же студент. Возможное время проведения курсов образует граф ''H'' с рёбрами между двумя временны́ми окнами, если расстояние по времени между ними достаточно велико. Например, если хотят иметь циклическое еженедельное расписание, такое, что каждый студент приходит на практические занятия через день, то граф ''H'' был бы [[Дополнение графа|дополнением графа]] ''C''<sub>7</sub>. Гомоморфизм графа из ''G'' в ''H'' является тогда назначением курсов по временным окнам{{sfn|Cameron|2006|с=1}}. Чтобы добавить требование, скажем, чтобы никакой студент не имел занятия как в пятницу, так и в понедельник, достаточно удалить одно ребро из графа ''H''.
Простая задача {{не переведено 5|Выделение частор|распределения частот||frequency allocation}} может быть поставлена следующим образом. Имеется несколько передатчиков [[Беспроводная вычислительная сеть|беспроводной сети]]. Нужно выбрать на каждом из них частотный канал, по которому он будет передавать данные. Чтобы избежать [[Электромагнитная помеха|помех]], географически близкие передатчики должны иметь каналы с достаточно отличающимися частотами. Если это условие ограничено простым порогом для понятия «географически близки» и «
В каждом случае эти упрощённые модели показывают много особенностей, которые следует отрабатывать на практике{{sfn|Hell, Nešetřil|2004|с=31–32}}. [[Удовлетворение ограничений|Задачи удовлетворения ограничений]], которые обобщают задачи гомоморфизма графа, могут выражать дополнительные типы условий (такие как индивидуальные предпочтения или ограничения на число совпадающих назначений). Это позволяет сделать модели более реалистичными и практичными.
=== Формальная точка зрения ===
В общем случае вопрос поиска гомоморфизма из одной структуры в другую является [[Удовлетворение ограничений|задачей удовлетворения ограничений]] ({{lang-en|constraint satisfaction problem}}, CSP).
Случай графов даёт конкретный первый шаг, который помогает понять более сложные задачи удовлетворения ограничений.
Строка 124:
Примерами графов с произвольно большими значениями нечётного обхвата и хроматического числа являются [[Кнезеровский граф|кнезеровские графы]]{{sfn|Geňa, Tardif|1997|loc=Proposition 3.14}} и [[Мычельскиан#Конус над графами|обобщённые мычельскианы]]{{sfn|Gyárfás, Jensen, Stiebitz|2004|с=1–14}}.
Последовательность таких графов с одновременным увеличением значений обоих параметров даёт бесконечное число несравнимых графов ([[антицепь]] в предпорядке гомоморфизмов){{sfn|Hell, Nešetřil|2004|loc=Proposition 3.4}}.
Другие свойства, такие как [[Плотный порядок|плотность]]
Построения графов с большими значениями хроматического числа и обхвата, а не просто нечётного обхвата, также возможны, но более сложны (см. [[Обхват (теория графов)#Обхват и раскраска графов|Обхват и раскраска графов]]).
Строка 147:
: '''Теорема''' (Федер, [[Варди, Моше|Варди]] 1998): Для любого языка ограничений ''Γ'' задача CSP(''Γ'') эквивалентна после [[Полиномиальная сводимость|полиномиального сведения]] некоторой задаче ''H''-раскраски для некоторого ориентированного графа ''H''{{sfn|Feder, Vardi|1998|с=57–104}}.
Интуитивно это означает, что любая алгоритмическая техника или результат о сложности, применимые к задачам ''H''-
=== Гомоморфизмы из фиксированного семейства графов ===
| |||