Для установки нажмите кнопочку Установить расширение. И это всё.

Исходный код расширения WIKI 2 регулярно проверяется специалистами Mozilla Foundation, Google и Apple. Вы также можете это сделать в любой момент.

4,5
Келли Слэйтон
Мои поздравления с отличным проектом... что за великолепная идея!
Александр Григорьевский
Я использую WIKI 2 каждый день
и почти забыл как выглядит оригинальная Википедия.
Статистика
На русском, статей
Улучшено за 24 ч.
Добавлено за 24 ч.
Альтернативы
Недавние
Show all languages
Что мы делаем. Каждая страница проходит через несколько сотен совершенствующих техник. Совершенно та же Википедия. Только лучше.
.
Лео
Ньютон
Яркие
Мягкие

Граф Брауэра — Хемерса

Из Википедии — свободной энциклопедии

Граф Брауэра — Хемерса
Вершин 81
Рёбер 810
Диаметр 2
Обхват 3
Автоморфизмы 233280
Хроматическое число 7
Свойства
Логотип Викисклада Медиафайлы на Викискладе

Граф Брауэра — Хемерса — 20-регулярный неориентированный граф с 81 вершиной и 810 рёбрами. Это сильно регулярный, дистанционно-транзитивный граф и граф Рамануджана. Хотя его построение является математическим фольклором, он был назван именами Андреаса Брауэра и Уиллема Х. Хемерса, которые доказали его единственность в качестве строго регулярного графа.

Построение

Граф Брауэра — Хемерса имеет несколько связанных алгебраических построений. Одно из самых простых построений — как обобщённый граф Пэли порядка 4. Его можно определить путём выбора каждой вершины из конечного поля , а в качества рёбер берутся каждые два элемента, отличающиеся на четвёртую степень[1][2].

Свойства

Граф Брауэра — Хемерса является единственным сильно регулярным графом с параметрами (81, 20, 1, 6). Это означает, что он имеет 81 вершину, 20 рёбер на вершину, 1 треугольник на ребро и путь, соединяющий каждые две несмежные вершины имеет длину 6[3]. Как сильно регулярный граф с третьим параметром 1, граф Брауэра — Хемерса обладает свойством, что любое ребро принадлежит единственному треугольнику. То есть он локально линеен. Поиск больших плотных графов с этим свойством является одной из формулировок проблемы Ружи — Семереди[4].

Будучи строго регулярным, граф дистанционно-транзитивен[5].

История

Хотя Брауэр писал, что построения этого графа является «фольклорным» и цитировал раннюю статью 1964 года по латинским квадратам Дейла М. Меснера[1], граф назван именами Андреаса Брауэра и Уиллема Х. Хемерса, которые в 1992 году опубликовали доказательство, что он единственный строго регулярный граф с такими параметрами[3].

Связанные графы

Граф Брауэра — Хемерса является первым в бесконечном семействе графов Рамануджана, определённых как обобщение графов Пэли над полем характеристики три[2]. Вместе с ладейным графом и графом Геймса он является одним из трёх возможных сильно регулярных графов, параметры которых имеют вид [6].

Граф следует отличать от графа судоку, другого 20-регулярного графа с 81 вершиной. Граф судоку получается из головоломки Судоку, если разместить вершину в каждой ячейке судоку и соединить рёбрами вершины, которые находятся в той же строке, в том же столбце или блоке головоломки. Граф имеет много клик с 9 вершинами и требует 9 цветов для любой раскраски. Раскраска в 9 цветов этого графа описывает решение головоломки судоку[7][8]. В качестве контраста, в графе Брауэра — Хемерса наибольшими кликами являются треугольники и для раскраски нужно лишь 7 цветов[5].

Примечания

  1. 1 2 Andries Brouwer. Brouwer–Haemers graph. Архивировано 10 апреля 2018 года.
  2. 1 2 Ricardo A. Podestá. The spectra of generalized Paley graphs and applications. — 2018. — arXiv:1812.03332.
  3. 1 2 Brouwer A. E., Haemers W. H. Structure and uniqueness of the (81,20,1,6) strongly regular graph // Discrete Mathematics. — 1992. — Т. 106/107. — С. 77–82. — doi:10.1016/0012-365X(92)90532-K.
  4. Clark L. H., Entringer R. C., McCanna J. E., Székely L. A. Extremal problems for local properties of graphs // The Australasian Journal of Combinatorics. — 1991. — Т. 4. — С. 25–31. Архивировано 6 апреля 2019 года.
  5. 1 2 Weisstein, Eric W. Brouwer–Haemers Graph (англ.) на сайте Wolfram MathWorld.
  6. Andriy V. Bondarenko, Danylo V. Radchenko. On a family of strongly regular graphs with  // Journal of Combinatorial Theory. — 2013. — Т. 103, вып. 4. — С. 521–531. — doi:10.1016/j.jctb.2013.05.005.
  7. Jesús Gago-Vargas, Maria Isabel Hartillo-Hermoso, Jorge Martín-Morales, Jose Maria Ucha-Enríquez. Sudokus and Gröbner bases: Not only a divertimento // Computer Algebra in Scientific Computing, 9th International Workshop, CASC 2006, Chisinau, Moldova, September 11-15, 2006, Proceedings / Victor G. Ganzha, Ernst W. Mayr, Evgenii V. Vorozhtsov. — Springer, 2006. — Т. 4194. — С. 155–165. — (Lecture Notes in Computer Science). — doi:10.1007/11870814_13.
  8. Agnes M. Herzberg, M. Ram Murty. Sudoku squares and chromatic polynomials // Notices of the American Mathematical Society. — 2007. — Т. 54, вып. 6. — С. 708–717. Архивировано 18 февраля 2019 года.
Эта страница в последний раз была отредактирована 31 января 2024 в 17:00.
Как только страница обновилась в Википедии она обновляется в Вики 2.
Обычно почти сразу, изредка в течении часа.
Основа этой страницы находится в Википедии. Текст доступен по лицензии CC BY-SA 3.0 Unported License. Нетекстовые медиаданные доступны под собственными лицензиями. Wikipedia® — зарегистрированный товарный знак организации Wikimedia Foundation, Inc. WIKI 2 является независимой компанией и не аффилирована с Фондом Викимедиа (Wikimedia Foundation).