21.4. МЕТРИЧЕСКИЕ СХЕМЫ

Схема Хэмминга и другие схемы, приведенные ниже, являются примерами метрических схем, которые определяются графами.

Пусть обозначает связанный граф с вершинами, не содержащий петель и кратных ребер, и пусть X обозначает множество вершин. Расстояние между вершинами равно числу ребер кратчайшего пути, соединяющего эти вершины. Максимальное расстояние (обозначим его через между любыми двумя вершинами называется диаметром графа

Определение. Граф называется метрически регулярным (или совершенно регулярным, или регулярным по расстоянию), если для любых для которых число вершин таких, что является константой не зависящей от выбора х и у.

Ясно, что из метрически регулярного графа диаметра мы получим схему отношений с классами, если назовем -связанными вершины находящиеся на расстоянии Схемы отношений, которые могут быть получены таким способом, называются метрическими схемами. Чтобы построить граф из схемы, вершины х и у назовем смежными, если и только если например, схема Хэмминга является метрической, а соответствующий ей граф представляет собой остов единичного -мерного куба (см. рис. 21.1).

Метрически регулярные графы диаметра 2 называются сильно регулярными графами.

Упражнения. (4). Показать, что любая схема отношений с двумя классами является метрической (и может быть получена из сильно регулярного графа).

Но не все схемы отношений — метрические.

(5). Показать, что схема отношений — метрическая, если и только если [Указание. (Необходимость.) Пусть обозначает граф, задаваемый отношением показать, что тогда и только тогда, когда

Таким образом, если схема отношений является метрической, то для

и, следовательно, многочлен относительно степени Тогда алгебра многочленов от и если известны собственные значения матрицы то легко находятся все собственные значения. В рассмотренном выше примере (в силу (21.23)), поэтому если а — произвольное собственное значение

матрицы является собственным значением матрицы . В общем случае согласно соотношению (21.27)

Упражнение. (6). Доказать, что если — многочлен относительно степени то схема — метрическая.

Наиболее интересным свойством метрической схемы является тот факт, что собственные значения могут быть получены с помощью семейства ортогональных многочленов.

Определение. Схема отношений называется -полиноми-альной схемой, если существуют неотрицательные действительные числа и действительные многочлены где такие, что

Из теоремы 3 вытекает, что образуют семейство ортогональных многочленов

Аналогично определяется -полиномиальная схема.

Например, схема Хэмминга одновременно является и и -поликомиальной схемой

Теорема 6. (Дельсарт.) Схема отношений является метрической тогда и только тогда, когда она является -полиномиальной схемой.

Доказательство. Если схема — метрическая, то — многочлен относительно степени Положим Тогда существуют многочлены такие, что Кроме того, и согласно упражнению (1) 0. Все числа различны, так как из условия вытекает, что что невозможно, так как матрица невырождена. Следовательно, схема является -полиномиальной.

Обратно предположим, что схема является -полиномиальной, и пусть где Тогда из условий вытекает, что Так как многочлены ортогональны, то они удовлетворяют некоторому трехчленному рекуррентному соотношению (см. Сегё [1297], с. 55) , где (Коэффициенты этого соотношения должны удовлетворять различным условиям, что нас сейчас не интересует.) Подстановка в это соотношение значения дает:

для соответствующим образом подобранных коэффициентов

Из упражнения (5) теперь следует, что схема является метрической.

Задача (нерешенная). (21.1). Дать подобное описание для Q-полиномиальных схем.