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

Не путать с гомеоморфизмом графов .

Гомоморфизм цветочного снарка J ₅ в граф циклов C ₅ .
Это также ретракция на подграф по пяти центральным вершинам. Таким образом, J ₅ фактически гомоморфно эквивалентен с- ядру C ₅ .

В математической области теории графов гомоморфизм графов — это отображение между двумя графами , которое учитывает их структуру. Более конкретно, это функция между множествами вершин двух графов, которая отображает соседние вершины в соседние вершины.

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

Определения

В этой статье, если не указано иное, графы являются конечными, неориентированными графами с петлями разрешены, но кратные ребра (параллельные ребра) запрещены. графа Гомоморфизм f из графика $G=(V(G),E(G))$ к графику $H=(V(H),E(H))$, написано

ж : Г → Ч

это функция от $V(G)$ к $V(H)$ который сохраняет края. Формально, $(u,v)\in E(G)$ подразумевает $(f(u),f(v))\in E(H)$, для всех пар вершин $u,v$ в $V(G)$.Если существует какой-либо гомоморфизм из G в H , то G называется гомоморфной H - или H раскрашиваемой . Это часто обозначается как просто

Г → Ч .

Приведенное выше определение распространяется на ориентированные графы. Тогда для гомоморфизма f : G → H , ( f ( u ), f ( v )) является дугой (направленным ребром) H, если ( u , v ) является дугой G .

Существует инъективный гомоморфизм из G в H (т. е. тот, который отображает различные вершины в вершины в H ) тогда и только тогда, когда G изоморфен G подграфу в H различные .Если гомоморфизм f : G → H является биекцией и его обратная функция f ⁻¹ также является гомоморфизмом графов, то f является изоморфизмом графов.

Накрывающие карты представляют собой особый вид гомоморфизмов, которые отражают определение и многие свойства накрывающих карт в топологии . Они определяются как сюръективные гомоморфизмы (т. е. что-то отображается в каждую вершину), которые также являются локально биективными, то есть являются биекцией в окрестности каждой вершины.Примером является двойное покрытие , сформированное из графа путем разделения v на v0 _u1 и v1 _, замены u , v ребрами u0 _{двудольное} , v1 _и вершины v0 _{каждого} каждой и _ребра . Функция, отображающая v ₀ и v ₁ в накрытии в v в исходном графе, является гомоморфизмом и накрывающим отображением.

графов Гомеоморфизм — это другое понятие, не связанное напрямую с гомоморфизмами. Грубо говоря, он требует инъективности, но позволяет отображать ребра в пути (а не только в ребра). Миноры графов — еще более расслабленное понятие.

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

K ₇ , полный граф с 7 вершинами, является ядром.

Основная статья: Core (теория графов)

Два графа G и H , гомоморфно эквивалентны если грамм → ЧАС и ЧАС → грамм . Карты не обязательно являются сюръективными или инъективными. Например, полные двудольные графы K _2,2 и K _3,3 гомоморфно эквивалентны: каждое отображение можно определить как взятие левой (соответственно правой) половины графа области и отображение только одной вершины в левой (соответственно . справа) половина графика изображения.

Ретракция — это гомоморфизм r графа G в подграф H графа G такой, что ( v ) = v для каждой вершины v графа H. r подграф H называется ретрактом G . В этом случае

Ядро . — это граф, не имеющий гомоморфизма ни одному собственному подграфу Эквивалентно, ядро ​​можно определить как граф, который не сводится ни к одному подграфу. Каждый граф G гомоморфно эквивалентен единственному ядру (с точностью до изоморфизма), ядром G называемому . Примечательно, что это в целом неверно для бесконечных графов. Однако те же определения применимы к ориентированным графам, и ориентированный граф также эквивалентен уникальному ядру.Каждый граф и каждый ориентированный граф содержит свое ядро ​​в виде ретракта и индуцированного подграфа .

