UDC 519.17
REPRESENTATION OF FRAGMENTARY STRUCTURES BY ORIENTED GRAPHS
Abstract. In the paper, the properties of fragmentary structures are investigated and relation between fragmentary structures and marked acyclic oriented graphs with one source is established, also the correspondence of isomorphic fragmentary structure classes with unmarked acyclic oriented graphs of certain type, which are called feasible graphs, is established. The notion of the dimension of a feasible graph and its corresponding isomorphic fragmentary structures is defined. An expression for the lower-bound estimate of the dimension is obtained. A theorem on the properties of feasible graphs is proved. The number of fragmentary structures and classes of isomorphic fragmentary structures of small dimensions is calculated.
Keywords: fragmentary structure, partially ordered set, DAG, hypercube.
FULL TEXT
REFERENCES
- Whitney H. On the abstract properties of linear dependence. American Journal of Mathematics. 1935. Vol. 57, N 3. P. 509–533.
- Bjorner A., Ziegler G. M. Introduction to greedoids. In: White N. (ed.). Matroid Applications Cambridge: Cambridge University Press: Matroid Applications, 1992. P. 284–357.
- Illyev V.P. Problems on independence systems solvable by the greedy algorithm. Diskretnaya matematika. 2009. Vol. 21, Issue 4. P. 85–94.
- Kozin I.V., Kryvtsun O.V. Pinchuk V.P. Evolutionary-fragmentary model of the routing problem. Kibernetika i Sistemnyj Analiz. 2015. Vol. 51, N 3. P. 125–131.
- Kozin I.V., Kryvtsun O.V., Poluga S.I. Fragmentary structure and evolutionary algorithm for rectangular cutting problems. Visnyk Zaporizʹkoho natsionalʹnoho universytetu. Ser. Fizyko-matematychni nauky. 2014. N 2. P. 65–72.
- Kozin I.V., Kryvtsun O.V. Modelling of the single-layer and two-layer routing problems. Upravlyayushchiye sistemy i mashiny. 2016. N 2. P. 58–64.
- Kozin I.V., Borue S.Yu., Kryvtsun O.V. Mathematical model of different type bin packing. Visnyk Zaporizʹkoho natsionalʹnoho universytetu. Ser. Ekonomichni nauky. 2016. N 2. P. 85–92.
- Kryvtsun Ye.V. Evolutionary-fragmentary algorithm of finding the minimal axiom set. Upravlyayushchiye sistemy i mashiny. 2016. N 5. P. 25–31.
- Kozin I.V., Polyuga S.I. About properties of fragmented structure. Visnyk Zaporizʹkoho natsionalʹnoho universytetu. Ser. Fizyko-matematychni nauky. 2012. N 1. P. 99–106.
- Poluga S.I. Fragmental optimization models in problems of covering graphs with typical subgraphs: PhD Thesis in Phys.-math. Sciences, Zaporizhzhia (2015). 140 p. URL: http://phd.znu.edu.ua/page/dis/ 06_2016/Polyuga_dis.pdf.
- Berge C., Théorie des graphes et ses applications [Russian translation]. Moscow: Izd-vo innostrannoy lit, 1962. 320 с.
- Harary F., Palmer E.M., Graphical enumeration [Russian translation]. Moscow: Mir, 1977. 324 p.
