Статья в сборнике "Математические вопросы кибернетики" №15, Москва, 2006
Авторы:Дебрев Е.В.
О безусловных рёберных тестах для регулярных семейств графов
Аннотация:
Рассматриваются безусловные рёберные тесты для неориентированных графов без петель и кратных рёбер, заданных на фиксированном конечном множестве нумерованных вершин. Для каждого регулярного семейства, состоящего из графов с не более чем двумя классами подобия вершин, получены верхние и нижние оценки минимального объёма такого теста, различающиеся не более чем в 8 раз. С учётом ранее полученных результатов, для всех регулярных семейств графов на n нумерованных вершинах найден порядок по n роста минимального объёма безусловного рёберного теста.
Ключевые слова:
безусловный рёберный тест, регулярное семейство графов