Например, все полные графы K _n и все нечетные циклы ( графы циклов нечетной длины) являются ядрами.Любой 3-раскрашиваемый граф G , содержащий треугольник (т. е. имеющий полный граф K ₃ в качестве подграфа), гомоморфно эквивалентен K ₃ . Это связано с тем, что, с одной стороны, 3-раскраска G — это то же самое, что гомоморфизм G → K ₃ , как объяснено ниже. С другой стороны, каждый подграф тривиально допускает гомоморфизм в G , откуда K3 _→ G G. следует Это также означает, что K ₃ является ядром любого такого графа G . Аналогично, каждый двудольный граф , имеющий хотя бы одно ребро, эквивалентен K ₂ .

Связь с раскрасками

k -раскраска так , для некоторого целого числа k — это назначение одного из k цветов каждой вершине графа G что концы каждого ребра приобретают разные цвета. - раскраски k графа G точности соответствуют гомоморфизмам G в полный граф Kk _. в Действительно, вершины K _k соответствуют k цветам, и два цвета смежны как вершины K _k тогда и только тогда, когда они различны. Следовательно, функция определяет гомоморфизм K _k тогда и только тогда, когда она отображает смежные вершины G в разные цвета (т. е. является k -раскраской). В частности, группа G является k -раскрашиваемой тогда и только тогда, когда она K _k -раскрашиваема.

существуют два гомоморфизма G → H и H → Kk _Kk , то их композиция G → также является _Если гомоморфизмом. Другими словами, если граф H можно раскрасить в k цветов и существует гомоморфизм из G в H , то G также может быть k -цветом. Следовательно, из G → H следует χ( G ) ⩽ χ( H ), где χ обозначает хроматическое число графа (наименьшее k , для которого он k -раскрашиваем).

Варианты

Общие гомоморфизмы также можно рассматривать как своего рода раскраску: если вершины фиксированного графа H являются доступными цветами , а ребра H описывают, какие цвета совместимы , то H -раскраска графа G — это присвоение цветов вершинам графа H. G так, чтобы соседние вершины имели совместимые цвета.Многие понятия раскраски графов вписываются в этот шаблон и могут быть выражены как гомоморфизмы графов в различные семейства графов. Круговые раскраски можно определить с помощью гомоморфизмов в круговые полные графы , уточняя обычное понятие раскрасок. Дробная и b -кратная раскраска может быть определена с помощью гомоморфизмов в графы Кнезера . T-раскраски соответствуют гомоморфизмам в некоторые бесконечные графы. Ориентированная раскраска ориентированного графа является гомоморфизмом любого ориентированного графа . L (2,1)-раскраска — это гомоморфизм в дополнение к графу путей , который является локально инъективным, то есть он должен быть инъективным в окрестности каждой вершины.

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

Основная статья: Теорема Галлаи – Хассе – Роя – Витавера

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

Фольклорная теорема утверждает, что для всех k ориентированный граф G имеет гомоморфизм T → _k тогда и только тогда, когда он не допускает гомоморфизма направленного пути P → _{k +1} . Здесь P → _n — ориентированный граф с вершинами 1, 2, …, n и ребрами от i до i + 1, для i = 1, 2, …, n − 1.Следовательно, граф является k -раскрашиваемым тогда и только тогда, когда он имеет ориентацию, не допускающую гомоморфизма из P → _{k +1} .Это утверждение можно немного усилить, сказав, что граф является k -раскрашиваемым тогда и только тогда, когда некоторая ориентация не содержит направленного пути длины k (нет P → _{k +1} в качестве подграфа). Это теорема Галлаи–Хассе–Роя–Витавера .

удовлетворения

Примеры

Граф H непоследовательных дней недели, изоморфный графу C дополнений 7 _и круговой клике K _7/2

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

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

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

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

