stringtranslate.com

Граф Хэмминга

H (3,3) изображен как график единичных расстояний

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

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

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

Приложения

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

Сложность вычислений

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

Ссылки

  1. ^ abc Брауэр, Андрис Э .; Хемерс, Виллем Х. (2012), «12.3.1 Графы Хэмминга» (PDF) , Спектры графов , Universitext, Нью-Йорк: Springer, стр. 178, номер домена : 10.1007/978-1-4614-1939-6, ISBN 978-1-4614-1938-9, MR  2882891 , получено 2022-08-08.
  2. ^ Карами, Хамед (2022), «Сбалансированное расстояние по ребрам графов Хэмминга», Журнал дискретных математических наук и криптографии , 25 : 2667–2672, doi : 10.1080/09720529.2021.1914363.
  3. ^ ab Имрих, Вильфрид; Клавжар, Сэнди (2000), «Графы Хэмминга», Графы произведений , Wiley-Interscience Series in Discrete Mathematics and Optimization, Wiley-Interscience, Нью-Йорк, стр. 104–106, ISBN 978-0-471-37039-0, г-н  1788124.
  4. ^ Блокхейс, Аарт; Брауэр, Андрис Э .; Хемерс, Виллем Х. (2007), «О 3-хроматических дистанционно регулярных графах», Designs, Codes and Cryptography , 44 (1–3): 293–305, doi : 10.1007/s10623-007-9100-7 , MR  2336413. См. в частности примечание (e) на стр. 300.
  5. ^ ab Dekker, Anthony H.; Colbert, Bernard D. (2004), «Надежность сети и топология графа», Труды 27-й Австралазийской конференции по информатике — том 26, ACSC '04, Дарлингхерст, Австралия, Австралия: Australian Computer Society, Inc., стр. 359–368.
  6. ^ Бейли, Роберт Ф.; Кэмерон, Питер Дж. (2011), «Размер базы, метрическая размерность и другие инварианты групп и графов», Бюллетень Лондонского математического общества , 43 (2): 209–242, doi :10.1112/blms/bdq096, MR  2781204, S2CID  6684542.
  7. ^ Хорват, Борис; Писански, Томаж (2010), «Продукты графов единичных расстояний», Дискретная математика , 310 (12): 1783–1792, doi : 10.1016/j.disc.2009.11.035 , MR  2610282
  8. ^ Слоан, NJA (1989), «Нерешенные проблемы в теории графов, возникающие при изучении кодов» (PDF) , Graph Theory Notes of New York , 18 : 11–20.
  9. ^ Кулен, Якобус Х.; Ли, У Сон; Мартин, В. (2010), «Характеристика полностью регулярных кодов с алгебраической точки зрения», Комбинаторика и графики , Contemp. Матем., вып. 531, Провиденс, Род-Айленд: Америка, стр. 223–242, arXiv : 0911.1828 , doi : 10.1090/conm/531/10470, ISBN. 9780821848654, MR  2757802, S2CID  8197351. На стр. 224 авторы пишут, что «тщательное изучение полностью регулярных кодов в графах Хэмминга является центральным для изучения ассоциативных схем».

Внешние ссылки