Граф Мура

Шаблон:Unsolved Граф Мура — регулярный граф степени $d$ и диаметром $k$, число вершин которого равно верхней границе

$1+d\sum _{i=0}^{k-1}(d-1{)}^i.$

Эквивалентное определение графа Мура — это граф диаметра $k$ с обхватом $2k+1$. Ещё одно эквивалентное определение графа Мура $G$ — это граф с обхватом $g=2k+1$, имеющий в точности $\frac{n}{g}(m-n+1)$ циклов длины $g$, где $n$, $m$ — число вершин и рёбер графа $G$. Графы, фактически, экстремальны по отношению к числу циклов, длина которых равна обхвату графаШаблон:Sfn.

Графы названы Аланом Хоффманом и Робертом СинглтономШаблон:Sfn именем Эдварда Мура, который поставил вопрос описания и классификации таких графов.

Имея максимально возможное число вершин для заданной комбинации степени и диаметра, графы Мура имеют минимально возможное число вершин для регулярных графов с заданной степенью и обхватом. Таким образом, любой граф Мура является клеткойШаблон:Sfn. Формула для числа вершин графа Мура может быть обобщена для возможности определения графов Мура с чётным обхватом, и эти графы снова являются клетками.

Границы числа вершин по степени и диаметру

Граф Петерсена как граф Мура. Любое дерево поиска в ширину имеет $d(d-1{)}^i$ вершин в его i-ом уровне.

Пусть $G$ — любой граф с максимальной степенью $d$ и диаметром $k$, тогда возьмём дерево, образованное поиском в ширину, с корнем в вершине $v$. Это дерево имеет 1 вершину уровня 0 (сама вершина $v$), и максимум $d$ вершин уровня 1 (соседи вершины $v$). На следующем уровне имеется максимум $d(d-1)$ вершин — каждый сосед вершины $v$ использует одно ребро для соединения с вершиной $v$, так что имеет максимум $d-1$ соседей уровня 2. В общем случае подобные доводы показывают, что на любом уровне $1\le i\le k$ может быть не больше $d(d-1{)}^i$ вершин. Таким образом, общее число вершин может быть не больше

$1+d\sum _{i=0}^{k-1}(d-1{)}^i.$

Хоффман и СинглтонШаблон:Sfn первоначально определили граф Мура как граф, для которого эта граница числа вершин достигается. Таким образом, любой граф Мура имеет максимально возможное число вершин среди всех графов, в которых степень не превосходит $d$, диаметр — $k$.

Позднее СинглтонШаблон:Sfn показал, что графы Мура можно эквивалентно определить как граф, имеющий диаметр $k$ и обхват $2k-1$. Эти два требования комбинируются, из чего выводится d-регулярность графа для некоторого $d$.

Графы Мура в качестве клеток

Вместо верхней границы числа вершин в графе в терминах его максимальной степени и диаметра мы можем использовать нижнюю границу числа вершин в терминах минимальной степени и обхвата Шаблон:Sfn. Предположим, что граф $G$ имеет минимальную степень $d$ и обхват $2k+1$. Выберем произвольную начальную вершину $v$ и, как и прежде, представим дерево поиска в ширину с корнем в $v$. Это дерево должно иметь одну вершину уровня 0 (сама вершина $v$) и по меньшей мере $d$ вершин на уровне 1. На уровне 2 (для $k>1$), должно быть по меньшей мере $d(d-1)$ вершин, поскольку каждая вершина на уровне $l$ имеет по меньшей мере $d-1$ оставшихся связей, и никакие две вершины уровня 1 не могут быть смежными или иметь общие вершины уровня 2, поскольку создался бы цикл, более короткий, чем обхват. В общем случае похожие доводы показывают, что на любом уровне $1\le i\le k$ должно быть по меньшей мере $d(d-1{)}^i$ вершин. Таким образом, общее число вершин должно быть не менее

$1+d\sum _{i=0}^{k-1}(d-1{)}^i.$

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

Для чётного обхвата $2k$ можно образовать аналогичное дерево поиска в ширину, начиная с середины одного ребра. Получаем границу минимального числа вершин в графе этого обхвата с минимальной степенью $d$

$2\sum _{i=0}^{k-1}(d-1{)}^i=1+(d-1{)}^{k-1}+d\sum _{i=0}^{k-2}(d-1{)}^i.$

Таким образом, в графы Мура иногда включаются графы, на которых данная граница достигается. Снова любой такой граф является клеткой.

Примеры

Теорема Хоффмана — Синглтона утверждает, что любой граф Мура с обхватом 5 должен иметь степень 2, 3, 7 или 57. Графами Мура являются:

• Полные графы $K_n$ с n > 2 вершинами. (диаметр 1, обхват 3, степень n-1, порядок $n$)
• Нечётные циклы $C_{2n+1}$. (диаметр $n$, обхват $2n+1$, степень 2, порядок 2n+1)
• Граф Петерсена. (диаметр 2, обхват 5, степень 3, порядок 10)
• Граф Хоффмана — Синглтона. (диаметр 2, обхват 5, степень 7, порядок 50)
• Гипотетический граф с диаметром 2, обхватом 5, степенью 57 и порядком 3250, в настоящее время неизвестно, существует ли такой.

Хигман показал, что, в отличие от других графов Мура, неизвестный граф не может быть вершинно-транзитивным. Мачай и Ширан позднее показали, что порядок автоморфизмов такого графа не превосходит 375.

В обобщённом определении графов Мура, где разрешается чётный обхват, графы с чётным обхватом соответствуют графам инцидентности (возможно вырожденных) обобщённых многоугольников. Несколько примеров — чётные циклы $C_{2n}$, полные двудольные графы $K_{n,n}$ с обхватом четыре, граф Хивуда со степенью 3 и обхватом 6 и граф Татта — Коксетера со степенью 3 и обхватом 8. ИзвестноШаблон:SfnШаблон:Sfn), что все графы Мура, кроме перечисленных выше, должны иметь обхват 5, 6, 8 или 12. Случай чётного обхвата следует из теоремы Фейта-Хигмана о возможных значениях $n$ для обобщённых n-угольников.

См. также

• Проблема размера — диаметра
• Шаблон:Не переведено 5

Литература

• Шаблон:Статья
• Шаблон:Книга.
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья.
• Шаблон:Статья
• Шаблон:Статья.
• Шаблон:Статья

Ссылки

• Brouwer and Haemers: Spectra of graphs Шаблон:Wayback
• Шаблон:MathWorld
• Шаблон:MathWorld