Граф Геммінга

Hamming graph
Названо на честь	Річард Геммінг
Вершин	$q^{d}$
Ребер	${\frac {d(q-1)q^{d}}{2}}$
Діаметр	$d$
Спектр	$\{(d(q-1)-qi)^{{\binom {d}{i}}(q-1)^{i}};i=0,\ldots ,d\}$
Властивості	$d(q-1)$-регулярний вершинно-транзитивний дистанційно-регулярний
Позначення	$H(d,q)$

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

Визначення

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

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

Окремі випадки

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

• 

Застосування

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

Обчислювальна складність

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

Література

• 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. Граф Геммінга(англ.) на сайті Wolfram MathWorld.
• Brouwer, Andries E. Hamming graphs. Архів оригіналу за 2 липня 2016. Процитовано 23 березня 2017.