Введение

Регулярный граф с длиной окружности, более чем в два раза превышающей его диаметр.

В теории графов, граф Мура — это регулярный граф, длина кратчайшего цикла (окружность) которого больше чем в два раза превышает его диаметр (расстояние между двумя наиболее удалёнными вершинами). Если степень такого графа равна d, а его диаметр — k, то его окружность должна быть равна 2k + 1. Это справедливо для графа степени d и диаметра k тогда и только тогда, когда число его вершин равно верхней границе максимально возможного числа вершин в любом графе с данной степенью и диаметром. Следовательно, эти графы решают проблему о степени и диаметре для своих параметров. Другое эквивалентное определение графа Мура G состоит в том, что он имеет окружность g = 2k + 1 и ровно циклов длины g, где n и m — соответственно, число вершин и рёбер G. Фактически, они являются экстремальными по отношению к числу циклов, длина которых равна окружности графа. Графы Мура названы в честь Эдварда Ф. Мура, который поставил задачу описания и классификации этих графов. Помимо того, что графы Мура имеют максимальное возможное число вершин для заданной комбинации степени и диаметра, они также имеют минимальное возможное число вершин для регулярного графа с заданной степенью и окружностью. То есть любой граф Мура является клеткой. Формула для числа вершин в графе Мура может быть обобщена, чтобы позволить определение графов Мура с чётной и нечётной окружностью, и в этом случае эти графы также являются клетками.

Ограничивающие вершины по градусу и диаметру

Пусть G – любой граф с максимальной степенью d и диаметром k, и рассмотрим дерево, построенное поиском в ширину, начиная с любой вершины v. Это дерево имеет 1 вершину на уровне 0 (саму v) и не более d вершин на уровне 1 (соседей v). На следующем уровне имеется не более d(d − 1) вершин: каждый сосед v использует одно из своих ребер для соединения с v и, таким образом, может иметь не более d − 1 соседей на уровне 2. В общем случае, аналогичный аргумент показывает, что на любом уровне 1 ≤ i ≤ k может быть не более d^(i-1) вершин. Таким образом, общее количество вершин может быть не более d^k - 1. Изначально граф Мура определялся как граф, для которого эта граница на количество вершин достигается точно. Следовательно, любой граф Мура имеет максимальное возможное количество вершин среди всех графов с максимальной степенью d и диаметром k. Позже было показано, что графы Мура можно эквивалентно определить как графы с диаметром k и длиной окружности 2k + 1; эти два требования в совокупности приводят к тому, что граф становится d-регулярным для некоторого d и удовлетворяет формуле подсчета вершин.

Графики Мура в виде клеток

Вместо того чтобы оценивать верхнюю границу числа вершин в графе через его максимальную степень и диаметр, мы можем, используя аналогичные методы, вычислить нижнюю границу числа вершин через его минимальную степень и длину окружности. Предположим, граф G имеет минимальную степень d и длину окружности 2k + 1. Выберем произвольно начальную вершину v и, как и прежде, рассмотрим дерево поиска в ширину с корнем в v. Это дерево должно содержать одну вершину на уровне 0 (саму v) и не менее d вершин на уровне 1. На уровне 2 (при k > 1) должно быть не менее d(d − 1) вершин, поскольку каждая вершина на уровне 1 имеет не менее d − 1 свободных смежностей для заполнения, и никакие две вершины на уровне 1 не могут быть смежны друг с другом или с общей вершиной на уровне 2, так как это привело бы к образованию цикла длиной меньше заданной длины окружности. В общем случае, аналогичный аргумент показывает, что на любом уровне 1 ≤ i ≤ k должно быть не менее вершин. Таким образом, общее число вершин должно быть не менее.

В графе Мура эта граница на число вершин достигается точно. Каждый граф Мура имеет длину окружности ровно 2k + 1: в нем недостаточно вершин для большей длины окружности, а более короткий цикл привел бы к тому, что в первых k уровнях какого-либо дерева поиска в ширину было бы слишком мало вершин. Следовательно, любой граф Мура имеет минимальное возможное число вершин среди всех графов с минимальной степенью d и длиной окружности 2k + 1: это клетка. Для четной длины окружности 2k можно аналогично построить дерево поиска в ширину, начиная с середины одного ребра. Полученная граница на минимальное число вершин в графе с такой длиной окружности и минимальной степенью d равна

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