Граф Хэмминга

Материал из WikiGrapp
Перейти к:навигация, поиск

Граф Хэмминга (Hamming graph) — граф G = (V,E), у которого каждая вершина x \in V может быть помечена словом a(x) (фиксированной длины n) над некоторым множеством символов \Sigma так, что выполняется равенство

H(a(x), a(y)) = d_{G}(x,y),

где d_{G}(x,y) — обычное расстояние в графе, а H(a,b) — расстояние Хэмминга между a и b, т.е. число позиций k, в которых k-й символ в a отличается от k-го символа в b. Если |\Sigma|= c, то граф Хэмминга есть d-мерная c-арная клика.

Граф G называется бинарным графом Хэмминга, если \Sigma =\{0,1\}.

Литература

  • Workshop. Berlin, 1990 // Lect. Notes Comp. Sci., 1991, vol. 484.