Графи Геммінга — це спеціальний клас графів, названих ім'ям Річарда Геммінга, які використовуються в деяких галузях математики та інформатики.
Визначення Нехай — множина з q елементів, а — додатне число. Граф Геммінга H(d,q) має множину вершин , множину впорядкованих -кортежів елементів множини (послідовності довжини елементів із ). Дві вершини суміжні, якщо вони відрізняються рівно однією координатою, тобто якщо відстань Геммінга дорівнює одиниці. Граф Геммінга дорівнює прямому добутку повних графів .
У деяких випадках графи Геммінга можуть визначатися як прямий добуток повних графів, які можуть мати різні розміри. На відміну від графів , ці графи ширшого класу не будуть обов'язково дистанційно регулярними, але залишаються регулярними та вершинно транзитивними.
Окремі випадки
— узагальнений чотирикутник . Див. примітку на с. 300.. — повний граф . — граф-ґратка , а також туровий граф. — граф із однією вершиною . — граф гіперкуба . — граф одиничних відстаней з вершинами та ребром (на малюнку).
Застосування Графи Геммінга цікаві своїм зв'язком з кодами з виправленням помилок та На с. 224 автори пишуть, що «ретельне вивчення повних регулярних кодів у графах Геммінга є центральним моментом при вивченні асоціативних схем».. Також їх використвують як мережеву топологію в розподілених обчисленнях.
Обчислювальна складність Можна перевірити, чи є граф графом Геммінга, і, якщо є, знайти розмітку вершин кортежами, яка реалізує граф Геммінга, за лінійний час.
Примітки
Література
Посилання