Граф Хэмминга: различия между версиями
Glk (обсуждение | вклад) (Создана новая страница размером '''Граф Хэмминга''' (''Hamming graph'') - граф <math>G = (V,E)</math>, у которого каждая вершина <m...) |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 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] | ||
Версия от 11:50, 13 октября 2009
Граф Хэмминга (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].
Литература
[WG'90]