Граф Мура

В теории графов , А граф Мур является регулярным графом по степени г и диаметром к которой число вершин равна верхней грани

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

Эквивалентное определение графа Мура состоит в том, что это граф диаметра с обхватом . Другое эквивалентное определение графа Мура состоит в том, что он имеет обхват и точно циклы длины , где и - соответственно числа вершин и ребер графа . На самом деле они экстремальны по количеству циклов, длина которых равна обхвату графа. ^[1]${\ displaystyle k}$ ${\ displaystyle 2k + 1}$${\ displaystyle G}$${\ displaystyle g = 2k + 1}$${\ displaystyle {\ frac {n} {g}} (m-n + 1)}$${\ displaystyle g}$${\ displaystyle n}$${\ displaystyle m}$${\ displaystyle G}$

Графы Мура были названы Хоффманом и Синглтоном (1960) в честь Эдварда Ф. Мура , который поставил вопрос об описании и классификации этих графов.

Помимо максимально возможного количества вершин для данной комбинации степени и диаметра, графы Мура имеют минимально возможное количество вершин для обычного графа с данной степенью и обхватом. То есть любой граф Мура - это клетка . ^[2] Формула для числа вершин в графе Мура может быть обобщена, чтобы позволить определение графов Мура с четным и нечетным обхватом, и снова эти графы являются клетками.

Ограничение вершин по градусам и диаметрам [ править ]

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

Пусть 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 вершин. Таким образом, общее количество вершин может быть не более

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

Хоффман и Синглтон (1960) первоначально определили граф Мура как граф, для которого точно соблюдается это ограничение на количество вершин. Следовательно, любой граф Мура имеет максимально возможное количество вершин среди всех графов максимальной степени d и диаметра k .

Позже Синглтон (1968) показал, что графы Мура могут быть эквивалентно определены как имеющие диаметр k и обхват 2 k +1; эти два требования объединяются, чтобы заставить граф быть d -регулярным для некоторого d и удовлетворять формуле подсчета вершин.

Графики Мура как клетки [ править ]

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

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

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

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

${\ Displaystyle 2 \ сумма _ {я = 0} ^ {k-1} (d-1) ^ {i} = 1 + (d-1) ^ {k-1} + d \ sum _ {я = 0 } ^ {k-2} (d-1) ^ {i}.}$

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

Примеры [ править ]

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

• В полных графах по п> 2 узлов (диаметр 1, обхват 3, степень п-1, п) порядка${\displaystyle K_{n}}$
• Нечетные циклы (диаметр n, обхват 2n + 1, степень 2, порядок 2n + 1)${\displaystyle C_{2n+1}}$
• Граф Петерсена (диаметр 2, 5 обхват, степень 3, порядок 10)
• Хоффман-Синглтон (диаметр 2, 5 обхвата, степень 7, порядок 50)
• Гипотетический график диаметра 2, обхвата 5, степени 57 и порядка 3250, существование которого неизвестно ^[4]

Хотя все известные графы Мура являются вершинно-транзитивными графами , неизвестный (если он существует) не может быть вершинно-транзитивным, так как его группа автоморфизмов может иметь порядок не более 375, что меньше его числа вершин. ^[5]

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

См. Также [ править ]

• Проблема диаметра градуса
• Таблица наибольших известных графиков заданного диаметра и максимальной степени

Заметки [ править ]

Ссылки [ править ]

• Азария, Джерней; Клавжар, Санди (2015), «Графы и циклы Мура - экстремальные графы для выпуклых циклов», Журнал теории графов , 80 : 34–42, arXiv : 1210.6342 , doi : 10.1002 / jgt.21837
• Bannai, E .; Ито Т. (1973), «О конечных графах Мура» , журнал факультета естественных наук Токийского университета. Разд. 1 A, Mathematics , 20 : 191–208, MR  0323615 , заархивировано из оригинала 24 апреля 2012 г.
• Bollobás, Béla (1998), Modern Graph Theory , Graduate Texts in Mathematics , 184 , Springer-Verlag.
• Дальфо, К. (2019), «Обзор отсутствующего графа Мура» (PDF) , Линейная алгебра и ее приложения , 569 : 1–14, DOI : 10.1016 / j.laa.2018.12.035 , hdl : 2117/127212 , Руководство по ремонту  3901732
• Дамерелл, RM (1973), "О графах Мура", Математический Труды Кембриджского философского общества , 74 (2): 227-236, Bibcode : 1973PCPS ... 74..227D , DOI : 10,1017 / S0305004100048015 , MR  0318004
• Эрдеш, Пол ; Реньи, Альфред ; Сос, Вера Т. (1966), "О проблеме теории графов" (PDF) , Studia Sci. Математика. Hungar. , 1 : 215-235, архивируются от оригинала (PDF) на 2016-03-09 , извлекаются 2010-02-23.
• Хоффман, Алан Дж .; Singleton, Роберт Р. (1960), "Мур графы с диаметром 2 и 3", IBM Журнал исследований и разработок , 5 (4): 497-504, DOI : 10,1147 / rd.45.0497 , MR  0140437
• Мачай, Мартин; Siran, Юзеф (2010), "Поиск свойств отсутствующего Мура графа", Линейная алгебра и ее применения , 432 (9): 2381-2398, DOI : 10.1016 / j.laa.2009.07.018.
• Singleton, Роберт Р. (1968), "Там нет нерегулярного графа Мура", American Mathematical Monthly , 75 (1): 42-43, DOI : 10,2307 / 2315106 , JSTOR  2315106 , MR  0225679

Внешние ссылки [ править ]

• Брауэр и Хемерс: Спектры графов
• Эрик В. Вайсштейн , График Мура ( теорема Хоффмана-Синглтона ) в MathWorld .