Тестовые задачи на графах тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ . ИМЕНИ М.В.ЛОМОНОСОВА

МЕХАНИКО-МАТЕМАТИЧЕСКИЙ ФАКУЛЬТЕТ

На правах рукописи УДК 519.7

Дебрев Евгений Валерьевич

ТЕСТОВЫЕ ЗАДАЧИ НА ГРАФАХ

01.01.09 — дискретная математика и математическая кибернетика

АВТОРЕФЕРАТ диссертации на соискание учёной степени кандидата физико-математических наук

МОСКВА - 2004

Работа выполнена на кафедре дискретной математики Московского государственного университета им М. В. Ломоносова.

Научный руководитель: Официальные оппоненты:

Ведущая организация:

доктор физико-математических наук профессор О. М. Касим-Заде. доктор физико-математических наук профессор Л. А. Шоломов; кандидат физико-математических наук В. В. Кочергин. Институт математики им. С. Л. Соболева СО РАН.

Защита диссертации состоится 16 апреля 2003 г. в 16 часов 15 минут на заседании диссертационного совета Д.501.001.84 в Московском государственном университете им. М. В. Ломоносова по адресу 119992, ГСП-2, Москва, Ленинские горы, МГУ им. М. В. Ломоносова (Главное здание, аудитория 14-08).

С диссертацией можно ознакомиться в библиотеке механико-математического факультета МГУ (Главное здание, 14 этаж).

Автореферат разослан 16 марта 2003 г.

Учёный секретарь диссертационного совета Д.501.001.84 в МГУ доктор физико-математических наук, профессор

В. Н. Чубариков

Общая характеристика работы

Актуальность темы

Становление теории тестов как раздела дискретной математики приходится на конец 50-х годов XX века и связано прежде всего с именем С. В. Яблонского, который, по-видимому, первым поставил в общем виде задачу о построении табличных тестов минимального объёма1. Дальнейшее развитие этой теории в работах А. Е. Андреева, Е. В. Дюковой, Ю.И. Журавлёва, А. Д. Коршунова, В. Б. Кудрявцева, М.Ю. Мошкова, В.Н. Носкова, Н.П. Редькина, В. А. Слепяна, Н. А. Соловьёва и многих других исследователей принесло множество результатов; обзор некоторых из них можно найти в статье С. В. Яблонского2.

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

Если последовательность элементарных проверок, выполняемых тестом, всегда одна и та же, т. е. не зависит от идентифицируемого объекта, то такой тест называется безусловным] в противном случае тест называется условным. Количество элементарных проверок, выполненных тестом, называется объёмом теста.

Задачи о построении условных тестов, рассматривались различными авторами; многочисленные результаты в этой области можно найти в книгах М. Айгнера3, Р. Альсведе и И. Вегенера4, М.Ю. Мошкова5.

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

2Яблонский C.B. Некоторые вопросы надёжности и контроля управляющих систем // Математические вопросы кибернетики. Вып. 1. — М.: Наука, 1988. — С. 5-25. 3Aigner M. Combinatorial Search. Wiley, 1988. 4Альсведе P., Вегенер И. Задачи поиска. — M.: Мир, 1982.

6Мошков М.Ю. Деревья решений. Теория и приложения. — Нижний Новгород:

РОС НАЦИОНАЛЬНА»j

_ библиотека Г

СЯстсрбуфГ- » * 08 Щ

Задачи о построении тестов, где в качестве семейства объектов V выбирается то или иное семейство графов, имеют относительно короткую историю. Как правило в задачах такого рода функции единичных проверок доставляют некоторую «теоретико-графовую» информацию: принадлежность того или иного ребра искомому графу, или количество рёбер в пересечении искомого графа с некоторым заданным. Отличительной особенностью теоретико-графовых тестовых задач является то, что как правило семейства графов определяются в инвариантных терминах (с точностью до изоморфизма). Такие семейства графов — содержащие вместе с каждым графом и все ему изоморфные — называются регулярными.

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

В. Гребинским и Г. Кучеровым6'7 были получены результаты (оценки, точные по порядку величины) для объёма условных тестов, в которых единичная проверка выясняет, имеет ли искомый граф хотя бы одно ребро в пересечении с некоторой кликой (такая проверка, как и однорёберная, даёт лишь ответ «да» или «нет»), а также для тестов, в которых значением единичной проверки является число рёбер в пересечении некоторой клики с искомым графом.

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

