Control Systems and Computers

DOI: https://doi.org/10.15407/usim.2017.01.003

Upr. sist. maš., 2017, Issue 1 (267), pp. 3-18.

UDC 519.816

Nadezhda К. Tymofijeva, Doctor of Engineering Sciences, International Research and Training Centre of Information Technologies and Systems of the NAS and MES of Ukraine, Glushkov ave., 40, Kyiv, 03187, Ukraine, E-mail: tymnad@gmail.com 

About Symmetry of the Combinatorial Sets

Introduction. Symmetry is typical for the various structures (animate and inanimate nature). In combinatorics we can also find symmetry, as the exactness is so approximate, in particular it is common for the combinatorial sets. Its mathematical formulation is conducted with the use of the finite sequence of numbers which are characterized by the  approximate or exact symmetry and are built according to the certain rules. The plane, which passes through the greatest number of sequences, divides it into two parts, the value of which decreases uniformly from the center but not approximate symmetry in the combinatorics mean a finite sequence of numbers, whose values increased to necessarily those of the mirror symmetric. With strict symmetry of the imaginary plane divides the sequence of numbers or the largest number or passes between the two larges. Two parted parts is mirror symmetric.

Purpose. In the article the symmetry of the combinatorial set of configurations is ordered by the certain rules. We don’t focus on the release of symmetric groups and the identification number of their species. We has studied some properties of the symmetric sets.

Results. For combinatorial sets of different types of combinatorial configurations the finite sequence is built, which is defined as the approximate and exact symmetry. For combination without repetition for different values n of these sequences the arithmetical triangle is formed and it is characterized by exact symmetry. For integer partitioning or partitioning n-element set into subsets the finite sequence is created, it is characterized by the approximate symmetry. For the traveling salesman problem the number of identical and different routes are defined. It is shown that in their set they are distributed symmetrically.

Conclusion. The results can be used in solving the combinatorial optimization problems of different classes to analyze changes in the values of the objective function depending on the structure of input data sets based on the combinatorial symmetry configurations and the study of various natural phenomena, which have symmetry and the combinatorial nature.

Keywords: symmetry of combinatorial sets, traveling salesman problem, combinatorial configuration, combinatorial optimization, objective function.

Download full text!

1. Kolmogorov, A.N., Fomin, S.V., 1981. Elementy teorii funkcij i funkcional’nogo analiza, M.: Nauka, 543 p (In Russian).
2. Frid, Je., 1079. Elementarnoe vvedenie v abstraktnuju algebru, M.: Mir, 230 p (In Russian).
3. Kozin, I.V., 2008. Principy simmetrii v teorii prinjatija reshenij, Zaporozh’e, Polіgraf, 164 p.
4. Petuhov, S.V., 1988. Geometrii zhivoj prirody i algoritmy samoorganizacii, M.: Znanie, Serija Matematika, Kibernetika, 6, 48 p. (In Russian).
5. Navarro, Hoakin., 2014. Zazerkal’e. Simmetrija v matematike, Mir matematiki, Tom 17, Moskva, 159 p. (In Russian).
6. Timofeeva, N.K., 2007. Teoretiko-chislovi metodi rozv’yazannya zadach kombinatornoyi optimizatsiyi. Avtoref. dis… dokt. tehn. nauk. In-t kibernetiki im. V.M. Glushkova NAN Ukrayini, Kiyiv, 32 p (In Ukrainian).
7. Timofeeva, N.K., 2010. “Rekurentno-periodichniy metod dlya generuvannya kombinatornih konfiguratsiy”. Kombinatorni konfiguratsiyi ta yih zastosuvannya: Materiali desyatogo Mizhvuzivskogo naukovo-praktichnogo seminaru (15-16 zhovtnya 2010), Kirovograd: Kirovogr. tehn. un-t, pp. 138–141 (In Ukrainian).
8. Timofeeva, N. K., 2004. “Ob osobennostjah formirovanija i uporjadochenija vyborok”. Kibernetika i sistem. analiz, 3, pp. 174–182. (In Russian).
9. Timofeeva, N.K., 2002. “O nekotoryh svojstvah razbienij mnozhestva na podmnozhestva”. Upravlausie sistemy i masiny, 5, pp. 6–23 (In Russian).
10. Timofeeva, N.K., 1990. O gamil’tonovom cikle i zadache kommivojazhera, Kiev, 29 p. Dep.v VINITI 14.11.90, 5742-V90 (In Russian).
11. Timofeeva, N.K., 1998. “Uporjadochenie mnozhestva znachenij argumenta celevoj funkcii v kombinatornoj optimizacii”, Kibernetika i sistem. analiz, 6, pp. 78–88 (In Russian).
12. Timofіjeva, N.K., 2014. “Pro simetrії kombіnatornih mnozhin ta bіologіchnih form”.System Analysis and Information Technologies, 16-th International Conference SAIT’2014, Kyiv, Ukraine, May 26-30, 2014. Proceedings of Institute for Applied System Analysis of National Technical University of Ukraine, Kyiv Politechnic Institute, Kyiv, Ukraine, pp. 160–161 (In Ukrainian).

Received 11.01.2017