ИНДЕКСНЫЕ МЕТОДЫ ФОРМИРОВАНИЯ КОМБИНАТОРНЫХ КОНФИГУРАЦИЙ КЛАССА СИСТЕМ РАЗЛИЧНЫХ ПРЕДСТАВИТЕЛЬСТВ

Резюме: Цель. В статье рассмотрены способы решения класса комбинаторных задач, известных как системы различных представительств (с.р.п.). Поставлена задача разработки методов и алгоритмов формирования комбинаторной конфигурации, включающей в себя в качестве строк, столбцов или строк и столбцов подмножества, являющиеся с.р.п., составленных из элементов исходного семейства nхn – множеств, занимающих в исходных множествах различные позиции, а также определить возможное количество предлагаемых конфигураций. Метод. Использованы методы индексного упорядочения расположения элементов в формируемых системах различных представительств, сущность которых состоит в формулировке требований к процессу формирования конфигураций, обладающих заданными свойствами, че- рез закономерность индексации в них элементов. Результат. Рассмотрена общая формулировка задачи построения с.р.п., как задача формирования из элементов совокупности множеств, подмножеств, которые включают в себя по одному элементу из каждого исходного множества, при этом каждый из этих элементов в исходных множествах расположены на различных позициях. Задача в работе переформулирована через особенности требований к индексации элементов этих подмножеств. Каждый элемент в системах множеств имеет двухиндексное обозначение, первый элемент в индексе указывает на его принадлежность определенному исходному множеству, второй – на местоположение. Для выполнения требований, сформулированных в поставленной задаче, необходимо, чтобы индексы элементов, образующих с.р.п., принимали значения от 1 до n. Вывод. Предложены два метода решения поставленной задачи: циклическими сдвигами строк и столбцов матричной конфигурации, сформированной исходными множествами и по заданному закону индексации элементов окружения. Определено число возможных вариантов формирования систем представительств. Установлены причины распространения предлагаемых методов решения задачи только для исходных множеств нечетной размерности. 

1. Виленкин Н.Я. Комбинаторика. - М.: Наука,1969

2. Лазарев A. Комбинаторика. Электронныйресурс. www. hse.ru. Institute of Control Seines of Russian Academy of sienses, 2010

3. Кадиев И.П., Кадиев П.А.Циклические методы индексной сортировки элементов массивов данных. Вестник ДГТУ, Технические науки, 2015, Т.. с.79-83

4. Кадиев И.П., Кадиев П.А. Способ задания правил индексации элементов матричных комбинаторных конфигураций. Вестник ДГТУ, Технические науки, 2016, Т.42. с.93-101

5. Кофман А.Н.Введение в прикладную комбинаторику. - М.: Наука, 1975

6. Носов В.А., Скачков В.Н., Тараканов В.Е. Комбинаторный анализ. (Матричные проблемы теории выбора). – Итоги науки. ВИНИТИ. Серия Теория вероятностей. Математическая статистика. Теоретическая кибернетика. 1981. №18.с.53-83

7. Райзер Г.Дж. Комбинаторная математика. – М.:, Мир, 1966

8. Рыбников К.А. Введение в комбинаторный анализ. – М.: Изд. МГУ, 1985

9. Рыбников К.А.Комбинаторный анализ. Очерки истории. – М.: Изд. МГУ,1998.

10. Сачков В.Н. Введение в комбинаторные методы дискретной математики. М.:Наука,1982

11. Тараканов В.Е. Комбинаторные задачи и {0,1}-матрицы. – М.: Наука, 1985.

12. М. Холл. Глава №5 «Системы различных представителей» // Комбинаторика Combinatorial Theory / пер. с англ. С. А. Широковой; под ред. А. О. Гельфанда и В. Е. Тараканова. – М.: Мир, 1970. – С. 65–78. – 424 с.

13. Alexander Schrijver. Chapter 22 «Transversals», chapter 23 «Common transversals» // Combinatorial optimization. – Springer, 2003.

14. Свами К. Тхуласираман. Графы, сетииалгоритмы /Graphs, Networks, and Algorithms пер. с англ. М. В. Горбатовой, В. Л. Торхова, С. А. Фролова, В. Н. Четверикова; под ред. В. А. Горбатова. – М.: Мир, 1984. – 455 с.

15. Denes J., Keedwell A. D. Latin Squares and their Applications, Budapest, 1974

16. Алекберли Д.М. Критерий существования непрерывного размещения двусимвольных слов в матрице раз- мера L×(2k+1). – Информационные технологии и вычислительные системы. 2010, №2, с. 50-58.

17. Коршунов Ю.М. Гл.11 Задачи теории расписаний и массового обслуживания. /В кН. Математические основы кибернетики. – М.: Энергоиздат, 1987, с.437-465

18. Моисеев Н.Н. Математические задачи системного анализа. – М.: Наука,1981, с.486 19. Айгнер М. Комбинаторная теория. - М.: Мир.1982.