В теории графов граф Мура — это регулярный граф , обхват которого (кратчайшая длина цикла ) более чем в два раза превышает его диаметр (расстояние между двумя самыми дальними вершинами ). Если степень такого графа равна d , а его диаметр равен k , его обхват должен быть равен 2k + 1. Это верно для графа степени d и диаметра k , если и только если его число вершин равно
верхняя граница наибольшего возможного числа вершин в любом графе с этой степенью и диаметром. Следовательно, эти графы решают проблему степени-диаметра для своих параметров.
Другое эквивалентное определение графа Мура G состоит в том, что он имеет обхват g = 2k + 1 и ровно н/г ( m – n + 1) циклов длины g , где n и m – соответственно числа вершин и ребер графа G . Они фактически экстремальны по отношению к числу циклов, длина которых равна обхвату графа. [1]
Графы Мура были названы Хоффманом и Синглтоном (1960) в честь Эдварда Ф. Мура , который поставил вопрос об описании и классификации этих графов.
Помимо максимально возможного числа вершин для заданной комбинации степени и диаметра, графы Мура имеют минимально возможное число вершин для обычного графа с заданной степенью и обхватом. То есть любой граф Мура является клеткой . [ 2] Формула для числа вершин в графе Мура может быть обобщена, чтобы позволить определить графы Мура как с четным, так и с нечетным обхватом, и снова эти графы являются клетками.
Пусть G — любой граф с максимальной степенью d и диаметром k , и рассмотрим дерево, образованное поиском в ширину, начинающимся с любой вершины v . Это дерево имеет 1 вершину на уровне 0 ( сама v ) и не более d вершин на уровне 1 (соседи v ). На следующем уровне имеется не более d ( d − 1) вершин: каждый сосед v использует одну из своих смежностей для соединения с v и, таким образом, может иметь не более d − 1 соседей на уровне 2. В общем, аналогичное рассуждение показывает, что на любом уровне 1 ≤ i ≤ k может быть не более d ( d − 1) i −1 вершин. Таким образом, общее число вершин может быть не более
Хоффман и Синглтон (1960) изначально определили граф Мура как граф, для которого эта граница числа вершин выполняется точно. Таким образом, любой граф Мура имеет максимально возможное число вершин среди всех графов с максимальной степенью d и диаметром k .
Позднее Синглтон (1968) показал, что графы Мура можно эквивалентно определить как имеющие диаметр k и обхват 2k + 1 ; эти два требования объединяются, чтобы заставить граф быть d -регулярным для некоторого d и удовлетворять формуле подсчета вершин.
Вместо верхней границы числа вершин в графе с точки зрения его максимальной степени и диаметра, мы можем вычислить с помощью аналогичных методов нижнюю границу числа вершин с точки зрения его минимальной степени и его обхвата. [2] Предположим, что G имеет минимальную степень d и обхват 2k + 1. Выберем произвольно начальную вершину v и , как и прежде, рассмотрим дерево поиска в ширину с корнем в v . Это дерево должно иметь одну вершину на уровне 0 ( сама v ) и не менее d вершин на уровне 1. На уровне 2 (для k > 1 ) должно быть не менее d ( d − 1) вершин, поскольку каждая вершина на уровне 1 имеет не менее d − 1 оставшихся смежностей для заполнения, и никакие две вершины на уровне 1 не могут быть смежными друг с другом или с общей вершиной на уровне 2, поскольку это создало бы цикл короче предполагаемого обхвата. В общем, аналогичное рассуждение показывает, что на любом уровне 1 ≤ i ≤ k должно быть не менее d ( d − 1) i вершин. Таким образом, общее число вершин должно быть не менее
В графе Мура эта граница на количество вершин выполняется точно. Каждый граф Мура имеет обхват ровно 2k + 1 : у него недостаточно вершин, чтобы иметь больший обхват, а более короткий цикл привел бы к тому, что на первых k уровнях некоторого дерева поиска в ширину будет слишком мало вершин. Таким образом, любой граф Мура имеет минимально возможное количество вершин среди всех графов с минимальной степенью d и обхватом 2k + 1 : это клетка.
Для четного обхвата 2 k можно аналогичным образом сформировать дерево поиска в ширину, начинающееся с середины одного ребра. Результирующая граница минимального числа вершин в графе этого обхвата с минимальной степенью d равна
(Вместо этого правая часть формулы подсчитывает количество вершин в дереве поиска в ширину, начиная с одной вершины, учитывая возможность того, что вершина на последнем уровне дерева может быть смежной с d вершинами на предыдущем уровне.) Таким образом, графы Мура иногда определяются как включающие графы, которые точно соответствуют этой границе. Опять же, любой такой граф должен быть клеткой.
Теорема Хоффмана–Синглтона утверждает, что любой граф Мура с обхватом 5 должен иметь степень 2, 3, 7 или 57. Графы Мура: [3]
Хотя все известные графы Мура являются вершинно-транзитивными графами , неизвестный граф (если он существует) не может быть вершинно-транзитивным, поскольку его группа автоморфизмов может иметь порядок не более 375, что меньше числа его вершин. [5]
Если используется обобщенное определение графов Мура, которое допускает графы с четным обхватом, то графы Мура с четным обхватом соответствуют графам инцидентности (возможно вырожденных) обобщенных многоугольников . Некоторые примеры — четные циклы C 2 n , полные двудольные графы K n , n с обхватом четыре, граф Хивуда со степенью 3 и обхватом 6 и граф Тутта–Коксетера со степенью 3 и обхватом 8. В более общем смысле известно, что, за исключением графов, перечисленных выше, все графы Мура должны иметь обхват 5, 6, 8 или 12. [6] Случай с четным обхватом также следует из теоремы Фейта-Хигмана о возможных значениях n для обобщенного n -угольника.
