×

Representation of fragmentary structures by oriented graphs. (English. Russian original) Zbl 1418.05068

Cybern. Syst. Anal. 55, No. 2, 313-320 (2019); translation from Kibern. Sist. Anal. 2019, No. 2, 163-170 (2019).
Summary: This paper investigates properties of fragmentary structures and establishes a relation between them and marked acyclic digraphs with one source and also a correspondence between classes of isomorphic fragmentary structures and unmarked acyclic digraphs of certain type, which are called feasible graphs. The concepts of a dimension of a feasible graph and its corresponding isomorphic fragmentary structures are defined. An expression is obtained for the lower-bound estimate of a dimension. A theorem on properties of feasible graphs is proved. The numbers of fragmentary structures and classes of isomorphic fragmentary structures of small dimensions are counted.

MSC:

05C20 Directed graphs (digraphs), tournaments
05C10 Planar graphs; geometric and topological aspects of graph theory
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] H. Whitney, “On the abstract properties of linear dependence,” American Journal of Mathematics, Vol. 57, No. 3, 509-533 (1935). · Zbl 0012.00404
[2] A. Bjorner and G. M. Ziegler, “Introduction to greedoids,” in: N. White (ed.), Matroid Applications, Cambridge University Press (1992), pp. 284-357. · Zbl 0772.05026
[3] V. P. Ilyev, “Problems on independence systems solvable by the greedy algorithm,” Discrete Math. Appl., Vol. 19, Iss. 5, 512-522 (2009). · Zbl 1237.05037
[4] I. V. Kozin, O. V. Kryvtsun, and V. P. Pinchuk, “Evolutionary-fragmentary model of the routing problem,” Cybernetics and Systems Analysis, Vol. 51, No. 3, 432-437 (2015). · Zbl 1327.90262
[5] I. V. Kozin, O. V. Kryvtsun, and S. I. Poluga, “Fragmentary structure and evolutionary algorithm for rectangular cutting problems,” Visnyk of Zaporizhzhya National University, Ser. Physical & Mathematical Sciences, No. 2, 65-72 (2014).
[6] I. V. Kozin and O. V. Kryvtsun, “Modelling of the single-layer and two-layer routing problems,” USiM, No. 2, 58-64 (2016).
[7] I. V. Kozin, S. Yu. Borue, and O. V. Kryvtsun, “Mathematical model of different type bin packing,” Visnyk of Zaporizhzhya National University, Ser. Economical Sciences, No. 2, 85-92 (2016).
[8] Ye. V. Kryvtsun, “Evolutionary-fragmentary algorithm of finding the minimal axiom set,” USiM, No. 5, 25-31 (2016).
[9] I. V. Kozin and S. I. Polyuga, “Properties of fragmentary structures,” Visnyk of Zaporizhzhya National University, Ser. Mathematical Modeling and Applied Mechanics, No. 1, 99-106 (2012).
[10] S. I. Poluga, Fragmental Optimization Models in Problems of Covering Graphs with Typical Subgraphs [in Ukrainian], PhD Thesis in Phys.-math. Sciences, Zaporizhzhya (2015). URL: http://phd.znu.edu.ua/page/dis/06_2016/Polyuga_dis.pdf.
[11] C. Berge, Théorie des Graphes et ses Applications [Russian translation], Izd. Innostr. Lit., Moscow (1962). · Zbl 0214.50804
[12] F. Harary and E. M. Palmer, Graphical Enumeration [Russian translation], Mir, Moscow (1977). · Zbl 0266.05108
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.