Графы Хэмминга - это особый класс графов, названный в честь Ричарда Хэмминга и используемый в нескольких областях математики и информатики . Пусть S - набор из q элементов, а d - натуральное число. Хэмминг граф Н ( д , д ) имеет множество вершин S д , множество упорядоченных д -кортежей элементов S , или последовательностей длина D от S . Две вершины смежны, если они отличаются ровно одной координатой; то есть, если ихРасстояние Хэмминга равно единице. Хэмминга графа Н ( д , д ) является, что эквивалентно, декартово произведение из г полных графов K д . [1]
Граф Хэмминга | |
---|---|
Названный в честь | Ричард Хэмминг |
Вершины | |
Края | |
Диаметр | |
Спектр | |
Характеристики | -регулярный Вершинно-транзитивный дистанционно-регулярный [1] |
Обозначение | |
Таблица графиков и параметров |
В некоторых случаях графы Хэмминга могут рассматриваться в более общем плане как декартовы произведения полных графов, которые могут иметь различные размеры. [2] В отличие от графов Хэмминга H ( d , q ), графы этого более общего класса не обязательно дистанционно регулярны , но они продолжают быть регулярными и вершинно-транзитивными .
Особые случаи
- H (2,3), который является обобщенным четырехугольником G Q (2,1) [3]
- H (1, q ), который является полным графом K q [4]
- H (2, q ), который является решетчатым графом L q, q, а также графом ладьи [5]
- H ( d , 1), который является одноэлементным графом K 1
- H ( d , 2), который является графом гиперкуба Q d . [1] Гамильтоновы пути в этих графах образуют коды Грея .
- Поскольку декартовы произведения графов сохраняют свойство быть графом единичных расстояний , [6] графы Хэмминга H ( d , 2) и H ( d , 3) являются графами единичных расстояний.
Приложения
Графики Хэмминга интересны в связи с исправлением ошибок кодов [7] и ассоциативных схем , [8] , чтобы назвать две области. Они также рассматривались как топология сети связи в распределенных вычислениях . [4]
Вычислительная сложность
Можно за линейное время проверить, является ли граф графом Хэмминга, и в этом случае найти его пометку с кортежами, которая реализует его как граф Хэмминга. [2]
Рекомендации
- ^ a b c Брауэр, Андрис Э .; Хемерс, Виллем Х. (2012), Спектры графов , Universitext, New York: Springer, p. 178, DOI : 10.1007 / 978-1-4614-1939-6 , ISBN 978-1-4614-1938-9, Руководство по ремонту 2882891.
- ^ а б Имрих, Вильфрид; Клавжар, Санди (2000), "Графы Хэмминга", Графы продуктов , Серия Wiley-Interscience по дискретной математике и оптимизации, Wiley-Interscience, Нью-Йорк, стр. 104–106, ISBN 978-0-471-37039-0, MR 1788124.
- ^ Blokhuis, Aart; Брауэр, Андрис Э .; Haemers, Willem H. (2007), "На 3-хроматических дистанционно регулярных графов", Designs, Коды и криптография , 44 (1-3): 293-305, дой : 10,1007 / s10623-007-9100-7 , MR 2336413. См., В частности, примечание (e) на стр. 300.
- ^ а б Деккер, Энтони Х .; Колберт, Бернард Д. (2004), «Надежность сети и топология графов», Труды 27-й Австралазийской конференции по информатике - Том 26 , ACSC '04, Дарлингхерст, Австралия, Австралия: Австралийское компьютерное общество, Inc., стр. 359 –368.
- ^ Бейли, Роберт Ф .; Кэмерон, Питер Дж (2011), "Базовый размер, метрическая размерность и другие инварианты групп и графов", Бюллетень Лондонского математического общества , 43 (2): 209-242, DOI : 10,1112 / БЛМ / bdq096 , MR 2781204.
- ^ Хорват, Борис; Pisanski, Tomaž (2010), "Продукты единицы измерения расстояния графов", дискретная математика , 310 (12): 1783-1792, DOI : 10.1016 / j.disc.2009.11.035 , МР 2610282
- ^ Sloane, NJA (1989), "Нерешенные проблемы теории графов, возникающие при изучении кодов" (PDF) , Graph Theory Notes of New York , 18 : 11–20.
- ^ Koolen, Jacobus H .; Ли, Ву Сон; Мартин, Уильям Дж. (2010), «Характеризация полностью регулярных кодов с алгебраической точки зрения», Комбинаторика и графы , Contemp. Math., 531 , Providence, RI: Amer. Математика. Soc, стр 223-242,.. Arxiv : 0911,1828 , DOI : 10,1090 / conm / 531/10470 , ISBN 9780821848654, Руководство по ремонту 2757802. На стр. 224 авторы пишут, что «тщательное изучение полностью регулярных кодов в графах Хэмминга является центральным для изучения схем ассоциации».
Внешние ссылки
- Вайсштейн, Эрик В. «График Хэмминга» . MathWorld .
- Брауэр, Андрис Э. "Графы Хэмминга" .