RUS  ENG
Полная версия
ЖУРНАЛЫ // Дискретная математика // Архив

Дискрет. матем., 2004, том 16, выпуск 3, страницы 118–140 (Mi dm167)

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

З. С. Ложкина


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

УДК: 519.95

Статья поступила: 06.11.2003

DOI: 10.4213/dm167


 Англоязычная версия: Discrete Mathematics and Applications, 2004, 14:4, 385–407

Реферативные базы данных:


© МИАН, 2024