Цель работы

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

Методы исследования

В диссертации используются методы теории графов, в том числе экс-

Изд-во Нижегородского гос. ун-та, 1994.

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

7V. Grebinski, Recherche Combinatoire: Problemes de Pesage, Reconstruction de Graphes et Applications, Dipl6me de Doctorat de l'Universite Henri Poincare, 1998.

тремальной теории графов, комбинаторного анализа, теории тестов. Научная новизна

Все основные результаты диссертации являются новыми. В диссертации получены следующие основные результаты.

1. На основе введённого в диссертации понятия подобия вершин графа построена классификация всех графов по числу классов подобия вершин; дано полное описание графов, имеющих не более двух классов подобия.

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

Для всех регулярных семейств Qn, состоящих из графов с не более, чем двумя классами подобия вершин, установлены верхние и нижние оценки объёма безусловного рёберного теста, различающиеся при любом п не более, чем в 8 раз.

3. Изучены некоторые конкретные регулярные семейства графов, представляющие самостоятельный интерес. Для семейств Kv<n-pt ¡Сп,

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

4. Для регулярного семейства графов "Нп, состоящего из всех гамиль-тоновых циклов на п вершинах, найдено точное значение объёма минимального теста, равное получена полная характеризация всех тестов, построены в явном виде минимальные тесты.

Теоретическая и практическая ценность

Работа носит теоретический характер. Результаты диссертации могут быть использованы в дальнейших исследованиях в области задач комбинаторного поиска, теории тестов и других разделах дискретной математики и математической кибернетики. Результаты диссертации могут

быть полезны специалистам Московского государственного университета им. М. В. Ломоносова, Института прикладной математики им. М. В. Келдыша РАН, Вычислительного центра им. А. А. Дородницына РАН, Института математики им. С. Л. Соболева СО РАН, Нижегородского государственного университета им. Н.И. Лобачевского, Новосибирского государственного университета, Санкт-Петербургского государственно -го университета.

Апробация работы

Результаты диссертации докладывались на XXII Конференции молодых ученых механико-математического факультета МГУ (Москва, апрель 2000 г.), на XI Межгосударственной школе-семинаре «Синтез и сложность управляющих систем» (Нижний Новгород, ноябрь 2000 г.), на XIV Международной школе-семинаре «Синтез и сложность управляющих систем» (Нижний Новгород, октябрь 2003 г.), на семинаре «Математические вопросы кибернетики» под руководством академика РАН О. Б. Лупанова (декабрь 1999 г., февраль 2003 г., ноябрь 2003 г.), на семинаре «Синтез управляющих систем» под руководством академика РАН О. Б. Лупанова (ноябрь-декабрь 2002 г.), на 28 Австралазийской конференции по комбинаторной математике и комбинаторным вычислениям (The 28th Australasian Conference on Combinatorial Mathematics and Combinatorial Computing, Мельбурн, Австралия, декабрь 2003 г.).

Публикации

Основные результаты диссертации опубликованы в 5 работах автора, перечисленных в конце автореферата.

Структура и объём работы

Диссертация состоит из введения и семи глав, разбитых на разделы. Текст диссертации изложен на 91 странице. Список литературы содержит 19 наименований.

Краткое содержание диссертации

Во Введении содержится постановка задач, рассматриваемых в работе, обзор результатов, полученных другими авторами, и краткое изложение основных результатов диссертации.

В главе 1 приводятся основные определения, не являющиеся общеизвестными, вводятся обозначения и приводятся доказательства простейших утверждений, используемых в диссертации.

Задача о построении тестов в диссертации рассматривается для семейств графов, заданных на множестве из п нумерованных вершин, которое обозначается через V^,.

б

Для семейства Qn неориентированных графов без петель и кратных рёбер, заданных на Vn, вводится понятие различающего графа, т. е. графа, образованного рёбрами теста; его дополнение называется коразлича-ющим графом для семейства Qn. Тест (различающий граф) для семейства Qn называется минимальным, если он имеет минимальный возможный объём. Для объёма (числа рёбер) минимального теста для семейства графов Qn вводится обозначение L(Q„).

Для семейства графов, образованного дополнениями графов семейства Qn, вводится специальное обозначение:

co-Qn = {G:Ge Qn).

В диссертации изучаются тесты для регулярных, т. е. замкнутых относительно изоморфизма, семейств графов.

