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

Статья в сборнике "Математические вопросы кибернетики" №11, Москва, 2002
Авторы: Дебрев Е.В.
О различении графов из некоторых семейств посредством безусловных реберных тестов
Аннотация:
Будем рассматривать неориентированные графы без петель и кратных ребер. Предположим, что требуется найти некоторый неизвестный граф X; для этого разрешается выбирать произвольные ребра и для каждого выбранного ребра задать вопрос «принадлежит ли выбранное ребро графу X?» Требуется однозначно определить граф X, задав как можно меньшее число таких вопросов. В данной работе рассматривается решение данной задачи с использованием безусловных тестов, то есть алгоритмов, в которых набор проверяемых ребер фиксирован заранее. Изучены семейства графов, отвечающие разбиениям множества n вершин на два класса эквивалентности; при этом вершины, находящиеся в отношении эквивалентности, соединены ребрами, и, таким образом, классам эквивалентности соответствуют клики графа. Для этих семейств рассмотрены вопросы существования различающего графа, который в данном случае выступает в качестве безусловного теста. Также исследован вопрос вида различающего графа для различных семейств графов.
Ключевые слова:
теория графов, различение графов, безусловные реберные тесты, различающий граф
Язык публикации: русский,  страниц: 16 (с. 177-192)
Направление исследований:
Математические вопросы и теория численных методов
Полный текст на русском языке: Сведения об авторах:
  • Дебрев Евгений Валерьевич,  МГУ им. М.В.Ломоносова, механико-математический факультет