Граф Мура: различия между версиями

'''Граф Мура''' — [[регулярный граф]] [[Степень вершины (теория графов)|степени]] ''<math>d''</math> и [[Расстояние (теория графов)|диаметром]] ''<math>k''</math>, число вершин которого равно верхней границе

Эквивалентное определение графа Мура — это граф диаметра ''<math>k''</math> с [[Обхват (теория графов)|обхватом]] 2''k'' <math>2k+ 1</math>. Ещё одно эквивалентное определение графа Мура ''<math>G''</math> — это граф с обхватом ''<math>g = 2k+1''</math>, имеющий в точности <math> \frac{n}{g}(m-n+1) </math> циклов длины <math>g</math>''g,'' где <math>n</math>''n, m'' <math>m</math> — число вершин и рёбер графа <math>G</math>''G.'' Графы, фактически, экстремальны по отношению к числу циклов, длина которых равна обхвату графа{{sfn|Azarija, Klavžar|2015}}.

[[Файл:Petersen-as-Moore.svg|thumb| [[Граф Петерсена]] как граф Мура. Любое дерево [[Поиск в ширину|поиска в ширину]] имеет ''<math>d''(''d''-1)<sup>''^i''</supmath> вершин в его ''i''-ом уровне.]]

Пусть ''<math>G''</math> — любой граф с максимальной степенью ''<math>d''</math> и диаметром ''<math>k''</math>, и возьмём дерево, образованное [[Поиск в ширину|поиском в ширину]], с корнем в вершине ''<math>v''</math>. Это дерево имеет 1 вершину уровня 0 (сама вершина ''<math>v''</math>), и максимум ''<math>d''</math> вершин уровня 1
(соседи вершины ''<math>v''</math>). На следующем уровне имеется максимум ''<math>d''(''d''-1)</math> вершин — каждый сосед вершины ''<math>v''</math> использует одно ребро для соединения с вершиной ''<math>v''</math>, так что имеет максимум ''<math>d''-1</math> соседей уровня 2. В общем случае подобные доводы показывают, что на любом уровне <math>1 ≤ ''\leq{i'' ≤ ''}\leq{k''}</math> может быть максимум ''<math>d''(''d''-1)<sup>''^i''</supmath> вершин. Таким образом, общее число вершин может быть не больше

Хоффман и Синглтон{{sfn|Hoffman, Singleton|1960}} первоначально определили граф Мура как граф, для которого эта граница числа вершин достигается. Таким образом, любой граф Мура имеет максимально возможное число вершин среди всех графов, в которых степень не превосходит ''<math>d''</math>, диаметр — ''<math>k''</math>.

Позднее Синглтон{{sfn|Singleton|1968}} показал, что графы Мура можно эквивалентно определить как граф, имеющий диаметр ''<math>k''</math> и обхват 2''k''+<math>2k-1</math>. Эти два требования комбинируются, из чего выводится ''d''-регулярность графа для некоторого ''<math>d''</math>.

Вместо верхней границы числа вершин в графе в терминах его максимальной степени и диаметра мы можем использовать нижнюю границу числа вершин в терминах минимальной степени и [[Обхват (теория графов)|обхвата]] {{sfn|Erdős, Rényi, Sós|1966}}. Предположим, что граф ''<math>G''</math> имеет минимальную степень ''<math>d''</math> и обхват 2''k''<math>2k+1</math>. Выберем произвольную начальную вершину ''<math>v''</math> и, как и прежде, представим дерево поиска в ширину с корнем в ''<math>v''</math>. Это дерево должно иметь одну вершину уровня 0 (сама вершина ''<math>v''</math>) и по меньшей мере ''<math>d''</math> вершин на уровне 1. На уровне 2 (для ''<math>k'' > 1</math>), должно быть по меньшей мере ''<math>d''(''d''-1)</math> вершин, поскольку каждая вершина на уровне <math>l</math> имеет по меньшей мере ''<math>d''-1</math> оставшихся связей, и никакие две вершины уровня 1 не могут быть смежными или иметь общие вершины уровня 2, поскольку создался бы цикл, более короткий, чем обхват. В общем случае похожие доводы показывают, что на любом уровне <math>1 ≤ ''\leq{i'' ≤ ''}\leq{k''}</math> должно быть по меньшей мере ''<math>d''(''d''-1)<sup>''^i''</supmath> вершин. Таким образом, общее число вершин должно быть не менее

В графе Мура это число вершин достигается. Каждый граф Мура имеет обхват в точности 2''k''<math>2k+1</math> — он не имеет достаточно вершин, чтобы иметь больший обхват, а более короткий цикл привёл бы к недостатку вершин в первых ''<math>k''</math> уровнях некоторых деревьев поиска в ширину.

Таким образом, любой граф Мура имеет минимально возможное число вершин среди всех графов с минимальной степенью ''<math>d''</math> и диаметром ''<math>k''</math> — он является [[Клетка (теория графов)|клеткой ]].

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

* [[Полный граф|Полные графы]] <math> K_n </math> с n > 2 вершинами. (диаметр 1, обхват 3, степень n-1, порядок <math>n</math>)

* Нечётные [[Граф-цикл|циклы]] <math> C_{2n+1} </math>. (диаметр <math>n</math>, обхват <math>2n+1</math>, степень 2, порядок 2n+1)

В обобщённом определении графов Мура, где разрешается чётный обхват, графы с чётным обхватом соответствуют графам инцидентности (возможно вырожденных) {{не переведено 5|Обобщённый многоугольник|обобщённых многоугольников||Generalized polygon}}. Несколько примеров — чётные циклы <math> C_{2n} </math>, [[Полный двудольный граф|полные двудольные графы]] <math> K_{n,n} </math> с обхватом четыре, [[граф Хивуда]] со степенью 3 и обхватом 6 и [[граф Татта — Коксетера]] со степенью 3 и обхватом 8. Известно{{sfn|Bannai, Ito|1973}}{{sfn|Damerell|1973}}), что все графы Мура, кроме перечисленных выше, должны иметь обхват 5, 6, 8 или 12. Случай чётного обхвата следует из теоремы Фейта-Хигмана о возможных значениях <math>n</math> для обобщённых n-угольников.