В главах 2-5 диссертации устанавливаются точные по порядку величины оценки объёма'Минимальных тестов для всех регулярных семейств графов и строятся соответствующие этим оценкам тесты.

В главе 2 вводится понятие регулярного семейства графов и доказываются некоторые утверждения для таких семейств.

Вершины и и v графа G называются подобными, если граф, полученный их перестановкой, совпадает с G. Отношение подобия вершин в графе есть отношение эквивалентности; классы эквивалентности по отношению подобия вершин называются классами подобия вершин в G.

Пусть и и v — две различные вершины графа G. Множество вершин D(u,v) = 5(u)AS(u)\{u,u}, где через S(x) обозначена окрестность вершины х (множество вершин, смежных с гг), а через Д — симметрическая разность множеств, называется множеством дисбаланса вершин и и v, а его мощность d(u,v) = \D(u,v)\ — дисбалансом этих вершин. При этом, по определению для любой вершины и множество D(u,u) пусто, a d(u,u) = 0. Вершины и и v графа G подобны тогда и только тогда, когда d(u,v) = 0.

Введены специальные обозначения для некоторых важных семейств графов. Семейство графов на V^,, каждый из которых есть объединение двух непересекающихся по вершинам клик: р-клики и (п—р)-клики, обозначается через /Ср)П_р (1 ^ р ^ n — 1). Семейство графов на VJ,, каждый из которых есть объединение ¿-клики и п — t изолированных вершин, обозначается через

В диссертации доказана следующая теорема.

Теорема 1. Пусть граф G имеет не менее трёх классов подобия вершин. Тогда для всякого регулярного семейства Qn, содержащего G, вы-

полнено неравенство:

Таким образом, каждое регулярное семейство относится к одному из двух типов: к первому относятся те семейства, в которых содержится по крайней мере один граф с тремя или более классами подобия вершин, а ко второму — семейства, состоящие только из графов, имеющих не более двух классов подобия вершин.

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

Оставшаяся часть главы 2 посвящена описанию графов, из которых состоят семейства второго типа; изучению тестов для таких семейств посвящены главы 3-5. Таким образом в диссертации рассмотрены все регулярные семейства графов.

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

Теорема 2. Граф на п вершинах имеет не более двух классов подобия тогда и только тогда, когда он является графом одного из следующих видов:

1) полный граф (один класс подобия);

2) пустой граф (один класс подобия);

3) граф из семейства г<3е 1 ^ р ^ п — 1 (два класса подобия);

4) граф из семейства со-КРгП-Р1 где 1 ^ р ^ п — 1 (два класса подобия);

5) граф из семейства 2™, где 2 ^ Ь ^ п — 2 (два класса подобия);

6) граф из семейства со-0%, где 2 ^ 4 ^ п — 2 (два класса подобия).

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

Различающий граф для семейства является таковым и для семейства со-Оп, которое состоит из дополнений графов семейства Qn. Поэтому шесть видов графов в утверждении теоремы 2 разбиваются на три пары, которые изучаются по отдельности.

Если семейство не содержит иных графов, кроме п-клики и пустого графа на п вершинах (пункты 1 и 2 теоремы 2), то построение минимальных рёберных тестов для такого семейства тривиально и в отдельном исследовании не нуждается.

Глава 3 диссертации посвящена изучению минимальных тестов для семейств ¡Ср<п-р и со-К,РъП-р (п ^ 2, 1 ^ р ^ п — 1), указанных в пунктах 3 и 4 теоремы 2. Вместе с этими семействами при каждом п ^ 2 рассматриваются следующие семейства:

= и {*„}.

Семейства дополнений со-/Ср1П_р) со-Ю1 и со-Кд отдельно не рассматриваются, т.к. результаты, полученные для семейств переносятся на них автоматически.

Следующая теорема, доказанная в диссертации, характеризует минимальные различающие графы для семейства (при каждом ).

Теорема 3. Минимальные различающие графы для /СЦ — это в точности деревья на п вершинах.

Такая характеризация немедленно приводит к точному значению для объёма минимального теста, как для семейства /Сд, так и для семейства

Теорема 4. При всех п^Ъ выполнено:

Следует отметить, что семейство /Сд содержит ровно 2П-1 графов, поэтому /Сд содержит максимальное число графов, которое дерево на

