Граф Хэмминга - Hamming graph

Граф Хэмминга
Названный в честьРичард Хэмминг
Вершины
Края
Диаметр
Спектр
Характеристики-обычный
Вершинно-транзитивный
Дистанционно-регулярный[1]
Обозначение
Таблица графиков и параметров
ЧАС(3,3) нарисованный как график единичного расстояния

Графы Хэмминга особый класс графики названный в честь Ричард Хэмминг и используется в нескольких отраслях математика и Информатика. Позволять S быть набором q элементы и d положительное целое число. Граф Хэмминга ЧАС(d,q) имеет множество вершин Sd, набор заказанных d-наборы элементов S, или последовательности длины d из S. Две вершины соседний если они отличаются ровно по одной координате; то есть, если их Расстояние Хэмминга является одним. Граф Хэмминга ЧАС(d,q) эквивалентно Декартово произведение из d полные графики Kq.[1]

В некоторых случаях графы Хэмминга могут рассматриваться в более общем смысле как декартовы произведения полных графов, которые могут иметь различные размеры.[2] В отличие от графов Хэмминга ЧАС(d,q) графы в этом более общем классе не обязательно дистанционно-регулярный, но они продолжают быть обычный и вершинно-транзитивный.

Особые случаи

  • ЧАС(2,3), который является обобщенным четырехугольником грамм Q (2,1)[3]
  • ЧАС(1,q), который является полным графом Kq[4]
  • ЧАС(2,q), который является решетчатым графом Lд, д а также график ладьи[5]
  • ЧАС(d, 1), который представляет собой одноэлементный граф K1
  • ЧАС(d, 2), что является граф гиперкуба Qd.[1] Гамильтоновы пути в виде этих графиков Коды Грея.
  • Поскольку декартовы произведения графов сохраняют свойство быть график единичного расстояния,[6] графы Хэмминга ЧАС(d, 2) и ЧАС(d, 3) являются графами единичных расстояний.

Приложения

Графы Хэмминга интересны в связи с коды с исправлением ошибок[7] и схемы ассоциации,[8] назвать две области. Они также рассматривались как топология сети связи в распределенных вычислений.[4]

Вычислительная сложность

Это возможно в линейное время чтобы проверить, является ли граф графом Хэмминга, и в этом случае найдите его пометку с кортежами, которая реализует его как граф Хэмминга.[2]

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

  1. ^ а б c Брауэр, Андрис Э.; Хемерс, Виллем Х. (2012), Спектры графиков, Universitext, New York: Springer, p. 178, Дои:10.1007/978-1-4614-1939-6, ISBN  978-1-4614-1938-9, МИСТЕР  2882891.
  2. ^ а б Имрих, Вильфрид; Клавжар, Санди (2000), «Графики Хэмминга», Графики продуктов, Серия Wiley-Interscience по дискретной математике и оптимизации, Wiley-Interscience, Нью-Йорк, стр. 104–106, ISBN  978-0-471-37039-0, МИСТЕР  1788124.
  3. ^ Blokhuis, Aart; Брауэр, Андрис Э.; Хемерс, Виллем Х. (2007), "О 3-хроматических дистанционно регулярных графах", Конструкции, коды и криптография, 44 (1–3): 293–305, Дои:10.1007 / s10623-007-9100-7, МИСТЕР  2336413. См., В частности, примечание (e) на стр. 300.
  4. ^ а б Деккер, Энтони Х .; Кольбер, Бернар Д. (2004), "Устойчивость сети и топология графа", Труды 27-й Австралазийской конференции по информатике - Том 26, ACSC '04, Дарлингхерст, Австралия, Австралия: Австралийское компьютерное общество, Inc., стр. 359–368.
  5. ^ Бейли, Роберт Ф .; Кэмерон, Питер Дж. (2011), «Базовый размер, метрическая размерность и другие инварианты групп и графов», Бюллетень Лондонского математического общества, 43 (2): 209–242, Дои:10.1112 / blms / bdq096, МИСТЕР  2781204.
  6. ^ Хорват, Борис; Писанский, Томаж (2010), «Произведение графов единичных расстояний», Дискретная математика, 310 (12): 1783–1792, Дои:10.1016 / j.disc.2009.11.035, МИСТЕР  2610282
  7. ^ Слоан, Н. Дж. А. (1989), «Нерешенные проблемы теории графов, возникающие при изучении кодов» (PDF), Заметки по теории графов Нью-Йорка, 18: 11–20.
  8. ^ Koolen, Jacobus H .; Ли, Ву Сон; Мартин, Уильям Дж. (2010), "Характеризация полностью регулярных кодов с алгебраической точки зрения", Комбинаторика и графики, Contemp. Математика, 531, Провиденс, Род-Айленд: амер. Математика. Soc., Стр. 223–242, arXiv:0911.1828, Дои:10.1090 / conm / 531/10470, ISBN  9780821848654, МИСТЕР  2757802. На стр. 224 авторы пишут, что «тщательное изучение полностью регулярных кодов в графах Хэмминга имеет центральное значение для изучения схем ассоциации».

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