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

Граф Хэмминга
Назван в честь	Ричарда Хэмминга
Вершин	${\displaystyle q^{d}}$
Рёбер	${\displaystyle {\frac {d(q-1)q^{d}}{2}}}$
Диаметр	${\displaystyle d}$
Спектр	${\displaystyle \{(d(q-1)-qi)^{{\binom {d}{i}}(q-1)^{i}};i=0,\ldots ,d\}}$
Свойства	${\displaystyle d(q-1)}$-регулярный вершинно транзитивный дистанционно регулярный [1]

Графы Хэмминга — специальный класс графов, названных именем Ричарда Хэмминга и используемых в некоторых областях математики и информатики.

Определение

Пусть S — множество из q элементов, а d — положительное число. Граф Хэмминга H(d,q) имеет множество вершин S^d, множество упорядоченных d-кортежей элементов множества S (последовательности длины d элементов из S). Две вершины смежны, если они отличаются ровно одной координатой, то есть если расстояние Хэмминга равно единице. Граф Хэмминга H(d,q) равен прямому произведению d полных графов K_q [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₁
• H(d,2) является графом гиперкуба Q_d[1]
• H(3,3) является графом единичных расстояний с n=27 вершинами и n^4/3=81 рёбрами (на рисунке)

• 

Приложения

Графы Хэмминга интересны их связью с кодами с исправлением ошибок[6] и схемами отношений[7]. Они также приняты в качестве сетевой топологии в распределённых вычислениях[4].

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

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

Примечания

1. Brouwer, Haemers, 2012, с. 178.
2. Imrich, Klavžar, 2000, с. 104–106.
3. (Blokhuis, Brouwer, Haemers 2007). См. примечание на стр. 300.
4. Dekker, Colbert, 2004, с. 359–368.
5. Bailey, Cameron, 2011, с. 209–242.
6. Sloane, 1989, с. 11–20.
7. (Koolen, Lee, Martin 2010) На стр. 224 авторы пишут, что «тщательное изучение полных регулярных кодов в графах Хэмминга является центральным моментом при изучении ассоциативных схем».

Литература

• Andries E. Brouwer, Willem H. Haemers. Spectra of graphs. — New York: Springer, 2012. — С. 178. — (Universitext). — ISBN 978-1-4614-1938-9. — doi:10.1007/978-1-4614-1939-6.
• Wilfried Imrich, Sandi Klavžar. Product graphs. — Wiley-Interscience, New York, 2000. — С. 104—106. — (Wiley-Interscience Series in Discrete Mathematics and Optimization). — ISBN 0-471-37039-8.
• Aart Blokhuis, Andries E. Brouwer, Willem H. Haemers. On 3-chromatic distance-regular graphs // Designs, Codes and Cryptography. — 2007. — Т. 44, вып. 1—3. — С. 293—305. — doi:10.1007/s10623-007-9100-7.
• Anthony H. Dekker, Bernard D. Colbert. Proceedings of the 27th Australasian conference on Computer science - Volume 26. — Darlinghurst, Australia, Australia: Australian Computer Society, Inc., 2004. — С. 359—368. — (ACSC '04).
• Robert F. Bailey, Peter J. Cameron. Base size, metric dimension and other invariants of groups and graphs // Bulletin of the London Mathematical Society. — 2011. — Т. 43, вып. 2. — С. 209—242. — doi:10.1112/blms/bdq096.
• N. J. A. Sloane. Unsolved problems in graph theory arising from the study of codes // Graph Theory Notes of New York. — 1989. — Т. 18. — С. 11—20.
• Jacobus H. Koolen, Woo Sun Lee, William J. Martin. Combinatorics and graphs. — Providence, RI: Amer. Math. Soc., 2010. — Т. 531. — С. 223—242. — (Contemp. Math.). — doi:10.1090/conm/531/10470.

Ссылки

• Weisstein, Eric W. Hamming Graph (англ.) на сайте Wolfram MathWorld.
• Brouwer, Andries E. Hamming graphs  (неопр.). Дата обращения: 23 марта 2017. Архивировано 2 июля 2016 года.