Покрытия в числовых графах

Abstract

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

Розглядаються натуральні арифметичні й натуральні модульні графи. Доводяться властивості графів, що розв’язують задачу існування покриття, а також алгоритми знаходження покриття для заданого числового графа. Пропонується розширення алгоритмів, яке дозволяє застосування для арифметичних та модульних графів, а також і для звичайних графів.

Natural arithmetic and natural modular graphs are considered. The graphs qualities for cover problem are solved. The algorithms to allow compute coverability of NA- and NM-graphs were developed. Also algorithms to compute minimal cover for any NA- and NM-graph were made and appropriate statements were proved.