Об оптимальных точных покрытиях графа в классе слабо плотных базисов

Рассматривается задача о покрытии неориентированного связного графа без петель и кратных ребер графами из произвольных конечных базисов. Вводятся понятия сложности покрытия, сложности графа и функции Шеннона. В зависимости от асимптотики функции Шеннона выделены два класса базисов — почти плотные и слабо плотные. Для класса слабо плотных базисов и некоторого специального его подкласса найдены методы построения оптимальных точных покрытий графа двудольными базисными графами и получены оценки сложности таких покрытий. Данные методы основаны на алгоритмах оптимального точного покрытия $(0,1)$-матриц произвольными $(0,1)$-матрицами, а также на соответствии между покрытием $(0,1)$-матрицы и покрытием графа двудольными графами.