Графы и ориентированные графы можно рассматривать как частный случай гораздо более общего понятия, называемого реляционными структурами (определяемыми как набор с кортежем отношений). Ориентированные графы — это структуры с одним бинарным отношением (смежностью) в области (множестве вершин). С этой точки зрения гомоморфизмы таких структур являются в точности гомоморфизмами графов.В общем, вопрос нахождения гомоморфизма одной реляционной структуры в другую представляет собой проблему удовлетворения ограничений (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 при гомоморфной эквивалентности равен [ G ].Класс эквивалентности также может быть представлен уникальным ядром в [ G ].Отношение → является частичным порядком в этих классах эквивалентности; он определяет частично упорядоченный набор .

Пусть G < H что существует гомоморфизм из G в H , но нет гомоморфизма из H в G. означает , Отношение → является плотным порядком , что означает, что для всех (неориентированных) графов G , H таких, что G < H , существует граф K такой, что G < K < H (это справедливо, за исключением тривиальных случаев G = K ₀ или К ₁ ). Например, между любыми двумя , K1 , _{графами (кроме K0} K2 ) _. существует бесконечно _{полными} много круговых полных графов , соответствующих рациональным числам между натуральными числами

Частное множество классов эквивалентности графов при гомоморфизмах представляет собой дистрибутивную решетку с соединением [ G ] и [ H ], определяемым как (класс эквивалентности) непересекающегося объединения [ G ∪ H ] и пересечения [ G ] и [ H ] определяется как тензорное произведение [ G × H ] (выбор графов G и H, представляющих классы эквивалентности [ G ] и [ H ] не имеет значения). Неприводимые к объединению элементы этой решетки представляют собой точно связные графы. Это можно показать, используя тот факт, что гомоморфизм отображает связный граф в один связный компонент целевого графа. Неприводимые мультипликативные элементы этой решетки — это в точности графы . Это графы K такие, что произведение G × H имеет гомоморфизм к K только тогда, когда один из G или H также гомоморфен. Идентификация мультипликативных графов лежит в основе гипотезы Хедетниеми .

Гомоморфизмы графов также образуют категорию , в которой графы являются объектами, а гомоморфизмы — стрелками. Начальный объект — это пустой граф, а конечный объект — это граф с одной вершиной и одним циклом в этой вершине.Тензорное произведение графов является теоретико-категорным произведением и экспоненциальный график является экспоненциальным объектом для этой категории. Поскольку эти две операции всегда определены, категория графов является декартовой замкнутой категорией .По той же причине решетка классов эквивалентности графов относительно гомоморфизмов фактически является алгеброй Гейтинга .

Для ориентированных графов применяются те же определения. В частности, → является частичным порядком на классах эквивалентности ориентированных графов. Он отличается от порядка → на классах эквивалентности неориентированных графов, но содержит его как подпорядок. Это связано с тем, что каждый неориентированный граф можно рассматривать как ориентированный граф, где каждая дуга ( u , v ) появляется вместе со своей обратной дугой ( v , u ), и это не меняет определения гомоморфизма. Порядок → для ориентированных графов снова представляет собой дистрибутивную решетку и алгебру Гейтинга с операциями соединения и встречи, определенными, как и раньше. Однако он не плотный. Существует также категория с ориентированными графами в качестве объектов и гомоморфизмами в виде стрелок, которая снова является декартовой замкнутой категорией .

Несравненные графики

Граф Грётча, несравнимый с K ₃

Существует множество несравнимых графов относительно предпорядка гомоморфизма, то есть пар графов, ни один из которых не допускает гомоморфизма в другой. Один из способов их построения — рассмотреть нечетный обхват графа G , длину его кратчайшего цикла нечетной длины.Нечетный обхват, эквивалентно, представляет собой наименьшее нечетное число g , для которого существует гомоморфизм графа цикла на g вершинах в G . По этой причине, если G → H , то нечетный обхват G больше или равен нечетному H. обхвату

С другой стороны, если G → H то хроматическое число G меньше или равно хроматическому числу H. , Следовательно, если G имеет строго больший нечетный обхват, чем H , и строго большее хроматическое число, чем H , то G и H несравнимы. Например, граф Греча 4-хроматический и не содержит треугольников (он имеет обхват 4 и нечетный обхват 5), поэтому он несравним с треугольным графом K ₃ .

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

Среди ориентированных графов гораздо легче найти несравнимые пары. Например, рассмотрим ориентированные графы циклов C → _n с вершинами 1, 2, …, n и ребрами от i до i + 1 (для i = 1, 2, …, n − 1) и от n до 1.Существует гомоморфизм из C → _n в C → _k ( n , k ≥ 3) тогда и только тогда, когда n кратно k . В частности, все ориентированные графы циклов C → _n с n простыми числами несравнимы.

Вычислительная сложность

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

Гомоморфизмы фиксированного графа

Проблема гомоморфизма с фиксированным графом H в правой части каждого экземпляра также называется проблемой H -раскраски. Когда H — полный граф K _k , это графа проблема k -раскраски , которая разрешима за полиномиальное время для k = 0, 1, 2 и NP-полна в противном случае. В частности, K ₂ -раскрашиваемость графа G эквивалентна тому, что G является двудольным , что можно проверить за линейное время.В более общем смысле, когда H является двудольным графом, H -раскраска эквивалентна K ₂ -раскраске (или K ₀ / K ₁ -раскраске, когда H пуст/без ребер), поэтому решение одинаково легко принять. Павол Хелл и Ярослав Нешетржил доказали, что для неориентированных графов ни один другой случай неразрешим:

Теорема Хелла – Нешетрила (1990): проблема H -раскраски возникает в P, когда H двудольна, и NP-полна в противном случае.

Это также известно как теорема дихотомии для (неориентированных) гомоморфизмов графов, поскольку она делит задачи H -раскраски на NP-полные или P-задачи без промежуточных случаев.Для ориентированных графов ситуация более сложная и фактически эквивалентна гораздо более общему вопросу характеристики сложности задач удовлетворения ограничений . Оказывается, что задачи H -раскраски ориентированных графов столь же общие и разнообразные, как и задачи CSP с любыми другими видами ограничений. Формально (конечный) язык ограничений (или шаблон ) Γ представляет собой конечную область и конечное множество отношений над этой областью. CSP( Γ ) — это проблема удовлетворения ограничений, где экземплярам разрешено использовать ограничения только в Γ .

Теорема (Федер, Варди, 1998): Для каждого языка ограничений Γ проблема CSP( Γ ) эквивалентна при полиномиальном сокращении времени некоторой задаче H -раскраски для некоторого ориентированного графа H .

Интуитивно это означает, что любой алгоритмический метод или результат сложности, применимый к задачам H -раскраски для ориентированных графов H, также применим и к общим CSP. В частности, можно задаться вопросом, можно ли распространить теорему Хелла–Нешетрила на ориентированные графы. По приведенной выше теореме это эквивалентно гипотезе Федера-Варди (также известной как гипотеза CSP, гипотеза дихотомии) о дихотомии CSP, которая утверждает, что для каждого языка ограничений Γ CSP( Γ ) является NP-полным или в P. Эта гипотеза была доказана в 2017 году независимо Дмитрием Жуком и Андреем Булатовым, что привело к следующему следствию:

Следствие (Булатов 2017; Жук 2017): Задача H -раскраски ориентированных графов при фиксированном H является либо P-, либо NP-полной.

семейства

Проблема гомоморфизма с единственным фиксированным графом G в левой части входных экземпляров может быть решена методом перебора за время | В ( Ч ) | ^{O(| V ( G )|)} , поэтому полиномиален по размеру входного графа H . Другими словами, проблема тривиально решается в P для графов G ограниченного размера. Тогда возникает интересный вопрос: какие еще свойства G , помимо размера, делают возможными полиномиальные алгоритмы?

Важнейшим свойством оказывается ширина дерева , мера того, насколько древовидным является граф. Для графа G древовидной ширины не более k и графа H проблема гомоморфизма может быть решена за время | В ( Ч ) | ^{Хорошо ​ )} со стандартным подходом динамического программирования . На самом деле достаточно предположить, что ядро ​​группы G имеет ширину дерева не более k . Это справедливо, даже если ядро ​​неизвестно.