вершинах способно различить, или, что то же самое, для семейства дерево на п вершинах имеет минимально возможное, исходя из информационных соображений, количество рёбер.

В диссертации доказана теорема, которая даёт значение величины £,(•) для семейства /СЦ и со-КЦ, которое содержит все графы, описанные в пунктах 1-4 теоремы 2.

Теорема 5. При всяком п^З

ЦЯЦ и со-К%) = п. (1)

Семейства оказываются значительно более трудными для изу-

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

В диссертации установлена следующая характеризация различающих графов для семейств

Теорема 6. П )П ^ 2, 1 ^ р ^ п/2. и граф Я является различающим для семейства ¡СР)П..Р, то в зависимости от числа связных компонент Я выполнено одно из следующих трёх утверждений.

1) Граф Я содержит ровно одну связную компоненту (Я связен).

2) Граф Я содержит ровно две связных компоненты и выполнено условие:

(a) среди связных компонент Я нет чётной размера, не превосходящего 2р.

3) Граф Я содержит не менее трёх связных компонент и выполнены условие (а) и условие:

(b) среди связных компонент Я нет двух различных нечётных компонент, сумма размеров которых не превышает 1р.

Обратно, если выполнено одно из утверждений 1-3, то граф Я является различающим для семейства ¡Ср<п-р.

В силу теоремы 6 для того, чтобы определить, является ли граф Я различающим для семейства КРгП~Р1 достаточно составить набор натуральных чисел — размеров связных компонент графа Я — и проверить выполнение условий, указанных в теореме 6.

Минимальными различающими графами для семейств /Ср>п_р являются леса, т. е. графы, связные компоненты которых являются деревьями. Кроме того, минимальный различающий граф для семейства £Р>П-Р имеет максимально возможное при данных п и р, с учётом теоремы 6, число связных компонент (деревьев).

В диссертации установлено точное значение объёма минимального теста для каждого семейства АГР1„_Р (п ^ 2, 1 < р ^ [п/2]).

Теорема 7. При всякихр, п~^2р выполнено ЦК^^р) = п — к^п^р), где к(п,р) определяется следующим образом.

1) Если 2р ^ 1

к(п, р)

-{к

при п = 2р + 1,

при других значениях п.

2) Если Зр + 3 < п

если п четно, если п нечётно.

если г четно, если г нечётно,

3) иг: *$№рЬг&лШШ№ЩвМ@твом

я = (р + 1)д + г, (Кг<р+1.

4) Если п^ 4р + 3 и р нечётно, то

если г четно или Г ^ р, в противном случае,

где q иг определяются равенством

п + 2 = (р + 2)д + г, 0 < г < р + 2.

Теоремы 7 и 4 дают точные значения величины £(•) для элементарных (состоящих из одного класса изоморфизма) семе г /Ср,п_р и для их объединения (вместе с вырожденным случаем) — семейства ЮЦ. Следующая лемма, доказанная в диссертации, даёт верхнюю и нижнюю оценки для «промежуточных» семейств.

Лемма 27. Пусть Оп — непустое регулярное семейство графов, заданных на множестве вершин Уп, п ^ 3, Яп С К.п иЯп% {Кп,Кп}. Тогда выполнено следующее двойное неравенство:

Если оке п = 2, то Ь(Оп) = 0.

Таким образом, для всех регулярных семейств, состоящих из графов, описанных в пунктах 1-4 теоремы 2, установлены верхняя и нижняя оценки величины Ь(-), которые различаются не более, чем в 2 раза.

Глава 4 диссертации посвящена изучению тестов для семейств О," и со- 2"', указанных в пунктах 5 и 6 теоремы 2.

При £ € {0, \,п — 1,п} семейства <2™ совпадают с уже рассмотренными. Поэтому в этой главе значения параметра £ рассматриваются в переделах 2 ^ Ь ^ п — 2. Как и в предыдущей главе, семейство С0-2" отдельно не рассматривается.

В диссертации установлены нижняя и верхняя оценки объёма минимального теста для каждого из семейств С" (п ^ 4, 2 ^ < ^ п — 2).

Теорема 8. Пусть — 2. Верно следующее двойное

неравенство:

В диссертации показано, что верхняя и нижняя оценки в теореме 8 различаются не более, чем в 4 раза при любых значениях параметров п и Ь (п > 4, 2 ^ г < п - 2).

