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

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

Гомоморфизм цветочного снарка 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)$. Если существует какой-либо гомоморфизм из в H , то G называется гомоморфной H G или H -раскрашиваемой . Это часто обозначается как просто

Г → Ч .

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

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

Накрывающие карты представляют собой особый вид гомоморфизмов, которые отражают определение и многие свойства накрывающих карт в топологии . Они определяются как сюръективные гомоморфизмы (т. е. что-то отображается в каждую вершину), которые также являются локально биективными, то есть являются биекцией в окрестности каждой вершины. Примером может служить покрытие из графа путем разделения каждой вершины на v0 и _и v1 двойное _ребра замены u , v ребрами u0 _{, сформированное} , v1 _v0 и v _, u1 двудольное _{каждого} . Функция, отображающая 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 тривиально допускает гомоморфизм в G , K3 _откуда → G. следует Это также означает, что K ₃ является ядром любого такого графа G . Аналогично, каждый двудольный граф , имеющий хотя бы одно ребро, эквивалентен K ₂ .

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

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

Если существуют два гомоморфизма G → H и H → Kk _, то их композиция G → Kk _{также является} гомоморфизмом. Другими словами, если граф 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 ₀ или К ₁ ). Например, между любыми двумя ( кроме K0 _{графами} , K1 _{полными} , 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 Стипендии для проведения исследований на каникулах , отчет о студенческом исследовании под руководством Брайана Дэйви и Джейн Питкетли, Университет Ла Троб ).