Показатель в | В ( Ч ) | ^{Хорошо ​ )} -время алгоритма не может быть существенно уменьшено: нет алгоритма с временем работы | В ( Ч ) | ^{o(tw( G ) /log tw( G ))} существует, предполагая гипотезу экспоненциального времени (ETH), даже если входные данные ограничены любым классом графов неограниченной ширины дерева. ETH — это недоказанное предположение, похожее на P ≠ NP , но более сильное.При том же предположении практически отсутствуют другие свойства, которые можно использовать для получения алгоритмов с полиномиальным временем. Это формализуется следующим образом:

Теорема ( Гроэ ): Для вычислимого класса графов ${\mathcal {G}}$, проблема гомоморфизма для примеров $(G,H)$ с $G\in {\mathcal {G}}$ находится в P тогда и только тогда, когда графы в ${\mathcal {G}}$ имеют ядра ограниченной ширины дерева (при условии, что ETH).

разрешима ли проблема хотя бы за время, сколь угодно сильно зависящее от G , но с фиксированной полиномиальной зависимостью от размера H. Можно задаться вопросом , Ответ снова будет положительным, если мы ограничим G классом графов с ядрами ограниченной ширины дерева, и отрицательным для любого другого класса. На языке параметризованной сложности это формально означает, что проблема гомоморфизма в ${\mathcal {G}}$ параметризованный размером (количеством ребер) G, демонстрирует дихотомию. Это можно сделать с фиксированными параметрами, если графики в ${\mathcal {G}}$ имеют ядра ограниченной древовидной ширины и W[1] -полны в противном случае.

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

