Редукционные методы восстановления некоторого класса гиперграфов
7
Reduction methods of recovering a certain class of
hypergraphs
© A.A. Gurchenkov
1
, D.S. Kostyanoi
2
, A.V. Mokryakov
2
1
Bauman Mosocw State Technical University, Mosocw, 105005, Russia
2
MATI — Tsiolkovsky Russian State Aviation Technological University, Moscow,
121552, Russia
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.
Keywords:
hypergraphs, realizability of vector into graph, k-complexes.
REFERENCES
[1] Zykov A.A.
Uspekhi matematicheskikh nauk — Advance of Mathematical
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.
