INDEXING METHODS FOR FORMING COMBINATORIAL CONFIGURATIONS OF THE CLASS OF SYSTEMS OF DISTINCT REPRESENTATIVES

Abstract. Objectives In this paper, methods for solving of a class of combinatorial tasks, known as systems of distinct representatives (SDR), are considered. The objective is to develop methods and algorithms for the formation of a combinatorial SDR configuration that includes as rows, columns or row- and column subsets, which are composed of elements of the original family of nxn – sets occupying different positions in the initial sets, as well to determine the possible number of proposed configurations. Method Index ordering methods are used for the arrangement of elements in the formed systems of distinct representatives, the essence of which is to formulate requirements for the process of configuration having specified properties through the regularity of indexing elements within these configurations. Results The general formulation of the issue of constructing an SDR is considered in terms of a problem of formation from the elements of sets and subsets, which include one element from each initial set, with each of these elements being located at different positions in the original sets. The task was reformulated in reference to the requirements for indexing the elements of these subsets. Each element in set systems has a two-index designation, with the first element in the index indicating membership of a specific initial set and the second – to its location. In order to fulfil the requirements formulated in the task, it is necessary for indices of the SDR elements to have values from 1 to n. Conclusion Two methods for solving the problem are proposed: cyclic shifts of rows and columns of the matrix configuration formed by the original sets, and by a given law for indexing the elements of the environment. The number of possible options for the formation of representative systems is determined. The reasons for the propagation of the proposed methods for solving the problem are established only for initial sets of odd dimensions. 

1. Vilenkin N.Ya. Kombinatorika. Moscow: Nauka; 1969. [Vilenkin N.Ya. Combinatorics. Moscow: Nauka; 1969. (in Russ.)]

2. Lazarev A. Kombinatorika. Elektronnyy resurs. www. hse.ru. Institute of Control Seines of Russian Academy of scienses, 2010. [Lazarev A. Combinatorics. Electronic resource. www. hse.ru. Institute of Control Seines of Russian Academy of scienses, 2010. (in Russ.)]

3. Kadiev I.P., Kadiev P.A. Tsiklicheskie metody indeksnoy sortirovki elementov massivov dannykh. Vestnik Dagestanskogo gosudarstvennogo tekhnicheskogo universiteta. Tekhnicheskie nauki. 2015; 36:79-83. [Kadiev I.P., Kadiev P.A. Cyclic methods of index sorting of data array elements. Herald of Daghestan State Technical University. Technical Sciences. 2015; 36:79-83. (in Russ.)]

4. Kadiev I.P., Kadiev P.A. Sposob zadaniya pravil indeksatsii elementov matrichnykh kombinatornykh konfiguratsiy. Vestnik Dagestanskogo gosudarstvennogo tekhnicheskogo universiteta. Tekhnicheskie nauki, 2016; 42:93-101. [Kadiev I.P., Kadiev P.A. The method of specifying indexing rules for elements of matrix combinatorial configurations. Herald of Daghestan State Technical University. Technical Sciences. 2016; 42:93-101. (in Russ.)]

5. Kofman A.N. Vvedenie v prikladnuyu kombinatoriku. Moscow: Nauka; 1975. [Kofman A.N. Introduction to applied combinatorics. Moscow: Nauka; 1975. (in Russ.)]

6. Nosov V.A., Skachkov V.N. Tarakanov V.E. Kombinatornyy analiz (Matrichnye problemy teorii vybora). Itogi nauki. VINITI. Seriya Teoriya veroyatnostey. Matematicheskaya statistika. Teoreticheskaya kibernetika. 1981; 18:53-83. [Nosov V.A., Skachkov V.N. Tarakanov V.E. Combinatorial analysis (Matrix problems of the decision theory). Journal of Mathematical Sciences. 1981; 18:53-83. (in Russ.)]

7. Rayzer G.Dzh. Kombinatornaya matematika. Moscow: Mir; 1966. [Rayzer G.Dzh. Combinatorial mathematics. Moscow: Mir; 1966. (in Russ.)]

8. Rybnikov K.A. Vvedenie v kombinatornyy analiz. Moscow: Izd. MGU; 1985. [Rybnikov K.A. Introduction to combinatorial analysis. Moscow: MSU; 1985. (in Russ.)]

9. Rybnikov K.A. Kombinatornyy analiz. Ocherki istorii. Moscow: Izd. MGU; 1998. [Rybnikov K.A. Combinatorial analysis. Historical essays. Moscow: MSU; 1998. (in Russ.)]

10. Skachkov V.N. Vvedenie v kombinatornye metody diskretnoy matematiki. Moscow: Nauka; 1982. [Skachkov V.N. Introduction to combinatorial methods of discrete mathematics. Moscow: Nauka; 1982. (in Russ.)]

11. Tarakanov V.E. Kombinatornye zadachi i {0,1}-matritsy. Moscow: Nauka; 1985. [Tarakanov V.E. Combinatorial tasks and {0,1} -matrices. Moscow: Nauka; 1985. (in Russ.)]

12. Holl M. Glava №5 ―Sistemy razlichnykh predstaviteley‖ v ―Kombinatorika = Combinatorial Theory‖ pod red. Gel’fanda A.O. i Tarakanova V.E. Moscow: Mir; 1970. S. 65-78. [Holl M. Chapter №5 ―Systems of distinct representatives‖ in ―Combinatorics = Combinatorial Theory‖ Gel’fand A.O. and Tarakanov V.E. (Eds). Moscow: Mir; 1970. P. 65-78. (in Russ.)]

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

14. Svami K.T. Grafy, seti i algoritmy. Pod red. Gorbatova V.A. Moscow: Mir; 1984. 455 s. [Svami K.T. Graphs, Networks, and Algorithms. Gorbatov V.A. (Ed). Moscow: Mir; 1984. 455 p. (in Russ.)]

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

16. Alekberli D.M. Kriteriy sushchestvovaniya nepreryvnogo razmeshcheniya dvusimvol'nykh slov v matritse razmera L×(2k+1). Informatsionnye tekhnologii i vychislitel'nye sistemy. 2010; 2:50-58. [Alekberli D.M. A criterion for the existence of a continuous allocation of twocharacter words in L×(2k+1)-sized matrix. Informatsionnye tekhnologii i vychislitel'nye sistemy. 2010; 2:50-58.]

17. Korshunov Yu.M. Matematicheskie osnovy kibernetiki. Gl. 11. Zadachi teorii raspisaniy i massovogo obsluzhivaniya. Moscow: Energoizdat; 1987. S.437-465. [Korshunov Yu.M. Mathematical Foundations of Cybernetics. Chapter 11. The problems of scheduling and queueing theory. Moscow: Energoizdat; 1987. S.437-465. (in Russ.)]

18. Moiseev N.N. Matematicheskie zadachi sistemnogo analiza. Moscow: Nauka; 1981. 486 s. [Moiseev N.N. Mathematical problems of system analysis. Moscow: Nauka; 1981. 486 p. (in Russ.)] 19. Aygner M. Kombinatornaya teoriya. Moscow: Mir; 1982. [Aygner M. Combinatorial theory. Moscow: Mir; 1982. (in Russ.)]