В диссертации при к ап и £ (п ^ 4, 2 ^ Ь ^ п — 2) для семейства <2" явно построен различающий граф, имеющий — (£) рёбер. Этот граф обозначается через Я(£, п); он получен из Кп выбрасыванием рёбер клики, построенной на вершинах с номерами 1,2,..., Ь. Такой граф можно построить при любом значении параметра ? в промежутке 1 < * < п— 1.

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

Пусть 0п — регулярное семейство графов на множестве вершин Уп. Будем говорить, что в семействе 0п имеется коллизия, если О" С 0„ и при некотором

п — 2; в этом случае, число п — £ будем называть параметром коллизии.

Далее через га) обозначается объединение графа Я(£, п) и ребра, соединяющего первые две вершины. Через Тиг(п, 5) обозначается граф с

(2)

наименьшим числом рёбер, дополнение которого не содержит s-клик (ту-рановский граф), число рёбер в этом графе обозначается через T(n,s); согласно известной теореме Турана T(n,s) = g^C'J+l) + §9(9 — l)(s—1 —i")»

где q и Г есть соответственно неполное частное и остаток от деления п

В диссертации доказаны следующие утверждения.

Теорема 10. Пусть бп —регулярное семейство графов на множестве вершин Уп, состоящее из графов с не более, чем двумя классами подобия вершин. Пусть в Яп нет коллизий. Положим г равным наименьшему среди чисел 2, 3, ..., п — 2, такому что в семействе 0п содержится или со-О?, или равным п — 2, если указанных подсемейств в 0п нет. Тогда граф Н'(г,п) является различающим для семейства £?„.

Теорема 11. Пусть Яп — регулярное семейство графов на множестве вершин Уп, состоящее из графов с не более, чем двумя классами подобия вершин, не имеющее коллизий. Пусть в 0п содержится хотя бы одно из семейств или со-б™, а т равно наименьшему из соответствующих значений Тогда для величины Ь(0п) выполнены следующие соотношения:

В диссертации показано, что верхняя и нижняя оценки в теореме 11 различаются не более, чем в 4 раза.

Если в регулярном семействе Qn имеется коллизия с параметром $, то множество попарных симметрических разностей графов из Qn содержит а всякий граф этого семейства содержит п — s изолированных вершин. Чтобы построить различающий граф для семейства Qn с коллизиями, уже использовавшийся граф R{t,n) объединяется с турановским графом Tur(n, s). Вдиссертациидоказаны следующие утверждения.

Теорема 12. Пусть Qn —регулярное семейство графов на множестве вершин Vn, состоящее из графов с не более, чем двумя классами подобия вершин. Пусть в Qn есть коллизии us— наименьший из их параметров. Положим t равным наименьшему среди чисел 2, 3, ..., п — 2 такому, что в семействе Qn содержится Q" или co-QJ1. Тогда граф R'(t,n) UTur(n,s) является различающим для семейства Qn

Теорема 13. Пусть Qn —регулярное семейство графов на множестве вершин Vn, состоящее из графов с не более, чем двумя классами подобия

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

на« - I.8

вершин. Пусть в 5п есть коллизии ш— наименьший из их параметров. Положим t равным наименьшему среди чисел 2, 3, ..., п — 2 такому, что в семействе бп содержится б™ или 'СО-0£. Тогда выполнены следующие соотношения:

При любых значениях параметров верхняя и нижняя оценки в теореме 13 различаются не более, чем в 8 раз.

Таким образом, в главах 3-5 диссертации рассмотрены все регулярные семейства, состоящие из графов с не более, чем двумя классами подобия вершин. Для каждого такого семейства (/п установлены верхние и нижние оценки величины Ь(С/„), различающиеся не более, чем в 8 раз. Для семейств, не содержащих коллизий, полученные оценки различаются не более, чем в 4 раза. С учётом результатов главы 2 это завершает рассмотрение общего случая произвольных регулярных семейств графов.

В главах б и 7 диссертации изложен ряд результатов, уточняющих и дополняющих обшие результаты глав 2-5 и касающихся некоторых специальных семейств графов, которые представляют самостоятельный интерес.

В главе 6 изучаются различающие графы для некоторых семейств, аналогичных семействам рассмотренным в главе 3.

Рассматриваются семейства каждый граф такого семей-

ства состоит из к непересекающихся по вершинам клик, г-я клика содержит вершин При этом предполагается, что выполнены следующие два условия:

1) Р1 ^ Р2 < • • • < Рк,

