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

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

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

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

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

$H (2,3)$ , который представляет собой обобщенный четырехугольник $G Q (2,1)$ ^[4]
$H (1, q)$ , который представляет собой полный граф $K q$ ^[5]
$H (2, q)$ , который представляет собой решетчатый граф $L q,q,$ а также ладейный граф ^[6]
$H (d,1)$ , который является одноэлементным графом $K 1$
$H (d,2)$ , который является графом гиперкуба $Q d$ . ^[1] Гамильтоновы пути в этих графах образуют коды Грея .
Поскольку декартовы произведения графов сохраняют свойство быть графом единичных расстояний , ^[7] графы Хэмминга $H (d,2)$ и $H (d,3)$ являются графами единичных расстояний.

Приложения

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

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

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

Ссылки

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

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

[bh12-1] Jump up to: Перейти обратно: ^а ^б ^с Брауэр, Андрис Э .; Хемерс, Виллем Х. (2012), «12.3.1 Графы Хэмминга» (PDF) , Спектры графов , Universitext, Нью-Йорк: Springer, стр. 178, номер домена : 10.1007/978-1-4614-1939-6 , ISBN. 978-1-4614-1938-9 , MR 2882891 , получено 8 августа 2022 г. .

[2] Карами, Хамед (2022), «Сбалансированные по граничному расстоянию графы Хэмминга», Журнал дискретных математических наук и криптографии , 25 : 2667–2672, doi : 10.1080/09720529.2021.1914363 .

[ik00-3] Jump up to: Перейти обратно: ^а ^б Имрих, Вильфрид; Клавжар, Сэнди (2000), «Графы Хэмминга», Графики продуктов , Серия Wiley-Interscience по дискретной математике и оптимизации, 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.

[dc04-5] Jump up to: Перейти обратно: ^а ^б Деккер, Энтони Х.; Кольбер, Бернард Д. (2004), «Надежность сети и топология графов», Материалы 27-й Австралазийской конференции по информатике - Том 26 , ACSC '04, Дарлингхерст, Австралия, Австралия: Австралийское компьютерное общество, 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) , «Записки по теории графов», Нью-Йорк , 18 : 11–20 .

[9] Кулен, Якобус Х.; Ли, У Сон; Мартин, В. (2010), «Характеристика полностью регулярных кодов с алгебраической точки зрения», Комбинаторика и графики , Contemp. Матем., вып. 531, Провиденс, Род-Айленд: Америка, стр. 223–242, arXiv : 0911.1828 , doi : 10.1090/conm/531/10470 , ISBN 9780821848654 , МР 2757802 , S2CID 8197351 . На стр. 224, авторы пишут, что «тщательное изучение вполне регулярных кодов в графах Хэмминга имеет центральное значение для изучения ассоциативных схем».

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]