Будем рассматривать неориентированные графы без петель и кратных ребер. Предположим, что требуется найти некоторый неизвестный граф X; для этого разрешается выбирать произвольные ребра и для каждого выбранного ребра задать вопрос «принадлежит ли выбранное ребро графу X?» Требуется однозначно определить граф X, задав как можно меньшее число таких вопросов. В данной работе рассматривается решение данной задачи с использованием безусловных тестов, то есть алгоритмов, в которых набор проверяемых ребер фиксирован заранее. Изучены семейства графов, отвечающие разбиениям множества n вершин на два класса эквивалентности; при этом вершины, находящиеся в отношении эквивалентности, соединены ребрами, и, таким образом, классам эквивалентности соответствуют клики графа. Для этих семейств рассмотрены вопросы существования различающего графа, который в данном случае выступает в качестве безусловного теста. Также исследован вопрос вида различающего графа для различных семейств графов.

теория графов, различение графов, безусловные реберные тесты, различающий граф

Математические вопросы и теория численных методов