См. также

• Глоссарий терминов теории графов
• Гомоморфизм для одного и того же понятия в разных алгебраических структурах.
• Переписывание графа
• Медианные графики , определяемые как ретракты гиперкубов.
• Гипотеза Сидоренко

Ссылки

Общие книги и экспозиции

• Кэмерон, Питер (2006), Гомоморфизмы графов, Заметки группы по изучению комбинаторики (PDF)
• Черт, Павол ; Нешетржил, Ярослав (2004), Графы и гомоморфизмы , Оксфордская серия лекций по математике и ее приложениям, том. 28, Издательство Оксфордского университета, ISBN  0-19-852817-5
• Хан, Геня; Тардиф, Клод (1997), «Гомоморфизмы графов: структура и симметрия», Симметрия графов: алгебраические методы и приложения (PDF) , Springer, стр. 107–166, doi : 10.1007/978-94-015-8937-6_4
• Годсил, Крис ; Ройл, Гордон (2001), «6. Гомоморфизмы», Алгебраическая теория графов , Тексты для выпускников по математике, том. 207, Спрингер – Верлаг, Нью-Йорк, номер домена : 10.1007/978-1-4613-0163-9 , ISBN.  978-1-4613-0163-9 , S2CID   9661174
• Ловас, Ласло (2012). Большие сети и ограничения графов (PDF) . Провиденс, Род-Айленд: Американское математическое общество. ISBN  0-8218-9085-9 .

В удовлетворении ограничений

• Бодирский, Мануэль (2007), Гомоморфизмы графов и универсальная алгебра, конспекты курса (PDF)
• Черт, Павол ; Нешетржил, Ярослав (2008), «Раскраска, удовлетворение ограничений и сложность» (PDF) , Computer Science Review , 2 (3): 143–163, doi : 10.1016/j.cosrev.2008.10.003

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

• Браун, Рональд; Моррис, Ифор; Шримптон, Джон; Уэнсли, Кристофер Д. (2008), «Графики морфизмов графов» , Электронный журнал комбинаторики , 15 (1): A1, doi : 10.37236/919
• Грей, Чарльз Т. (2014), The Digraph Lattice (PDF) ( AMSI Стипендии для проведения исследований на каникулах , отчет о студенческом исследовании под руководством Брайана Дэйви и Джейн Питкетли, Университет Ла Троб ).