Тестовые задачи на графах

Настоящая диссертация посвящена изучению безусловных тестов, различающих графы из заданных семейств.

В общем виде задача о построении табличного теста, по-видимому, была поставлена С. В. Яблонским [8]. В такой постановке имеется заданное заранее конечное множество идентифицируемых (искомых) объектов, например, определённого характера неисправности некоторой электрической схемы, а также конечный набор допустимых элементарных проверок. Тестом называется всякий такой поднабор элементарных проверок, что, выполнив все проверки в поднаборе, по полученным данным можно однозначно идентифицировать любой объект из заданного множества. Представляет интерес поиск тестов наименьшего объёма (т. е. содержащих наименьшее возможное количество элементарных проверок), а также описание всех тестов.

Термин «табличный тест» связан с тем, что значения элементарных проверок на объектах можно выписать в виде элементов таблицы, строки которой поставлены в соответствие объектам, а столбцы проверкам, а на пересечении столбца р со строкой х стоит значение проверки р на объекте х. Тесты — это наборы столбцов такие, что если из таблицы исключить все остальные столбцы, то в ней не окажется двух одинаковых строк, объём теста — это число столбцов в нём.

Теория тестов получила дальнейшее развитие в работах А. Е. Андреева, Е. В. Дюковой, Ю. И. Журавлёва, А. Д. Коршунова, В. Н. Носкова, Н. П. Редькина, В. А. Слепяна, Н. А. Соловьёва и самого С. В. Яблонского. Обзор некоторых результатов многочисленных исследований можно найти в статье С. В. Яблонского [10], а также в монографии Н. А. Соловьёва [7].

Подчеркнём, что при рассмотрении табличных тестов, речь, как правило, идёт о тестах безусловных, т. е. для идентификации объекта выполняются все элементарные проверки теста (безразлично в каком порядке), а потом по набору значений этих проверок находится искомый объект, единственный по определению теста. Некоторыми авторами рассматривались и задачи другого типа — задачи об условных тестах (также используется термин «задачи комбинаторного поиска»).

Неформально под условным тестом понимается алгоритм, который шаг за шагом выполняет элементарные проверки, причём выбор проверки для следующего шага, вообще говоря, зависит от информации, полученной на предыдущих шагах. Результатом работы такого алгоритма, как и в случае безусловного теста, является однозначно идентифицированный объект. Но, в отличие от безусловного, условный тест может выполнять различное число элементарных проверок для идентификации различных объектов. В качестве меры сложности условного теста, аналогичной объёму безусловного теста, как правило, выбирают число выполненных элементарных проверок (длина теста) в худшем случае, либо в среднем (и то и другое — по всем искомым объектам).

Определения и некоторые результаты в отношении условных тестов можно найти в монографии [11], см. также [1] и [4].

В настоящей работе речь идёт о безусловных тестах, которые строятся для семейств конечных неориентированных графов без петель и кратных рёбер. Искомыми объектами в соответствующих задачах являются графы, принадлежащие заданным семействам, а элементарные проверки устанавливают, принадлежит ли искомому графу некоторое заданное ребротакие проверки называются рёберными.

Близкие задачи изучались различными авторами.

Построению условных тестов, идентифицирующих граф посредством рёберных тестов, посвящён раздел монографии М. Айгнера [11, раздел 3.5]. В нём установлен вид условных рёберных тестов наименьшей длины в худшем случае для следующих семейств графов на фиксированных п нумерованных вершинах: семейство деревьев, семейство максимальных паросочетаиий, семейство полных звёзд. Приводится общий метод построения нижних так называемых «жадных» оценок, дающий, однако, для многих семейств лишь оценку, точную по порядку величиныприводимая в книге оценка для семейства всех гамильтоновых циклов на п нумерованных вершинах получена таким способом.

Другими авторами рассматривались элементарные проверки более общего, по сравнению с рёберными, вида [13], [14, глава 2]. В указанных работах рассматриваются условные тесты для семейств конечных неориентированных графов без петель и кратных рёбер на п нумерованных вершинах. Элементарные проверки соответствуют всевозможным кликам на этих вершинах (как вариант, кликам, содержащим не более t вершин). В одной из моделей элементарная проверка устанавливает, имеет ли искомый граф хоть одно общее ребро с соответствующей кликой. В другой модели проверка выдаёт количество рёбер, общих у клики и искомого графа. Для длины тестов в худшем случае в указанных работах установлены оценки, точные по порядку величины.

Диссертация состоит из введения, семи глав и списка литературы.

1. Альсведе Р., Вегенер И. Задачи поиска. М.: Мир, 1982.

2. Баранов В. И., Стечкин Б. С. Экстремальные комбинаторные задачи и их приложения. М.: Наука, 1989.

3. Емеличев В. А., Мельников О. И., Сарванов В. И., Тышкевич Р. И. Лекции по теории графов. М.: Наука, 1990.

4. Мошков М. Ю. Деревья решений. Теория и приложения. Издательство Нижегородского университета, Нижний Новгород, 1994.

5. Нечипорук Э. И. О топологических принципах самокорректирования // Проблемы кибернетики. Вып. 21. М.: Наука, 1969. С. 5−102.

6. Оре. О. Теория графов. М.: Наука, 1980.

7. Соловьев Н. А. Тесты (теория, построение, применение). Новосибирск: Наука, 1978.

8. Чегис И. А., Яблонский С. В. Логические способы контроля электрических схем // Тр. МИАН СССР. 1958. — 51. — С. 270−360.

9. Эрдёш П., Спенсер Дж. Вероятностные методы в комбинаторике. М.: Мир, 1976. ¦

10. Яблонский С. В. Некоторые вопросы надёжности и контроля управляющих систем // Математические вопросы кибернетики. Вып. 1. — М.: Наука, 1988. С. 5−25.

11. Aigner М. Combinatorial Search.— Stuttgart: TeubnerChichester et al.: Wiley, 1988.

12. Ford G.W., Uhlenbeck G.E. Lectures in statistical mechanics. Providence, R.I., 1963. (Имеется перевод: Уленбек Дж., Форд Дж. Лекции по статистической механике. М.: Мир, 1965.

13. Grebinski V. and Kucherov G. Optimal Query Bounds for Reconstructing a Hamiltonian Cycle in Complete Graphs, Proceedings of 5th Israeli Symposium on Theory of Computing and Systems. IEEE Press, 1997, pp. 166−173.

14. Grebinski V. Recherche Combinatoire: Problemes de Pesage, Reconstruction de Graphes et Applications. Diplome de Doctorat de l’Universitd Henri Poincare, 1998. Публикации автора по теме диссертации.

15. Дебрев Е. В. Об одной задаче комбинаторного поиска // Дискретная математика. 2002. Т. 14, вып. 3. С. 8−17.

16. Дебрев Е. В. О различении графов из некоторых семейств посредством безусловных рёберных тестов // Математические вопросы кибернетики. Вып. 11. М.: Наука. Физматлит, 2002. С. 177−192.

17. Дебрев Е. В. О безусловных реберных тестах для некоторых семейств графов // Дискретный анализ и исследование операций. Серия 1. 2003. Т. 10, № 4. С. 8−30.