Головная страница ИПМ Библиотеки, издания  •  Поиск публикаций  English 
Публикация

Статья в сборнике "Математические вопросы кибернетики" №15, Москва, 2006
Авторы: Дебрев Е.В.
О безусловных рёберных тестах для регулярных семейств графов
Аннотация:
Рассматриваются безусловные рёберные тесты для неориентированных графов без петель и кратных рёбер, заданных на фиксированном конечном множестве нумерованных вершин. Для каждого регулярного семейства, состоящего из графов с не более чем двумя классами подобия вершин, получены верхние и нижние оценки минимального объёма такого теста, различающиеся не более чем в 8 раз. С учётом ранее полученных результатов, для всех регулярных семейств графов на n нумерованных вершинах найден порядок по n роста минимального объёма безусловного рёберного теста.
Ключевые слова:
безусловный рёберный тест, регулярное семейство графов
Язык публикации: русский,  страниц: 16 (с. 183-198)
Направление исследований:
Математические вопросы и теория численных методов
Полный текст на русском языке: Сведения об авторах:
  • Дебрев Евгений Валерьевич,  МГУ им. М.В.Ломоносова, механико-математический факультет