Меню Главная Случайная статья Настройки Граф Хэмминга Материал из https://ru.wikipedia.org Графы Хэмминга — специальный класс графов, названных именем Ричарда Хэмминга и используемых в некоторых областях математики и информатики. Содержание 1 Определение 2 Специальные случаи 3 Приложения 4 Вычислительная сложность 5 Примечания 6 Литература 7 Ссылки Определение Пусть S — множество из q элементов, а d — положительное число. Граф Хэмминга H(d,q) имеет множество вершин Sd, множество упорядоченных d-кортежей элементов множества S (последовательности длины d элементов из S). Две вершины смежны, если они отличаются ровно одной координатой, то есть если расстояние Хэмминга равно единице. Граф Хэмминга H(d,q) равен прямому произведению d полных графов Kq [1]. В некоторых случаях графы Хэмминга могут определяться как прямое произведение полных графов, которые могут иметь различные размеры[2]. В отличие от графов H(d,q), эти графы более широкого класса не будут обязательно дистанционно регулярными, но остаются регулярными и вершинно транзитивными. Специальные случаи H(2,3) является обобщённым четырёхугольником G Q (2,1)[3] H(1,q) является полным графом Kq[4]. H(2,q) является графом-решёткой Lq,q, а также ладейным графом [5]. H(d,1) является графом с одной вершиной K1 H(d,2) является графом гиперкуба Qd[1] H(3,3) является графом единичных расстояний с n=27 вершинами и n4/3=81 рёбрами (на рисунке) Приложения Графы Хэмминга интересны их связью с кодами с исправлением ошибок[6] и схемами отношений[7]. Они также приняты в качестве сетевой топологии в распределённых вычислениях[4]. Вычислительная сложность Можно проверить, является ли граф графом Хэмминга, и если является, найти разметку вершин кортежами, которая реализует граф Хэмминга, за линейное время[2]. Примечания 1 2 3 Brouwer, Haemers, 2012, с. 178. 1 2 Imrich, Klavar, 2000, с. 104–106. (Blokhuis, Brouwer, Haemers 2007). См. примечание на стр. 300. 1 2 Dekker, Colbert, 2004, с. 359–368. Bailey, Cameron, 2011, с. 209–242. Sloane, 1989, с. 11–20. (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. 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. 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. Ссылки Weisstein, Eric W. Hamming Graph (англ.) на сайте Wolfram MathWorld. Brouwer, Andries E. Hamming graphs  (неопр.). Дата обращения: 23 марта 2017. Архивировано 2 июля 2016 года.