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