WikiDer > Граф Мура

Moore graph
Вопрос, Web Fundamentals.svgНерешенная проблема в математике:
Существует ли граф Мура с обхватом 5 и степенью 57?
(больше нерешенных задач по математике)

В теория графов, а Граф Мура это регулярный график из степень d и диаметр k число вершин которого равно верхней границе

Эквивалентное определение графа Мура состоит в том, что это граф диаметра с обхват . Другое эквивалентное определение графа Мура это то, что у него есть обхват и именно циклы длины , куда и - это соответственно количество вершин и ребер . На самом деле они экстремальны по количеству циклов, длина которых равна обхвату графа.[1]

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

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

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

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

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

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

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

Графики Мура как клетки

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

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

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

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

Примеры

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

  • В полные графики на n> 2 узлах (диаметр 1, обхват 3, степень n-1, порядок n)
  • Странный циклы (диаметр n, обхват 2n + 1, степень 2, порядок 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-угольника.

Смотрите также

Примечания

Рекомендации

  • Азария, Джерней; Клавжар, Санди (2015), «Графы Мура и циклы являются экстремальными графами для выпуклых циклов», Журнал теории графов, 80: 34–42, arXiv:1210.6342, Дои:10.1002 / jgt.21837
  • Bannai, E .; Ито, Т. (1973), «О конечных графах Мура», Журнал факультета естественных наук Токийского университета. Разд. 1 A, математика, 20: 191–208, МИСТЕР 0323615, заархивировано из оригинал на 2012-04-24
  • Боллобаш, Бела (1998), Современная теория графов, Тексты для выпускников по математике, 184, Springer-Verlag.
  • Dalfó, C. (2019), "Обзор отсутствующего графа Мура", Линейная алгебра и ее приложения, 569: 1–14, Дои:10.1016 / j.laa.2018.12.035, МИСТЕР 3901732
  • Дэмерелл Р. М. (1973), "О графах Мура", Математические труды Кембриджского философского общества, 74 (2): 227–236, Bibcode:1973PCPS ... 74..227D, Дои:10.1017 / S0305004100048015, МИСТЕР 0318004
  • Эрдеш, Пол; Реньи, Альфред; Сос, Вера Т. (1966), «К проблеме теории графов» (PDF), Studia Sci. Математика. Hungar., 1: 215–235, архивировано с оригинал (PDF) на 2016-03-09, получено 2010-02-23.
  • Хоффман, Алан Дж.; Синглтон, Роберт Р. (1960), "Графы Мура диаметром 2 и 3", Журнал исследований и разработок IBM, 5 (4): 497–504, Дои:10.1147 / ряд.45.0497, МИСТЕР 0140437
  • Мачай, Мартин; Ширань, Йозеф (2010), "Поиск свойств отсутствующего графа Мура", Линейная алгебра и ее приложения, 432 (9): 2381–2398, Дои:10.1016 / j.laa.2009.07.018.
  • Синглтон, Роберт Р. (1968), "Неправильный граф Мура не существует", Американский математический ежемесячный журнал, 75 (1): 42–43, Дои:10.2307/2315106, JSTOR 2315106, МИСТЕР 0225679

внешняя ссылка