Hamming graph
Названо на честь	Річард Геммінг
Вершин	${\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]
Позначення	${\displaystyle H(d,q)}$

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

Нехай ${\displaystyle S}$ — множина з q елементів, а ${\displaystyle d}$ — додатне число. Граф Геммінга H(d,q) має множину вершин ${\displaystyle S^{d))$, множину впорядкованих ${\displaystyle d}$-кортежів елементів множини ${\displaystyle S}$ (послідовності довжини ${\displaystyle d}$ елементів із ${\displaystyle S}$). Дві вершини суміжні, якщо вони відрізняються рівно однією координатою, тобто якщо відстань Геммінга дорівнює одиниці. Граф Геммінга ${\displaystyle H(d,q)}$дорівнює прямому добутку ${\displaystyle d}$ повних графів ${\displaystyle K_{q))$^[1].

У деяких випадках графи Геммінга можуть визначатися як прямий добуток повних графів, які можуть мати різні розміри^[2]. На відміну від графів ${\displaystyle H(d,q)}$, ці графи ширшого класу не будуть обов'язково дистанційно регулярними, але залишаються регулярними та вершинно транзитивними.

• ${\displaystyle H(2,3)}$ — узагальнений чотирикутник ${\displaystyle G\,Q\,(2,1)}$^[3].
• ${\displaystyle H(1,q)}$ — повний граф ${\displaystyle K_{q))$^[4].
• ${\displaystyle H(2,q)}$ — граф-ґратка ${\displaystyle L_{q,q))$, а також туровий граф^[5].
• ${\displaystyle H(d,1)}$ — граф із однією вершиною ${\displaystyle K_{1))$_.
• ${\displaystyle H(d,2)}$ — граф гіперкуба ${\displaystyle Q_{d))$^[1].
• ${\displaystyle H(3,3)}$ — граф одиничних відстаней з ${\displaystyle n=27}$ вершинами та ${\displaystyle n^{4/3}=81}$ ребром (на малюнку).

Графи Геммінга цікаві своїм зв'язком з кодами з виправленням помилок^[6] та схемами відношень^[en][7]. Також їх використвують як мережеву топологію в розподілених обчисленнях^[4].

Можна перевірити, чи є граф графом Геммінга, і, якщо є, знайти розмітку вершин кортежами, яка реалізує граф Геммінга, за лінійний час^[2].

• Weisstein, Eric W. Граф Геммінга(англ.) на сайті Wolfram MathWorld.
• Brouwer, Andries E. Hamming graphs. Архів оригіналу за 2 липня 2016. Процитовано 23 березня 2017.