Reduction methods of recovering a certain class of hypergraphs
Authors: Gurchenkov A.A., Kostianoi D.S., Mokriakov A.V.
Published in issue: #6(30)/2014
DOI: 10.18698/2308-6033-2014-6-1294
Category: Information technology
The main purpose of the article is to study methods for obtaining some classes of hypergraphs from a given vector. For each class we present an algorithm of constructing hypergraph of this class from an arbitrary vector. If the hypergraph construction is impossible, the algorithm determines how much the vector should be diminished in order to allow it. In planar graphs an arc is drawn between two points. If dimension of space is increased by one unit, a plane is drawn through three points and hyperarc is a triangle. A priori we take four classes of hypergraphs. In the first case there are no hyperedges,and all of them have the same dimension. In the second case hyperedges may have different dimensionality, in other words, nodes can be incident to triangles and arcs. In the third case multiple hyperarcs are considered. In the fourth case hyperedges of different dimensions of the spaces are possible, by analogy with the second cas.
References
[1] Zykov A.A. Uspekhi matematicheskikh nauk - Advance of Mathematica/ Sciences, 1972, iss. 6 (180), pp. 3-7.
[2] Kostyanoi D.S. Model’ sbalansirovannogo raspredeleniya resursov v usloviyakh ogranichennosti [The model of balanced allocation of resources in limited conditions]. Nauchnye trudy mezhdunarodnoi konferentsii "XXXIX Gagarinskie chteniya" [Scientific proceedings of the International Conference "XXXIX Gagarin readings"], Moscow, 2013, pp. 69-70.
[3] Khakimi S.P. O realizuemosti mnozhestva tselykh chisel stepenyami vershin grafa [On the realizability of the set of integers by degrees of vertices]. Moscow, Mir Publ., Kibernetika coll. pap., iss. 2, 1966, pp. 40-53.
[4] Mironov A.A. Uspekhi Matematicheskikh Nauk - Advance in Math. Sci., vol. XXII, no. 6, 1977, pp. 231-232.
[5] Mironov A.A., Tsurkov V.I. Journal of Computer and Systems Sciences International, 1992, vol. 30, no. 5, pp. 114-119.
[6] Mironov A.A. O realizuemosti naborov chisel v graf i svoistva grafov s zadannym naborom stepenei vershin [On the realizability of sets of numbers in the graph and properties of graphs with a given set of vertex degrees]. Tr. Gor. GU, 1981, pp. 76-97.
[7] Mironov A.A. Doklady Akademii Nauk Rossii - RAS Reports, 1996, vol. 351, no. 4.
[8] Mokryakov A.V. Izvestiya RAN. Teoriya i Sistemy Upravleniya - Proceedings of the Russian Academy of Sciences. Theory and Control Systems, 2011, vol. 5, pp. 53-59.
[9] Mironov A.A., Mokryakov A.V., Sokolov A.A. Applied and Computational Mathematics, 2007, vol. 6, no. 1, pp. 58-68.
[10] Mironov A.A., Mokryakov A.V. Trudy ISA RAN. Dinamika Neodnorodnykh Sistem - Proceedings of ISA RAS. Dynamics of Heterogeneous Systems, Yu.S. Popkov, ed. 2006. no. 10(1), pp. 178-186.
[11] Mokryakov A.V., Tsurkov V.I. Reconstructing 2-complexes by a nonnegative integer-valued vector. Automation and Remote Control, 2011, vol. 72, no. 12, pp. 2541-2552.
[12] Mironov A.A., Tsurkov V.I. Doklady Akademii Nauk - RAS Reports, 1994, vol. 336, no. 1, pp. 35-38.
[13] Mironov A.A., Levkina T.A., Tsurkov V.I. Minimax Estimations of Arc Weights in Integer Networks with Fixed Node Degrees. Applied and Computational Mathematics, 2009, vol. 8, no. 2, pp. 216-226.
[14] Mironov A.A., Tsurkov V.I. Doklady Akademii Nauk - RAS Reports, 1996, vol. 346, no. 2, pp. 168-171.
[15] Mironov A.A., Tsurkov V.I. Minimax under Nonlinear Transportation Constraints. Doklady Mathematics, 2001, vol. 64, no. 3, pp. 351-354.
[16] Mironov A.A., Tsurkov V.I. Open transportation models with a minimax criterion. Doklady Mathematics, 2001, vol. 64, no. 3, pp. 374-377.