О верхней оценке сложности восстановления результирующего графа, полученного сочленением графов-компонент

Abstract

Анализируются композиции графов из компонент. Композиции представлены правильными и неправильными сочленениями. Предлагается способ и формулы для подсчета верхней оценки сложности восстановления результирующего графа, по известным верхним оценкам сложности восстановления его компонент. Полученные формулы обобщают формулы, полученные ранее для частных видов графов квазиколец и квазициклов.

Аналiзуються композицiї графiв iз компонент. Композицiї представлено правильними та неправильними зчленуваннями. Пропонується спосiб i формули для пiдрахунку верхньої оцiнки складностi вiдновлення результуючого графа, за вiдомими верхнiми оцiнками складностi вiдновлення його компонент. Здобутi формули узагальнюють формули, отриманi ранiше для окремих видiв графiв квазiкiлець i квазiциклiв.

The components compositions of graphs are analyzed. Compositions can be regular and not regular connections. Provides the method and formulas to calculate the upper bound of the resulting graph reconstruction,by the known upper bounds of its components reconstruction. The formulas generalize the formulas obtained earlier for particular types of graphs.