Представлення фрагментарних структур орієнтованими графами / Кривцун О. В. (2019)
Ukrainian

інтернет-адреса сторінки: http://jnas.nbuv.gov.ua/article/UJRN-0000968706
  Кибернетика и системный анализ      А - 2019  /     Випуск (2019, Т. 55, № 2)

Кривцун О. В.
Представлення фрагментарних структур орієнтованими графами

Досліджено властивості фрагментарних структур і встановлено зв'язок між ними та розміченими ациклічними орієнтованими графами з одним джерелом, а також встановлено відповідність класів ізоморфних фрагментарних структур нерозміченим ациклічним орієнтованим графам певного виду, які називаються допустимими графами. Визначено поняття розмірності допустимого графа та відповідних йому ізоморфних фрагментарних структур. Отримано вираз для нижньої оцінки розмірності. Доведено теорему про властивості допустимих графів. Підраховано кількості фрагментарних структур та класів ізоморфних фрагментарних структур малих розмірностей.

 https://doi.org/10.1007/s10559-019-00136-5
 Scopus

Бібліографічний опис:
Кривцун О. В.  Представлення фрагментарних структур орієнтованими графами. Кибернетика и системный анализ. 2019. Т. 55, № 2. С. 163-170. doi: https://doi.org/10.1007/s10559-019-00136-5 URL: http://jnas.nbuv.gov.ua/article/UJRN-0000968706

English  Cybernetics and Systems Analysis   /     Issue (2019, 55 (2))

Kryvtsun O.V.
Representation of fragmentary structures by oriented graphs

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. © 2019, Springer Science+Business Media, LLC, part of Springer Nature.

Keywords: directed acyclic graph, fragmentary structure, hypercube, partially ordered set, Directed graphs, Set theory, Acyclic digraph, Directed acyclic graph (DAG), Hypercube, Lower bounds, Oriented graph, Partially ordered set, Graph theory

Cite:
Kryvtsun O.V. (2019). Representation of fragmentary structures by oriented graphs. Cybernetics and Systems Analysis, 55 (2), 163-170. doi: https://doi.org/10.1007/s10559-019-00136-5 http://jnas.nbuv.gov.ua/article/UJRN-0000968706 [In Ukrainian].

 

Інститут інформаційних технологій НБУВ

+38 (044) 525-36-24
libnas@nbuv.gov.ua
Голосіївський просп., 3, к. 209
м. Київ, 03039, Україна