ФУНДАМЕНТАЛЬНАЯ И ПРИКЛАДНАЯ МАТЕМАТИКА
2008, ТОМ 14, ВЫПУСК 4, СТР. 137-149

Матрицы и графы существенной зависимости правильных семейств функций

А. А. Козлов
В. А. Носов
А. Е. Панкратьев

Аннотация

Посмотреть как HTML    Посмотреть как рисунок

В работе исследуются правильные семейства функций, применяемые при функциональном задании латинских квадратов большого порядка над множеством $n$-мерных булевых векторов. Правильные семейства функций изучаются с точки зрения структуры соответствующих графов существенной зависимости и их матриц инцидентности. Выведены различные необходимые и достаточные условия, при которых булева матрица реализуется как матрица существенной зависимости некоторого правильного семейства функций. Рассмотрены преобразования матриц, сохраняющие указанное свойство. Показано, что любой ориентированный граф без петель и кратных рёбер можно достаточно экономно вложить в качестве вершинного подграфа в граф существенной зависимости правильного семейства функций. При этом функции получаемого правильного семейства наследуют свойства семейства функций, реализующего исходный граф.

Полнотекстовая версия статьи в формате PDF (160 Kb)

URL страницы: http://mech.math.msu.su/~fpm/rus/k08/k084/k08408h.htm
Изменения вносились 28 февраля 2009 г.