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

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

[math]\displaystyle{ H(a(x), a(y)) = d_{G}(x,y), }[/math]

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

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

Литература

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