Содержание к диссертации
Введение 2
1 Основные определения и простейшие факты 10
Простейшие свойства различающих графов 13
Некоторые простейшие семейства графов 15
2 Регулярные семейства графов 17
Понятие регулярности 17
Одно комбинаторное неравенство 19
Классы подобия вершин в графах 22
3 Семейства JCptn-p и со-ІСріП-р 28
Определение семейств JCn и /Cq 28
Семейства JC1 и 29
Семейства JCptn-p 34
Оценки ,() дія подсемейств /Сп 47
Семейства Q* и со-0% 50
Семейства, состоящие из графов с не более, чем двумя классами подобия вершин 56
Семейства графов А>разбиений 70
Матрицы пересечений 71
Верхняя и нижняя оценки 74
7 Гамильтоновы циклы 78
Свойства коразличающих графов 79
Характеризация всех коразличающих графов 85
Максимальные коразличающие графы 86
Список литературы 89
Введение к работе
Настоящая диссертация посвящена изучению безусловных тестов, различающих графы из заданных семейств.
В общем виде задача о построении табличного теста, по-видимому, была поставлена С. В. Яблонским [8]. В такой постановке имеется заданное заранее конечное множество идентифицируемых (искомых) объектов, например, определённого характера неисправности некоторой электрической схемы, а также конечный набор допустимых элементарных проверок. Тестом называется всякий такой поднабор элементарных проверок, что, выполнив все проверки в поднаборе, по полученным данным можно однозначно идентифицировать любой объект из заданного множества. Представляет интерес поиск тестов наименьшего объёма (т. е. содержащих наименьшее возможное количество элементарных проверок), а также описание всех тестов.
Термин «табличный тест» связан с тем, что значения элементарных проверок на объектах можно выписать в виде элементов таблицы, строки которой поставлены в соответствие объектам, а столбцы проверкам, а на пересечении столбца р со строкой х стоит значение проверки р на объекте х. Тесты — это наборы столбцов такие, что если из таблицы исключить все остальные столбцы, то в ней не окажется двух одинаковых строк, объём теста — это число столбцов в нём.
Теория тестов получила дальнейшее развитие в работах А. Е. Андреева, Е. В. Дюковой, Ю. И. Журавлёва, А. Д. Коршунова, В. Н. Носкова, Н. П. Редькина, В. А. Слепяна, Н. А. Соловьёва и самого С. В. Яблонского. Обзор некоторых результатов многочисленных исследований можно найти в статье СВ. Яблонского [10], а также в монографии Н. А. Соловьёва [7].
Подчеркнём, что при рассмотрении табличных тестов, речь, как правило, идёт о тестах безусловных, т.е. для идентификации объекта выполняются все элементарные проверки теста (безразлично в каком порядке), а потом по набору значений этих проверок находится искомый объект, единственный по определению теста. Некоторыми авторами рас-
сматривались и задачи другого типа — задачи об условных тестах (также используется термин «задачи комбинаторного поиска»).
Неформально под условным тестом понимается алгоритм, который шаг за шагом выполняет элементарные проверки, причём выбор проверки для следующего шага, вообще говоря, зависит от информации, полученной на предыдущих шагах. Результатом работы такого алгоритма, как и в случае безусловного теста, является однозначно идентифицированный объект. Но, в отличие от безусловного, условный тест может выполнять различное число элементарных проверок для идентификации различных объектов. В качестве меры сложности условного теста, аналогичной объёму безусловного теста, как правило, выбирают число выполненных элементарных проверок (длина теста) в худшем случае, либо в среднем (и то и другое — по всем искомым объектам).
Определения и некоторые результаты в отношении условных тестов можно найти в монографии [11], см. также [1] и [4].
В настоящей работе речь идёт о безусловных тестах, которые строятся для семейств конечных неориентированных графов без петель и кратных рёбер. Искомыми объектами в соответствующих задачах являются графы, принадлежащие заданным семействам, а элементарные проверки устанавливают, принадлежит ли искомому графу некоторое заданное ребро; такие проверки называются рёберными.
Близкие задачи изучались различными авторами.
Построению условных тестов, идентифицирующих граф посредством рёберных тестов, посвящен раздел монографии М. Айгнера [11, раздел 3.5]. В нём установлен вид условных рёберных тестов наименьшей длины в худшем случае для следующих семейств графов на фиксированных п нумерованных вершинах: семейство деревьев, семейство максимальных паросочетаиий, семейство полных звёзд. Приводится общий метод построения нижних так называемых «жадных» оценок, дающий, однако, для многих семейств лишь оценку, точную по порядку величины; приводимая в книге оценка для семейства всех гамильтоновых циклов на п нумерованных вершинах получена таким способом.
Другими авторами рассматривались элементарные проверки более общего, по сравнению с рёберными, вида [13], [14, глава 2]. В указанных работах рассматриваются условные тесты для семейств конечных неориентированных графов без петель и кратных рёбер на п нумерованных вершинах. Элементарные проверки соответствуют всевозможным кликам на этих вершинах (как вариант, кликам, содержащим не более t вершин). В одной из моделей элементарная проверка устанавливает, имеет ли искомый граф хоть одно общее ребро с соответствующей кликой. В другой модели проверка выдаёт количество рёбер, общих у клики и ис-
комого графа. Для длины тестов в худшем случае в указанных работах установлены оценки, точные по порядку величины.
Диссертация состоит из введения, семи глав и списка литературы.
В главе 1 вводятся основные обозначения, даются определения и доказываются простейшие утверждения, которые многократно используются далее.
В главе 2 вводится понятие регулярного семейства графов и доказываются основные результаты общего характера относительно таких семейств. В частности все регулярные семейства разделяются на содержащие графы с тремя и более классами подобия вершин (отношение подобия вершин определяется в этой же главе), и семейства, таких графов не содержащие. Для различающих графов для семейств первого типа доказывается квадратичная по порядку нижняя оценка на число рёбер. Кроме того, здесь дана полная характеризация графов, имеющих не более двух классов подобия вершин. Изучению семейств, состоящих из таких графов, посвящены три последующие главы.
В главе 3 изучаются семейства графов, каждый из которых является объединением двух клик, не имеющих общих вершин. Получены точные результаты об объёме минимального теста для таких семейств.
В главе 4 изучаются семейства графов, каждый из которых состоит из і-клики ип-t изолированных вершин. Для числа рёбер в различающем графе для такого семейства получены верхняя и нижняя оценки, различающиеся не более, чем в 4 раза. Конструкция, использованная для получения верхней оценки, играет существенную роль в следующей главе.
В главе 5 собираются воедино сведенья, полученные в главах 2, 3 и 4 и доказываются общие утверждения о регулярных семействах, состоящих из графов, имеющих не более двух классов подобия вершин. Здесь установлены верхние и нижние оценки объёма минимального теста для всех таких семейств, различающиеся не более, чем в 8 раз.
Таким образом, в главах 2-5 найдены точные по порядку величины двусторонние оценки объёма минимального теста для всех ругулярных семейств графов на п вершинах. Во всех случаях эти оценки различаются не более, чем в 8 раз. Дано явное описание тестов, доставляющих указанные оценки.
В двух последних главах в дополнение к общим результатам рассматриваются некоторые конкретные семейства графов, представляющие особый интерес.
В главе б изучаются семейства графов, образованных объединением дизъюнктных клик; эта глава дополняет результаты главы 3.
В главе 7 изучается построение минимальных тестов для семейства Тіп
всех гамильтоновых циклов на п вершинах. Получены точные результаты относительно числа рёбер в минимальном тесте и характеризация всех тестов.
Для формулировки основных результатов необходимы некоторые понятая. Семейство графов на фиксированных п нумерованных вершинах называется регулярным, если оно вместе с каждым графом содержит и все ему изоморфные. Вершины и и v графа G называются подобными, если граф, полученный их перестановкой, совпадает с G (он, разумеется, изоморфен графу G). Нетрудно видеть, что отношение подобия вершин в фиксированном графе есть отношение эквивалентности. Граф, образованный рёбрами теста, идентифицирующего любой граф из заданного семейства Q, называется различающим графом для семейства Q. Наименьшее число рёбер в различающем графе для семейства Q обозначается через L(G).
Через JCp,n-p обозначается семейство всех графов на п вершинах, являющихся объединением непересекающихся по вершинам р-клики и (тг—р)-клики. Через QJ1 обозначается семейство всех графов на п вершинах, являющихся объединением -клики и n — t изолированных вершин. Для каждого семейства Qn графов на п вершинах через со-п обозначается семейство, состоящее из дополнений графов семейства Qn.
Диссертация содержит следующие основные результаты.
Теорема 1. Пусть граф G имеет не менее трёх классов подобия вершин. Тогда для всякого регулярного семейства Q, содержащего G, выполнено неравенство:
L{G) >(l- у^з) Q) - \п.
Теорема 2. Граф на п вершинах имеет не более двух классов подобия тогда и только тогда, когда он является графом одного из следующих видов:
полный граф (один класс подобия);
пустой граф (один класс подобия);
граф из семейства К.РіП-р, где 1 ^ р ^ п — 1 (два класса подобия);
граф из семейства со-Х^,>п_р, где 1 ^ р ^ п—1 (два класса подобия);
граф из семейства Q%, где 2 ^ t ^ п — 2 (два класса подобия);
граф из семейства co-Ql, где 2 ^ t ^ п — 2 (два класса подобия). В силу теорем 1 и 2 всякое регулярное семейство Q либо состоит лишь
из графов, имеющих не более двух классов подобия вершин и перечисленных в теореме 2, либо для величины L(Q) справедлива квадратичная по порядку нижняя оценка, приведённая в теореме 1.
В соответствии с результатами, изложенными в главе 1 (см. лемму 6), тесты для семейства графов Q в то же время являются и тестами для семейства Q, образованного дополнениями графов из семейства Q. Таким образом, в главе 3 изложены результаты о семействах двух типов: семейства, состоящие из графов, образованных объединением двух непересекающихся по вершинам клик и содержащих в объединении все п вершин, и семейства, образованные дополнениями таких графов, то есть полными двудольными графами, доли которых содержат в объединении все п вершин. Для семейства /Сд, содержащего все образованные двумя дизъюнктными кликами графы и полный граф, доказана
Теорема 3. Минимальные различающие графы для JCq — это в точности деревья на п вершинах.
Отсюда для семейства К%, а вместе с ним и для семейства К,п, содержащего все образованные двумя дизъюнктными кликами графы, но без полного графа, вытекает
Теорема 4. При всех п ^ 3 выполнено:
ЦК71) = Ь(Ц) = п - 1.
Теорема 4 даёт точный ответ на вопрос об объёме теста для семейств, в известном смысле максимальных, то есть содержащих все графы некоторого типа, среди которых имеются и неизоморфные друг другу. Случай «элементарных» семейств /Ср>п_р, являющихся классами изоморфизма графов, образованных дизъюнктными р-кликой и (п— р)-кликой, также разобран полностью.
Теорема 7. При всяких р, n ^ 2р выполнено L(JCpin-p) = n — k(n,p), где k(n,p) определяется следующим образом. 1. Если 2р < п <[ Зр + 2, то
к{п,р) = \ 2
при п = 2р+ 1,
при других значениях п.
2. Если Зр + 3 < п 5 Ар + 2, то
,, . Г 2, если п четно, к{п,р) = 4 '
[3, еслип нечетно.
3. Если п ^ 4р + 3 up четно, то
,, ч (а, если г четно.
если г нечетно,
где q иг определяются равенством
rc = (p+l)g + r, 0 ^ г <р+1. 4- Если п ^ Ар + 3 up нечётно, то
,, ч (а, если г четно или г ^ р,
к(п,р) = J *' ^ "
] q — 1, б противном случае,
где q иг определяются равенством
n + 2=(p + 2)q + r, О < г < р + 2.
Также доказано, что для любого из семейств /СРіП_р всякий минимальный тест является лесом (объединением деревьев, попарно не имеющих общих вершин и в объединении содержащих все п вершин). Величина к(п,р) есть число связных компонент (деревьев) этого леса. Для каждой комбинации параметров пир явно указывается набор размеров связных компонент, задающий тест.
Семейства 0% и co~Q% изучаются в главе 4. Доказана следующая теорема.
Теорема 8. Пусть n^4,2^i^n — 2. Верно следующее двойное неравенство:
=^< «ОД <)-$ (1)
Оценка сверху получена из явной конструкции различающего графа: из полного графа Кп выбрасываются рёбра клики, построенной на первых t вершинах. Такой граф обозначается через R(t, п).
Кроме того, показано, что верхняя и нижняя оценки, указанные в теореме 8, различаются не более, чем в четыре раза.
В главе 5 исследуются произвольные семейства, образованные графами с не более, чем двумя классами подобия вершин. Все такие регулярные семейства подразделяются на имеющие коллизии, т. е. содержащие при некотором (2 ^ і < п — 2) в качестве подсемейств Q" и Kt,n-t или co-Ql и co-JCt,n-t (число n—t называется параметром коллизии), и не имеющие коллизий. Далее через R'(t,n) обозначается объединение графа R(t, п) и ребра, соединяющего первые две вершины, а через Tur(n, s) — граф с наименьшим числом рёбер, дополнение которого не содержит s-клик (турановский граф). Доказаны следующие результаты.
Теорема 10. Пусть Qn — регулярное семейство графов на множестве вершин Vn, состоящее из графов с не более, чем двумя классами подобия
вершин. Пусть в уп нет коллизий. Положим г равным наименьшему среди чисел 2, 3, ..., п — 2, такому что в семействе Qn содержится Q? или co-Q, или равным п — 2, если указанных подсемейств в Qn нет. Тогда граф R'(r,n) является различающим для семейства Gn-Из теоремы 10 непосредственно следует
Теорема 11. Пусть Qn — регулярное семейство графов на множестве вершин Vn, состоящее из графов с не более, чем двумя классами подобия вершин, не имеющее коллизий. Пусть в Qn содержится хотя бы одно из семейств Q или co-Q, а г равно наименьшему из соответствующих значений t. Тогда для величины L(Qn) выполнены следующие соотношения:
Теорема 12. Пусть Qn — регулярное семейство графов на множестве вершин Vn, состоящее из графов с не более, чем двумя классами подобия вершин. Пусть в Qn есть коллизии us— наименьший из их параметров. Положим t равным наименьшему среди чисел 2, 3, ..., п — 2 такому, что в семействе Gn содержится Q" или co-Q. Тогда граф R'(t,n) UTur(n,s) является различающим для семейства Qn. Из теоремы 12 следует
Теорема 13. Пусть Qn — регулярное семейство графов на множестве вершин Vn, состоящее из графов с не более, чем двумя классами подобия вершин. Пусть в Gn есть коллизии us— наименьший из их параметров. Положим t равным, наименьшему среди чисел 2, 3, ..., п — 2 такому, что в семействе Gn содержится Qn или co-Qn. Тогда выполнены следующие соотношения:
тах(п(п-ДТ(П)5)) ^ цдп) ^ ^ _ Q +г(П|в) + L
Показано, что верхняя и нижняя оценки в теореме 11 различаются не более, чем в 4 раза, а в теореме 13 — не более, чем в 8 раз.
Это завершает рассмотрение регулярных семейств, состоящих из графов с не более, чем двумя классами подобия вершин. Для каждого такого семейства Gn установлены верние и нижние оценки величины L[Qn), различающиеся не более, чем в 8 раз. Для семейств, не содержащих коллизий, полученные оценки различаются не более, чем в 4 раза.
Похожие диссертации на Тестовые задачи на графах
