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

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].

Примітки

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