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

• Автор: Дебрев, Евгений Валерьевич
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2004
• Место защиты: Москва
• Количество страниц: 90 с.

1 Основные определения и простейшие факты
1. Простейшие свойства различающих графов
2. Некоторые простейшие семейства графов
2 Регулярные семейства графов
1. Понятие регулярности
2. Одно комбинаторное неравенство
3. Классы подобия вершин в графах
3 Семейства /Ср,п_р и со-1Ср,п-р
1. Определение семейств К.п и /Со
2. Семейства К,п и
3. Семейства 1Срп-р
4. Оценки Ь(-) для подсемейств К.п
4 Семейства О? и со-2"
5 Семейства, состоящие из графов с не более, чем двумя
классами подобия вершин
6 Семейства графов А>разбиений
1. Матрицы пересечений
2. Верхняя и нижняя оценки
7 Гамильтоновы циклы
1. Свойства коразличающих графов
2. Характеризация всех коразличающих графов
3. Максимальные коразличающне графы
Список литературы

Настоящая диссертация посвящена изучению безусловных тестов, различающих графы из заданных семейств.
В общем виде задача о построении табличного теста, по-видимому, была поставлена С. В. Яблонским [8]. В такой постановке имеется заданное заранее конечное множество идентифицируемых (искомых) объектов, например, определённого характера неисправности некоторой электрической схемы, а также конечный набор допустимых элементарных проверок. Тестом называется всякий такой поднабор элементарных проверок, что, выполнив все проверки в поднаборе, по полученным данным можно однозначно идентифицировать любой объект из заданного множества. Представляет интерес поиск тестов наименьшего объёма (т. е. содержащих наименьшее возможное количество элементарных проверок), а также описание всех тестов.
Термин «табличный тест» связан с тем, что значения элементарных проверок на объектах можно выписать в виде элементов таблицы, строки которой поставлены в соответствие объектам, а столбцы проверкам, а на пересечении столбца р со строкой х стоит значение проверки р на объекте х. Тесты — это наборы столбцов такие, что если из таблицы исключить все остальные столбцы, то в ней не окажется двух одинаковых строк, объём теста — это число столбцов в нём.
Теория тестов получила дальнейшее развитие в работах А. Е. Андреева, Е. В. Дюковой, Ю. И. Журавлёва, А. Д. Коршунова, В. Н. Носкова,
Н. П. Редькина, В. А. Слепяна, H.A. Соловьёва и самого С. В. Яблонского. Обзор некоторых результатов многочисленных исследований можно найти в статье С. В. Яблонского [10], а также в монографии H.A. Соловьёва [7].
Подчеркнём, что при рассмотрении табличных тестов, речь, как правило, идёт о тестах безусловных, т.е. для идентификации объекта выполняются все элементарные проверки теста (безразлично в каком порядке), а потом по набору значений этих проверок находится искомый объект, единственный по определению теста. Некоторыми авторами рас-

сматривались и задачи другого типа — задачи об условных тестах (также используется термин «задачи комбинаторного поиска»).
Неформально под условным тестом понимается алгоритм, который шаг за шагом выполняет элементарные проверки, причём выбор проверки для следующего шага, вообще говоря, зависит от информации, полученной на предыдущих шагах. Результатом работы такого алгоритма, как и в случае безусловного теста, является однозначно идентифицированный объект. Но, в отличие от безусловного, условный тест может выполнять различное число элементарных проверок для идентификации различных объектов. В качестве меры сложности условного теста, аналогичной объёму безусловного теста, как правило, выбирают число выполненных элементарных проверок (длина теста) в худшем случае, либо в среднем (и то и другое — по всем искомым объектам).
Определения и некоторые результаты в отношении условных тестов можно найти в монографии [11], см. также [1] и [4].
В настоящей работе речь идёт о безусловных тестах, которые строятся для семейств конечных неориентированных графов без петель и кратных рёбер. Искомыми объектами в соответствующих задачах являются графы, принадлежащие заданным семействам, а элементарные проверки устанавливают, принадлежит ли искомому графу некоторое заданное ребро; такие проверки называются рёберными.
Близкие задачи изучались различными авторами.
Построению условных тестов, идентифицирующих граф посредством рёберных тестов, посвящён раздел монографии М. Айгнера [11, раздел 3.5). В нём установлен вид условных рёберных тестов наименьшей длины в худшем случае для следующих семейств графов на фиксированных п нумерованных вершинах: семейство деревьев, семейство максимальных паросочетаний, семейство полных звёзд. Приводится общий метод построения нижних так называемых «жадных» оценок, дающий, однако, для многих семейств лишь оценку, точную по порядку величины; приводимая в книге оценка для семейства всех гамильтоновых циклов на п нумерованных вершинах получена таким способом.
Другими авторами рассматривались элементарные проверки более общего, по сравнению с рёберными, вида [13], [14,
глава 2]. В указанных работах рассматриваются условные тесты для семейств конечных неориентированных графов без петель и кратных рёбер на п нумерованных вершинах. Элементарные проверки соответствуют всевозможным кликам на этих вершинах (как вариант, кликам, содержащим не более і вершин). В одной из моделей элементарная проверка устанавливает, имеет ли искомый граф хоть одно общее ребро с соответствующей кликой. В другой модели проверка выдаёт количество рёбер, общих у клики и ис-

Покажем, что каким бы ни оказалось значение р, выполнено неравенство 2L(/CPi„_p) ^ гг—1. Согласно теореме 7 выполнено равенство L(KPin-p) = п — к(п,р), где величина к(п,р) полностью определяется условиями, указанными в той же теореме. Проверим, что 2(п — к(п,р)) ^ п— 1 во всех четырёх случаях в формулировке теоремы 7.
1. Если 2р ^ п ^ Зр + 2, то 2(п — к(п, р)) ^ 2(п — 2), что при п ^ 3 не меньше, чем п — 1.
2. Если Зр + 3 ^ п ^ 4р + 2, то п ^ 6 (поскольку р ^ 1) и тогда 2(n — к(п,р)) 2(п — 3) > гг — 1.
3. Если п ^ 4р + 3 и р чётно, то справедливы неравенства:
2(п — к(п,р)) > 2(п — |n/(p + 1)J) ^ 2(п — (n + 1)/2) = п — 1.
4. Если тг ^ 4р + 3 и р нечётно, то справедливы неравенства:
2(п — к(п,р)) > 2(п — [(и + 2)/(р+ 2)J) ^ 2(п — (п+ 1)/2) —п — 1.
Итак, при любых п, р, где п ^ 3, 1 ^ р < [п/2j, выполнено неравен-• ство:
т > L(£p,n-p) >
Лемма доказана.