Всякий граф из семейства задаёт некоторое отношение эк-

вивалентности на множестве вершин К, (и наоборот); всякие две различные эквивалентные вершины соединяются в этом графе ребром, максимальные клики соответствуют классам эквивалентности, рёберная про-веркадля ребра ш соответствует вопросу "эквивалентны ли данные элементы и и и?".

При к — 1 для каждого п имеется единственное семейство /Ср^,..^, состоящее из единственного графа Кп. При к = 2 семейства ^Срц^,..^» суть уже изученные в главе 3 семейства

В главе 6 рассмотрены семейства /Ср1,р2,...,рк при к ^ 3. В диссертации доказаны следующие утверждения.

Теорема 14.

Теорема 15. Пусть к ^ 3 и рг ^ 2, тогда

Нижняя оценка, которую даёт теорема 15, является не менее сильной, а если Р2 < P3i то и более сильной, чем оценка, которую даёт более общая теорема 1.

Видно, что случай к ^ 3 качественно отличается от случая к = 2, рассмотренного в главе 3.

В главе 7 исследованы различающие графы для семейства "Нп га-мильтоновых (т. е. проходящих через каждую из вершин ровно по одному разу) циклов на Vi,.

В диссертации доказаны следующие утверждения.

Теорема 16. Для того, чтобы граф G был коразличающим для семейства "Нп необходимо и достаточно, чтобы он не содержал ни чётных. циклов, ни пар нечётных циклов с общей вершиной.

Теорема 17. При всяком п ^ 3 минимальный различающий граф для семейства "Нп имеет ровно п{п — 3)/2 — [n/3j + 1 рёбер.

Тем самым, для семейств Нп при всяком п ^ 3 охарактеризованы все (ко ^различающие графы и установлено точное значение величины В диссертации дано описание минимальных различающих графов.

В заключение автор хотел бы выразить искреннюю благодарность своему научному руководителю — Октаю Мурадовичу Касим-Заде — за постановку задачи, многочисленные полезные обсуждения и всемерную поддержку на всех этапах данной работы.

Публикации автора по теме диссертации

1. Дебрев Е. В. О задаче поиска гамильтоновых циклов рёберными тестами // Материалы XI Межгосударственной школы-семинара «Синтез и сложность управляющих систем» (Нижний Новгород, 20-25 ноября 2000 г.). М: Изд-во центра прикладных исследований' при механико-математическом факультете МГУ, 2001. С. 60-66.

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

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

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

5. Дебрев Е. В. Тестовые задачи на графах // Материалы XIV Международной школы-семинара «Синтез и сложность управляющих систем» (Нижний Новгород, 27 октября - 1 ноября 2000 г.). Н. Новгород: Изд-во Нижегородского государственного педагогического университета, 2003. С. 27-32.

Издательство ЦПИ при механико-математическом факультете

МГУ им. М.В.Ломоносова.

Подписано в печать оз гоын.

Формат 60 х 90 1/16. Усл. печ. л.

Тираж 100 экз. Заказ /$

Лицензия на издательскую деятельность ИД В 04059, от 20.02.2001г.

Отпечатано с оригинал-макета на типографском оборудовании механико-математического факультета и Франко-русского центра им. A.M. Ляпунова.

»- 529 2

Введение

1 Основные определения и простейшие факты

1. Простейшие свойства различающих графов.

2. Некоторые простейшие семейства графов

2 Регулярные семейства графов

1. Понятие регулярности.

2. Одно комбинаторное неравенство.

3. Классы подобия вершин в графах.

3 Семейства Kytn-P и co-JCp^-p

1. Определение семейств JCn и /Cq.

2. Семейства fCn и

3. Семейства 1Ср<п-р.

4. Оценки £(•) для подсемейств /Сп.

4 Семейства и co-Qj}

5 Семейства, состоящие из графов с не более, чем двумя классами подобия вершин

6 Семейства графов А>разбиений

1. Матрицы пересечений.

2. Верхняя и нижняя оценки.

7 Гамильтоновы циклы

1. Свойства коразличающих графов.

2. Характеризация всех коразличающих графов.

3. Максимальные коразличающие графы.

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

В общем виде задача о построении табличного теста, по-видимому, была поставлена С. В. Яблонским [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: Teubner; Chichester 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.