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