[МУЗЫКА] [МУЗЫКА] Ричард Хэмминг — американский математик, работавший в знаменитой лаборатории Bell в период с 1946 года по 1976 год — был очень недоволен в самом начале своей карьеры тем, что программы с расчётами, которые он запускал на счётной машине этой компании Bell, а работали они тогда на релейных блоках с низкой скоростью и с вводом данных с помощью перфокарт... Так вот, во время чтения данных очень часто происходили ошибки, что приводило к автоматической остановке программы. Тогда Хэмминг придумал способ, как исправлять такие ошибки, которые возникают в одном бите. На самом деле, он придумал один из первых самоконтролирующихся и самокорректирующихся кодов, то есть кодов с исправлением ошибки, с автоматическим исправлением ошибки. Этот код был построен для двоичной системы исчислений. Хэмминг также придумал расстояние между двумя двоичными векторами одной и той же длины как число позиций, в которых эти векторы различаются. Такое расстояние теперь называется метрикой Хэмминга, и она обобщена для любых алфавитов. На основе этой метрики и было построены эти графы, которые мы сейчас будем с вами рассматривать. Но сначала давайте посмотрим пример, очень простой пример. Двоичный куб, вершинами которого являются двоичные векторы, и две вершины смежны тогда и только когда, когда эти двоичные векторы различаются ровно в одной позиции. Нетрудно увидеть, что векторы, или вершины нашего графа 000 и 111 находятся на максимальном расстоянии друг от друга, это диаметр этого графа, поскольку все позиции различны. А расстояние между вершинам 000 и 110, и 101 равно 2. Таков простейший пример графа Хэмминга. А теперь давайте введём понятие графа Хэмминга в самом общем виде. Рассмотрим пространство Хэмминга состоящее из q в степени n векторов длины n над алфавитом из q элементов. В этом пространстве мы определим метрику Хэмминга, которая равна числу различных позиций между векторами x и y. Тогда граф Хэмминга определяется как граф с множеством вершин, соответствующих элементам пространства Хэмминга, при этом ребро в нашем графе появляется тогда и только тогда, когда расстояние Хэмминга между соответствующими векторами равно 1. Граф Хэмминга можно также определить как декартово произведение n полных графов на q вершинах. Причём, если n = 1, то в этом случае наш граф будет изоморфен полному графу на q вершинах, а если q = 1, то мы имеем просто изолированные вершины. Граф Хэмминга обладает следующими свойствами. Он является регулярным графом в степени n * (q- 1) и диаметра n. Эти свойства следуют непосредственно из его определения. Этот граф также является дистанционно‐транзитивным. А поскольку он дистанционно‐транзитивный, значит, он должен быть и дистанционно регулярным, и массив его пересечений сейчас появляется на слайде. Помимо того, этот граф также является целочисленным графом, то есть спектр его содержит только целые значения, которые вы сейчас видите на слайде вместе с их кратностями. Помимо всего прочего, этот граф также является графом Кэли на аддитивной группе с порождающим множеством, которое также сейчас изображено на слайде. Так, для рассмотренного ранее двоичного куба, его вершинами являются двоичные векторы длины 3, а порождающее множество состоит из элементов стандартного базиса группы двоичных векторов длины n. То есть это векторы e1, e2, e3 — это стандартные векторы нашего пространства. Теперь давайте рассмотрим два частных случая графа Хэмминга. Если q = 2, то в этом случае граф Хэмминга принято называть гиперкубом, и обозначают его как Hn. Поскольку гиперкуб можно определить также как декартово произведение n графов K2, то в этом случае мы имеем следующее. Граф H1 будет изморфен K2, H2 изоморфен декартову произведению K2 на K2, и мы получаем цикл длины 4, H3 изморфен декартову произведению H2 на K2. А в общем случае мы имеем следующее. Гиперкуб H1 изоморфен декартову произведению H(n-1) на K2. Примеры гиперкубов малых размерностей можно сейчас видеть на слайде. Второй случай, частный случай графа Хэмминга. Если n = 2, то в этом случае граф Хэмминга называют «решёточный граф». Этот граф является сильно регулярным с параметрами q2; 2 * ( q- 1 ); ( q -2 ) и 2. Решёточный граф для q = 3 сейчас можно видеть на слайде. Всякая вершина имеет степень 4, и граф имеет диаметр 2. Нужно сказать, что по‐прежнему граф Хэмминга находит очень широкое применение в теории кодирования, в криптографии, в информатике, а также в биоинформатике, поскольку во всех этих дисциплинах используется метрика Хэмминга. Мы вернёмся с вами к этому графу в модуле 6, когда будем говорить о схемах отношений. А сейчас мне только хотелось бы отметить следующее, что Star граф, также являющийся графом Кэли на симметрической группе, и о спектральных свойствах которого мы с вами будем говорить в модуле 5, вкладывается в гиперкуб. Такая связь между этими двумя семействами графов была обнаружена, когда их стали использовать для представления компьютерных сетей. На сегодня всё. В следующий раз мы с вами поговорим о графах Джонсона и немного о графах Кнезера.