Граф Хэмминга: различия между версиями

Перейти к навигации Перейти к поиску
нет описания правки
(Создана новая страница размером '''Граф Хэмминга''' (''Hamming graph'') - граф <math>G = (V,E)</math>, у которого каждая вершина <m...)
 
Нет описания правки
Строка 1: Строка 1:
'''Граф Хэмминга''' (''Hamming graph'') -  
'''Граф Хэмминга''' (''[[Hamming graph]]'') - [[граф]] <math>G = (V,E)</math>, у которого каждая [[вершина]] <math>x \in V</math> может быть помечена словом <math>a(x)</math> (фиксированной длины <math>n</math>) над некоторым множеством символов <math>\Sigma</math> так, что выполняется равенство
граф <math>G = (V,E)</math>, у которого каждая вершина <math>x \in V</math> может быть
помечена словом <math>a(x)</math> (фиксированной длины <math>n</math>)
над некоторым множеством
символов <math>\Sigma</math> так, что выполняется равенство


<math>H(a(x), a(y)) = d_{G}(x,y),</math>
<math>H(a(x), a(y)) = d_{G}(x,y),</math>


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


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

Навигация