Граф Хэмминга
Шаблон:Граф Графы Хэмминга — специальный класс графов, названных именем Ричарда Хэмминга и используемых в некоторых областях математики и информатики.
Определение
Пусть S — множество из q элементов, а d — положительное число. Граф Хэмминга H(d,q) имеет множество вершин Sd, множество упорядоченных d-кортежей элементов множества S (последовательности длины d элементов из S). Две вершины смежны, если они отличаются ровно одной координатой, то есть если расстояние Хэмминга равно единице. Граф Хэмминга H(d,q) равен прямому произведению d полных графов Kq Шаблон:Sfn.
В некоторых случаях графы Хэмминга могут определяться как прямое произведение полных графов, которые могут иметь различные размерыШаблон:Sfn. В отличие от графов H(d,q), эти графы более широкого класса не будут обязательно дистанционно регулярными, но остаются регулярными и вершинно транзитивными.
Специальные случаи
- H(2,3) является обобщённым четырёхугольником G Q (2,1)[1]
- H(1,q) является полным графом KqШаблон:Sfn.
- H(2,q) является графом-решёткой Lq,q, а также ладейным графом Шаблон:Sfn.
- H(d,1) является графом с одной вершиной K1
- H(d,2) является графом гиперкуба QdШаблон:Sfn
- H(3,3) является графом единичных расстояний с n=27 вершинами и n4/3=81 рёбрами (на рисунке)
Приложения
Графы Хэмминга интересны их связью с кодами с исправлением ошибокШаблон:Sfn и схемами отношений[2]. Они также приняты в качестве сетевой топологии в распределённых вычисленияхШаблон:Sfn.
Вычислительная сложность
Можно проверить, является ли граф графом Хэмминга, и если является, найти разметку вершин кортежами, которая реализует граф Хэмминга, за линейное времяШаблон:Sfn.
Примечания
Литература
Ссылки
- ↑ Шаблон:Harv. См. примечание на стр. 300.
- ↑ Шаблон:Harv На стр. 224 авторы пишут, что «тщательное изучение полных регулярных кодов в графах Хэмминга является центральным моментом при изучении ассоциативных схем».