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

Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «Санкт-Петербургский государственный университет»

На правах рукописи

Абрамовская Татьяна Викторовна

Задачи гарантированного поиска на графах

01.01.09 - Дискретная математика и математическая кибернетика

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

1 8 ОКТ 2012

Санкт-Петербург - 2012

005053627

005053627

Работа выполнена на кафедре исследования операций математико-механиче-ского факультета Санкт-Петербургского государственного университета.

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

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

доктор физико-математических наук, профессор Петров Николай Николаевич Панина Гаянэ Юрьевна, доктор физико-математических наук, Санкт-Петербургский институт информатики и автоматизации РАН, ведущий научный сотрудник Чистяков Сергей Владимирович, доктор физико-математических наук, профессор, факультет прикладной математики - процессов управления СПбГУ, профессор

Санкт-Петербургский экономико-математический институт РАН

Защита состоится «_2_» {¿Яо^^/1^ 2012 г. в ^Рчасов на заседании диссертационного совета Д 212.232.29 при Санкт-Петербургском государственном университете, расположенном по адресу: 199034, Университетская наб., д. 7/9, ауд. 133.

С диссертацией можно ознакомиться в Научной библиотеке им. Горького Санкт-Петербургского государственного университета по адресу: 199034, Санкт-Петербург, Университетская наб., д. 7/9.

Автореферат разослан 2012 г.

Учёный секретарь диссертационного совета

Нежинский В. Г

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

Актуальность работы. Круг задач поиска на множествах сложной топологической структуры весьма широк. К задачам подобного рода относятся дифференциальные игры, например, проблема «Принцесса и Чудовище», сформулированная Р. Айзексом в [11], дискретные задачи поиска. Часто в качестве арены поиска рассматривается топологический граф. Группа преследователей ставит своей целью «поймать» (в том или ином смысле) невидимого убегающего, которому программа действий преследователей становится известной до начала поиска. Таким образом, речь идёт о задаче гарантированного поиска.

Стандартная задача поиска ставится следующим образом: для каждого графа найти наименьшее число преследователей, необходимое для успешного завершения поиска. Эту величину, зависящую от структуры графа, условия поимки и динамических возможностей участников, называют поисковым числом. Впервые задача об определении поискового числа была поставлена американским математиком Т. Парсонсом [12] и независимо Н. Н. Петровым [13] в 70-80 годы прошлого столетия. В последующие годы важные результаты, касающиеся поисковых чисел, были получены Пападимитриу, Гэри, Джонсоном, Сеймуром, Робертсоном, Томасом и другими известными зарубежными математиками.

Интерес к проблеме гарантированного поиска обусловлен, прежде всего, бесспорной актуальностью этой тематики, а также многочисленными связями между поисковыми числами и другими инвариантами графа, возникающими в различных областях математики. Например, некоторые характеристики графа, лежащие в основе теории СБИС (Сверхбольших Интегральных Схем), такие, как ширина разреза (the cut width), топологическая ширина ленты (the topological bandwidth), величина вершинного разделения (the graph

vertex separation number), выражаются через поисковые числа и тем самым получают новую интерпретацию с точки зрения теории поиска. Через поисковые числа выражаются также две основные составляющие известной теории миноров Робертсона и Сеймура — путевая и древесная ширина графа (the path width and the tree width). Ранее была обнаружена связь между задачами поиска на графе и «игрой в камни» (a pebble game) на ориентированном ациклическом графе, которая моделирует рациональное использование компьютерной памяти. Поисковые числа возникают также в задачах координации движения робота, в некоторых моделях борьбы с компьютерным вирусом, в проблеме сохранения секретности информации, передаваемой через электронную сеть при наличии мобильных подслушивающих устройств, проблеме картирования человеческого генома.

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

Задачам гарантированного поиска посвящен целый номер журнала Theoretical Computer Science (Volume 399, Number 3, 6 June2008), содержащий достаточно полную библиографию по гарантированному поиску [14]. Обзор результатов и приложений по теории гарантированного поиска подготовлен диссертантом совместно с научным руководителем Н. Н. Петровым и опубликован в [1].

Цель диссертационной работы состоит в исследовании проблемы е-поиска, разработке новых подходов к её изучению. Существенное место в диссертации отведено исследованию скачков функции Головача, доказательству достаточных условий её невырожденности, а также решению задачи £-поиска для некоторых графов.

На защиту выносятся следующие основные результаты и положения:

1. Доказано достаточное условие невырожденности функции Головача для деревьев.

2. Построено минимальное дерево с вырожденной функцией Головача, а также минимальное дерево с указанным свойством функции Головача в условии ограничения на степень вершин.

3. Доказана плотность множества деревьев с невырожденной функцией Головача в множестве всех деревьев фиксированной комбинаторной схемы.

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

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

Научная новизна. Все основные результаты диссертации являются новыми. Исследуются новые подходы к определению е-поискового числа. Так, помимо традиционных методов построения и описания выигрывающих программ преследователей, для достижения поставленных целей формулируется задача, двойственная к задаче Головача, в терминах которой определяется один их центральных объектов диссертационного исследования — функция Головача. Также ставятся проблемы монотонности е-поискового числа и реализуемости функции как функции Головача для некоторого графа. Эти новые проблемы решаются в диссертации для некоторых классов графов.

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

5

Апробация работы. Основные результаты диссертации докладывались на VIII молодёжной конференции «Лобачевские чтения-2009», КГУ, Казань, ноябрь 1-6, 2009 [2]; XLI международной научной конференции аспирантов и студентов «Процессы управления и устойчивость», ПМ-ПУ СПбГУ, Санкт-Петербург, апрель, 2010; IV международной конференции «Game Theory and Management», GTM2010, ВШМ СПбГУ, Санкт-Петербург, июнь 28-30, 2010 [3, 4]; семинаре кафедры исследования операций математико-механиче-ского факультета СПбГУ, апрель 2011 г.; Санкт-Петербургском городском топологическом семинаре под руководством проф. Н. Ю. Нецветаева, май 2011 г.; международной конференции «7th Spain-Italy-Netherlands Meeting on Game Theory», SING7, Paris School of Economics, University of Paris 1, Париж, Франция, июль 18-20, 2011; семинаре физико-математического клуба при ПОМИ и СПбГУ под руководством Г. Ю. Паниной, март 2012 г.; семинаре лаборатории теории игр и принятия решений СПб ЭМИ, май 2012 г.; VI международной конференции «Game Theory and Management», GTM2012, ВШМ СПбГУ, Санкт-Петербург, июнь 27-29, 2012 [5].

Публикации. Материалы диссертации опубликованы в 10 печатных работах, из них 6 статей в рецензируемых журналах [1, 6-10] (работы [6-10] опубликованы в издании по перечню ВАК), 1 статья в сборнике трудов конференции и 3 публикации — тезисы докладов.

В работах [4, 8-10] соавтору (научному руководителю) принадлежит постановка задачи, все результаты получены диссертантом самостоятельно. В работе [1] диссертантом подготовлен раздел IV. Работы [2, 3] — тезисы совместных докладов на международных конференциях на общую тему, где представлены как результаты автора, так и её научного руководителя.

Структура и объем диссертации. Диссертационная работа объёмом 114 страниц состоит из введения, трёх глав и списка литературы, включающего 81 наименование. Работа содержит 14 иллюстраций.

Содержание работы

В диссертации исследуется задача гарантированного поиска типа «увидел-поймал». В качестве арены поиска рассматривается топологический граф, вершины которого — точки в Е3, рёбра — конечнозвенные ломаные, соединяющие две вершины и пересекающиеся только в вершинах.

На графе введена метрика р — длина кратчайшего (по евклидовой норме) пути, соединяющего две точки и полностью лежащего в графе.

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

(Преследователи): х,- = щ, г € {1,2,..., к], (Убегающий): у = ио, граф С является для всех игроков фазовым ограничением, а допустимые управления — кусочно постоянные вектор-функции, заданные на произвольных замкнутых временных отрезках [0,т].

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

Задача е-поиска состоит в определении минимальной численности 5£(С) команды преследователей, гарантирующих поимку убегающего на С с радиусом поимки е при любой его траектории.

Величина зе(С) называется е-поисковым числом и впервые возникает в работе П. А. Головача [15], поэтому будем называть задачу об определении е-поискового числа для некоторого топологического графа задачей Головача, а функцию, которая сопоставляет каждому е е-поисковое число, — функцией Головача.

При е = 0 задача Головача эквивалентна задаче о нахождении рёберно-по-искового числа, поставленной Т. Парсонсом [12] и Н. Н. Петровым [13].

Первая глава посвящена узучению задачи е-поиска на деревьях, основные результаты этой главы опубликованы в [6, 8, 10].

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

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

Будем говорить, что функция Головача графа С имеет в точке гг = е*(С) единичный скачок, если £к{С) < ек+\(0, скачок высоты I, если £к(С) < Ек+1(С), а для всех 1 < г < / выполняется равенство = £¿+¿(6).

Скачки высоты 2 и более будем называть неединичными или нетривиальными. Функцию Головача, имеющую только единичные скачки, — невырожденной (вырожденной в противном случае).

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

Будем говорить, что преследователь Р е-неблизок к точке а дерева Т в

некоторый момент /, если р(а, x(t)) > є.

Одним из наиболее эффективных инструментов при решении задачи є-по-иска на деревьях является следующая Лемма о трёх ветвях.

Лемма 1.4.1. Пусть на дереве Т существует вершина а, от которой отходят три ветви В\, В 2, Bj, для каждой из которых выполнено следующее: в любой программе П,- команды Р, выигрывающей в задаче е-поиска на В„ найдется момент времени, в который каждый из преследователей є-неблизок к а, і = 1,2,3. Тогда команда Р не может успешно завершить е-поиск на Т.

Далее в первой главе решается поставленная ранее двойственная задача для одного преследователя на деревьях.

Рассмотрим дерево Т, пусть Z = (аі, аг ■ ■ ■, ап) — произвольная цепь наибольшей длины в Т. Поддеревья Аь А2, ...,Ат — ветви, отходящие от вершин цепи Z, содержащие только одну вершину цепи Z. Через lj обозначим длину наибольшей цепи в Aj, начинающейся в вершине цепи Z, j = 1,2,..., т.

Теорема 1.5.1. В принятых обозначениях, для произвольного дерева Т выполняется следующее равенство:

є\{Т) = і шах

Z J Є1.....m

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

Теорема 1.5.2. Если sq{T) > 1, mo єг(Т) < є\{Т).

Доказывается некоторое достаточное условие невырожденности функции Головача для деревьев.

Зафиксируем произвольное є > 0. Обозначим Т{е) множество всех таких деревьев Г, что никакие две вершины дерева Т степени три или более не находятся на расстоянии 2е друг от друга.

Теорема 1.6.1. Пусть Т є 7"(e), и пусть к преследователей ловят убе-

гающего с радиусом поимки е на Т. Тогда группа из к + 1 преследователей осуществляет б-поимку на Т при некотором 5 < е.

В заключении первой главы рассматриваются графы фиксированной комбинаторной схемы (естественно соответствующий всякому топологическому графу комбинаторный граф).

Рассмотрим произвольное дерево Т, сопоставим ему набор (/], /2,..., 1п) € (О, со)" в соответствии с введённой нумерацией рёбер комбинаторной схемы дерева Т, где и — длина /-го ребра дерева Т. Пусть на множестве (0, ею)" введена стандартная топология произведения. Обозначим X С (0, оо)" множество всех таких наборов (/ь 12,..., 1п), что дерево с фиксированной комбинаторной схемой и соответствующими длинами рёбер имеет невырожденную функцию Головача.

Тогда имеет место следующая

Теорема 1.7.2. Множество X открыто и плотно в (0, оо)".

Вторая глава посвящена минимальным по количеству рёбер деревьям из того или иного класса с вырожденной функцией Головача. Основные результаты этой главы опубликованы в [4, 6, 10].

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

Теорема 2.1.2. Функция Головача для дерева Т, имеющего не более 27 рёбер, является невырожденной.

Теорема 2.1.3. Функция Головача для дерева Т, имеющего не более 28 рёбер и вершины степени не больше 3, является невырожденной.

Точность последних двух теорем подтверждается построенными в этой главе примерами соответствующих деревьев.

Вырожденность функции Головача в классе минимальных по количеству рёбер деревьев с данным рёберно-поисковым числом (исследованию которых

посвящены работы [12, 16]) также иллюстрируется во второй главе.

На основании так называемых серий Парсонса, введённых в [12], строится последовательность деревьев {7*}£12. Относительно указанной последовательности получены важные результаты, из которых следует существование сколь угодно больших скачков функции Головача для деревьев (ранее возможность сколь угодно больших скачков была проиллюстрирована только на примере полных графов [17]). Кроме того, впервые строится функция Головача, содержащая два нетривиальных скачка.

Теорема 2.5.2. Для каждого п > 4 функция Головача для дерева Т„ имеет скачок высоты

Теорема 2.5.3. Для каждого п > 7 функция Головача дерева Тп имеет разрыв в точке е — 1 и 1-поисковое число дерева Т„ равно + 1.

Третья глава состоит из трёх параграфов, в которых изучаются новые подходы к исследованию проблемы е-поиска. Основные результаты этой главы опубликованы в [7, 9].

Рассматривается проблема монотонности е-поискового числа.

Будем называть е-поисковос число монотонным для связного подграфа Н графа С, если выполнено неравенство ле(Я) < 5е(С).

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

Теорема 3.1.2. Пусть С — граф, I — длина наименьшего ребра С, Н — произвольный связный подграф С. Тогда для всех 0 < е < | выполнено неравенство:

•Ус(е) >

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

Теорема 3.2.1. Пусть граф С с рёбрами единичной длины содержит в качестве подграфа полный граф Кп, С не имеет кратных рёбер. Тогда для О < е < 1 выполнено неравенство:

¿«(С) > *Е{Кп).

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

Пусть граф К'п, п > 3, получен из графа Кп удалением произвольного ребра, граф К'„ будем называть почти полным графом.

Теорема 3.2.2. Для п > 5, функция Головача графа К'п совпадает с функцией Головача графа Кп~

Далее ставится задача реализуемости функции как функции Головача некоторого графа. Пусть дана некоторая функция /(е), заданная на [0,+оо), кусочно постоянная, невозрастающая, непрерывная справа, принимающая целочисленные значения, причём существует £1 > О такое, что /(е) = 1 для всех е > £[. Функция / называется реализуемой, если существует граф й такой, что его функция Головача совпадает с / (граф С тогда будем называть реализацией

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

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

Теорема 3.3.2. Функция /3 реализуема в классе М тогда и только тогда, когда £1 > 3£г-

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

1. Абрамовская Т. В., Петров H. Н. Теория гарантированного поиска на графах // Дифференциальные уравнения и процессы управления. 2012. Т. 2. С. 9-65. URL: http://www.math.spbu.ru/diffjournal/RU/numbers/ 2012.2/article.165.html.

2. Абрамовская Т. В., Петров H. Н. Геометрические проблемы теории поиска // Труды математического центра имени Н.И.Лобачевского: Материалы VIII научной школы-конференции Лобачевские чтения 2009. Казань: Казан. матем. об-во, 2009. Т. 39. С. 1-10.

3. Abramovskaya T. V., Petrov N. N. Graph searching games with a radius of capture // Game Theory and Management, Collected abstracts, Ed. by L. A. Pet-rosyan, N. A. Zenkevich. SPb.: Graduate School of Management, 2010. P. 12-13.

4. Abramovskaya T. V., Petrov N. N. Graph searching games with a radius of capture // Contributions to Game Theory and Management, Ed. by L. A. Pet-rosyan, N. A. Zenkevich. SPb.: Graduate School of Management, 2011. Vol. IV. P. 8-18.

5. Abramovskaya T. V. The problem of the realizability of the function with properties of the Golovach function // Game Theory and Management, Collected abstracts, Ed. by L. A. Petrosyan, N. A. Zenkevich. SPb.: Graduate School of Management, 2012. P. 18-19.

6. Абрамовская Т. В. Нетривиальные разрывы функции Головача для деревьев // Вестник СПбГУ. Сер. 1. 2010. № 3. С. 3-12.

7. Абрамовская Т. В. Проблема реализуемости функции со свойствами функции Головача // Вестник СПбГУ. Сер. 1. 2012. № 2. С. 3-10.

8. Абрамовская Т. В., Петров Н. Н. О некоторых задачах гарантированного поиска на графах // Вестник СПбГУ. Сер. 1. 2010. № 2. С. 64-70.

9. Абрамовская Т. В., Петров Н. Н. О монотонности поискового числа в задаче Головача. Вестник СПбГУ // Вестник СПбГУ. Сер. 1. 2011. № 4. С. 3-9.

10. Абрамовская Т. В., Петров Н. Н. О сколь угодно больших скачках функции Головача для деревьев // Вестник СПбГУ. Сер. 1. 2011. № 1. С. 84-93.

Цитированная литература

11. Айзеке Р. Дифференциальные игры. Москва: Мир, 1967.

12. Parsons Т. D. Pursuit-evasion in a graph // Theory and Applications of Graphs. Y. Alavi and D. R. Lick, eds, Springer-Verlag. 1978. Vol. 642. P. 426-441.

13. Петров H. H. Задачи преследования при отсутствии информации об убегающем//Дифференциальные уравнени. 1982. Т. 18(№8). С. 1345-1352.

14. Fomin F. V., Thilikos D. M. An annotated bibliography on guaranteed graph searching // Theoretical Computer Science. 2008. Vol. 399(№3). P. 236-245.

15. Головач П. А. Об одной экстремальной задаче поиска на графах // Вестник ЛГУ. Сер. 1. 1990. Т. 15(№3). С. 16-21.

16. Головач П. А. Минимальные деревья с данным поисковым числом // Дискретная математика. 1992. Т. 4(№2). С. 52-60.

17. Головач П. А. Экстремальные задачи поиска на графах: Кандидатская диссертация/ЛГУ. 1990.

Подписано к печати 26.09.12. Формат 60x84 'Лб. Бумага офсетная. Гарнитура Тайме. Печать цифровая. Печ. л. 1,00. Тираж 100 экз. Заказ 5529.

Отпечатано в Отделе оперативной полиграфии химического факультета СПбГУ 198504, Санкт-Петербург, Старый Петергоф, Университетский пр., 26 Тел.: (812) 428-4043, 428-6919

Введение.

Глава 1. Проблема гарантированного поиска на деревьях.

1.1. Задача г-поиска. Функция Головача и ее свойства.

1.2. Двойственная задача и скачок функции Головача.

1.3. Технические замечания и дополнительные определения

1.4. Лемма о трёх ветвях.

1.5. Задача поиска на деревьях с малым числом преследователей

1.6. Достаточное условие невырожденности функции Головача для деревьев.

1.7. Проблема малых изменений длин рёбер.

Глава 2. Минимальные деревья с вырожденной функцией Головача

2.1. Невырожденность функции Головача для деревьев с малым числом рёбер.

2.2. Минимальное по числу рёбер дерево с вырожденной функцией Головача.

2.3. Неединичный скачок функции Головача в условиях ограничения на степень вершин.

2.4. Нетривиальный скачок для минимальных деревьев с рёберно-поис-ковым числом п.

2.5. Сколь угодно большой скачок функции Головача на деревьях

Глава 3. Некоторые проблемы теории ^-поиска.

3.1. Монотонность ^-поискового числа.

3.2. Полный подграф и почти полный граф.

3.3. Проблема реализуемости функции, обладающей свойствами функции Головача

Круг проблем, изучаемых в настоящем диссертационном исследовании, очерчивается идеей гарантированного поиска, выделяющей их в отдельный класс задач. Задачи подобного рода существенно отличаются от дифференци-1 ь альных игр преследования-уклонения с неполной информацией, рассмотренных Р. Айзексом в [8], хотя именно в указанной монографии ставится проблема «Принцесса и Чудовище» ([8], раздел 12.4), безусловно, оказавшая влияние на развитие теории гарантированного поиска и заключающаяся в следующем. В абсолютно тёмном помещении, форма и границы которого известны, Чудовище ловит Принцессу, если ему удаётся приблизиться к ней на заданное расстояние. При этом ограничений на скорость Принцессы не накладывается, а плата в указанной игре поиска — время поимки. Эта проблема была решена М. И. Зеликиным [21] в случае, если ареной поиска является окружность, и в дальнейшем широко изучена, в том числе на некоторых графах специального вида [35, 45, 46, 60, 61].

В основу задач гарантированного поиска положен «минимаксный принцип», не использующий вероятностного описания поведения игроков. Типичная задача гарантированного поиска на графах, на неформальном уровне, может быть сформулирована следующим образом. На графе группа игроков-преследователей ловит (в том или ином смысле) невидимого для них убегающего. Цель команды преследователей — построить «программу» действий, которая обеспечивала бы им поимку убегающего при любом его поведении. Иными словами, поимка должна быть гарантирована даже в том случае, когда выбранная преследователями программа становится известной убегающему «до начала поиска». В каждой формализации задачи поиска фиксируются динамические возможности участников, условие успешного завершения поиска (условие поимки), арена поиска (комбинаторный или топологический граф), и ставится следующая задача: найти наименьшее число преследователей, необходимое для успешного завершения поиска.

Впервые итерес к проблеме подобного рода проявил спелеолог Р. Брейш в [49], приводя «спасательную» версию игры. Представим себе, что в некоторой пещере, состоящей из холлов и лазов, потерялся исследователь. В распоряжении группы спасателей имеется карта пещеры (граф), но их работа существенно усложняется тем, что заблудившийся исследователь может бесцельно бродить по всей пещере с неизвестной скоростью. Требуется разработать план поиска, гарантирующий спасение спелеолога, т. е. исключающий любую возможность с ним разминуться. Несмотря на отсутствие точных формулировок и доказательств, Брейш в [49] рассмотрел примеры, иллюстрирующие некоторые ключевые идеи гарантированного поиска. Упомянем здесь недавно опубликованную монографию [50], в которой Брейш исследует проблему гарантированного поиска на картах известных пещер. Строгое изложение проблемы нахождения минимального числа преследователей проводится Т. Парсонсом в [73]. Независимо от упомянутых исследователей, задачу гарантированного поиска на графах ставит Н. Н. Петров в [25].

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

В настоящей работе в качестве арены поиска будет рассмотрен топологический граф.

Под графом понимается конечный связный топологический граф, вершины которого - точки в Ж3, рёбра — конечнозвенные ломаные, соединяющие две вершины и пересекающиеся только в вершинах.

На графе введена метрика р — длина кратчайшего (по евклидовой норме) пути, соединяющего две точки и полностью лежащего в графе.

На графе С располагаются группа игроков-преследователей, численностью к, и невидимый для них убегающий. Все участники обладают на графе простыми движениями:

Преследователи): х, = щ, I е {1,2,., к}, (Убегающий): у = щ.

Допустимые управления — кусочно постоянные вектор-функции, заданные на произвольных замкнутых временных отрезках [0, г].

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

Программой команды преследователей называется совокупность траекторий {х\(0,Х2(0> • • •»хк(0, * £ [0, г]}. Если при любой траектории убегающего у выбранная программа гарантирует поимку убегающего, то такая программа называется выигрывающей.

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

Задача е-поиска состоит в определении минимальной численности бе{(У) команды преследователей, обладающей выигрывающей программой с радиусом поимки е.

Величина ^(в) называется £-поисковым числом и впервые возникает в работе П. А. Головача [12], поэтому будем называть задачу об определнии е-гтоискового числа для некоторого топологического графа задачей Головача.

Поточечная поимка, т. е. случай £ = 0, приводит к оригинальной задаче гарантированного поиска на графах, поставленной в [73] и [25]. Несмотря на некоторые различия формализаций Парсонса и Петрова, Головачом в [11] доказана их эквивалентность между собой, а также эквивалентность некоторой дискретной задаче на соответствующем комбинаторном графе ([10]). Таким образом, в случае поточечной помки на графе С рассматриваемую задачу называют задачей Парсонса-Петрова, искомое в ней минимальное число преследователей еБ(С) — рёберно-поисковым числом (в каждой формализации задачи гарантированного поиска ищется то или иное поисковое число, для их различения образуют соответсвующее составное слово).

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

Движение каждого преследователя описывается последовательностью ходов. Каждым ходом преследователь может быть а) поставлен в вершину, б) снят с вершины, с) передвинут из вершины в вершину вдоль ребра.

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

1. либо один преследователь стоит в х, а другой переходит из х в у вдоль ребра е,

2. либо все рёбра, инцидентные х, за исключением е, очищены, и преследователь переходит из х в у вдоль ребра е.

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

В работах [73] и [25] решена задача Парсонса-Петрова для деревьев, в частности, Н. Н. Петров показал, что рёберно-поисковое число дерева совпадает с его степенью ветвления — топологическим инвариантом, который эффективно вычисляется.

Возможность очистки произвольного графа С без повторного загрязнения его рёбер командой преследователей, состоящей из к = еБ(С) преследователей, замечена А. ЛаПо и доказана в [66] (альтернативное доказательство приведено в [47]). Таким образом, множество программ преследователей, необходимых к рассмотрению в задаче Парсонса-Петрова на графе С, существенно сужается. Понятия очищенного и загрязнённого множеств естественным образом могут быть перенесены на общий случай е-поиска, но указанное свойство для положительных е принципиально не выполняется.

В работе [72] доказано, что задача вычисления рёберно-поискового числа графа в общем случае является А^Р-полной. На основе результатов Парсонса-Петрова, авторы работы [72] построили полиномиальный алгоритм для вычисления рёберно-поискового числа дерева. В той же работе [72] охарактеризованы графы с рёберно-поисковым числом, не превосходящим 3. Аналогичные результаты были получены в [29].

Известны работы, в которых рассматриваются бинарные операции над графами (см. [22] стр. 18). Например, в работе [80] рёберно-поисковое число декартова произведения непересекающихся графов выражается через рё-берно-поисковые числа операндов. Для соединения графов задача Парсонса-Петрова решена в [13]. Там же строится рёберно-поисковое число для всех полных п-дольных графов, определяемых как соединение п пустых графов.

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

Множество приложений задачи ГТарсонса-Петрова возникает в связи с поисковым числом ещё одной дискретной задачи гарантированного поиска. В работе Кироузиса и Пападимитриу [64] впервые была рассмотрена задача о вершинно-поисковом числе. В этой задаче движение каждого преследователя также описывается последовательностью ходов, но правила игры более простые. Каждым ходом либо преследователь ставится в вершину, либо один из преследователей, находящихся на графе, снимается. Ребро считается очищенным, если его концы заняты преследователями. Повторное загрязнение ребра определяется так же, как и в задаче о рёберно-поисковом числе. Вер-шинно-поисковое число графа для каждого графа G получило стандартное обозначение ns(G). Рёберно- и вершинно-поисковые числа (комбинаторного) графа G связывает очевидное соотношение ns(G) - es(G)\ < 1.

В [64] доказано, что рёберно-поисковое число графа, полученного из G помещением на каждое ребро двух вершин степени 2, совпадает с вершинно-поис-ковым числом G. Там же показано, что задача нахождения вершинно-поиско-вого числа в общем случае является TVP-полной, для деревьев, как и в задаче Парсонса-Петрова, разработаны линейные алгоритмы [54, 74, 75].

Топологические инварианты графов, о которых далее пойдёт речь, определяются при помощи нумераций вершин графов. Линейной укладкой (linear layout) графа G называется биекция

L : {1G,n = \VG\. Множество всех линейных укладок графа G обозначим через £(G).

Положим cw(G, L) := max {(и, v) e EG : L \u) < i, L~\v) > ill el,и 11 и cw(G) := min cw(G, L).

LeJXG)

Величина cw(G) называется шириной разреза (cut-width) графа G. Схожим образом определяются модифицированная ширина разреза (modified cut-width), величина вершинного разделения (vertex separation number) графа — все эти величины играют большую роль в теории сверхбольших интегральных схем при проектировании «линейных укладок» СБИС (см. обзор приложений в [7]). Типичная модель электронной микросхемы описывается графом G, в котором вершинами являются «переключатели», а рёбрами — «соединители». Если переключатели «укладываются» на прямой в порядке, задаваемой нумерацией L, то величины cw(G, L), mcw(G, L), vs(G, L) характеризуют «дефект» этой укладки, зависящий от рёберной структуры графа G.

Связь рёберно-поискового числа с указанными характеристиками графов описывается различными соотношениями, например, в [71 ] показано, что для всякого графа G справедливы следующие неравенства: es(G) < cw(G) < jA(G) es(G) - 1) + 1, где A(G) — максимальная степень вершины в графе G.

Изучению проблемы выражения рёберно-поискового числа через указанные инварианты посвящены работы [13, 54, 64, 71], исследования введённых характеристик и их применений в теории СБИС проводятся в [19, 67, 68, 81].

Посредством линейных укладок графов определяются также такие инварианты как ширина ленты (bandwidth) и топологическая ширина ленты (topological bandwidth) графа.

Пусть L е £(G), положим b(G, L) := max {|L~\u) - L-1(v)| : (и, v) e EG} и b(G) min b(G,L).

Le-C(G)

Величина b(G) называется шириной ленты графа G.

Следующая величина называется топологической шириной ленты графа tb(G) := min {b{G')}, где минимум берётся по всем графам G', получаемых из G помещением на его рёбра конечного числа вершин степени 2.

Связь этих двух характеристик с поисковыми числами показана в [70]. В работе [65], располагающей подробной библиографией, приводятся описания приложений в линейной алгебре, теории СБИС, в параллельных вычислительных системах, в некоторых задачах в области Искуственного Интеллекта и Биологии. Связь ширины ленты графа с одной задачей поиска {helicopter search problem) установлена Ф. В. Фоминым [56, 57]. С многочисленными результатами, касающимися ширины ленты графа, можно познакомиться в обзорах [51, 52, 65].

Опишем далее одну игру в камни (pebblegame), моделирующую задачу о рациональном использовании компьютерной памяти (см. [62, 64]) и связанную с гарантированным поиском на графах.

Игра происходит на ориентированном ациклическом графе ö, единственный её участник на каждом шаге может либо а) поставить камень на вершину у, если начала всех дуг, входящих в v, заняты камнями (на вершину, не имеющую «предшественников», камень можно поставить всегда); либо б) снять камень с вершины. Предполагается также, что на каждую вершину камень можно ставить только один раз.

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

Обозначим через S множество всех стратегий игрока, приводящих к «замощению» графа ö. Для каждой стратегии s е S введём в рассмотрение величину dem s, равную максимальному числу камней, одновременно находящихся на графе при использовании стратегии s. Определим величину dem G := mindern s, seS называемую демандом графа G.

Для произвольного (неориентированного) графа G через 0(G) обозначим множество всех ориентированных ациклических графов ö, полученных из G заданием ориентаций на всех его рёбрах.

Положим

Dem(G) := min dem G. eO(G)

Тогда, как показано в [64], для каждого графа G имеет место равенство

Dem(G) = ns(G).

Кироузис и Пападимитриу в [63] установили также связь между вершинно-поисковым числом и графами интервалов (см. [41], с. 35), которые, помимо самостоятельного интереса, привлекают внимание своими приложениями, например, в проблеме картирования человеческого генома [55].

Две характеристики — путевая ширина (pathwidth) и древовидная ширина (treewidth) графа — играющие важную роль в теории миноров Робертсона и Сеймура, приобретают различные теоретико-игровые интерпретации благодаря установленным связям с различными задачами поиска ([53, 76]).

Граф Н называется минором графа С, если Н получен стягиванием некоторых к рёбер (к > 0) одного из подграфов графа С.

Путевая ширина используется при изучении графов, имеющих в качестве минора лес. Говоря неформально, чем больше путевая ширина графа, тем «больше» лес, содержащийся в качестве минора этого графа. Древовидная ширина естественным образом возникает при исследовании структуры графов, имеющих в качестве минора планарный граф. Обзор многочисленных результатов Робертсона и Сеймура приведён в [48].

Более полная библиография и дальнейшие описания приложений о вер-шинно- и рёберно-поисковых числах приведены в [7, 39].

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

Некоторые черты ^-поискового числа существенно отличают задачу определения е-поискового числа от задач о рёберно- и вершинно-поисковых числах. Уже указывалась принципильная невозможность очищения некоторых графов без повторного загрязнения. Ещё одним свойством, которое чуждо перечисленным проблемам и существенно усложняет решение задачи е-поиска, является возможность роста е-поискового числа при переходе к подграфу. В общем случае может оказаться, что яЕ(Н) > для связного подграфа Н графа С и некоторого £ > 0.

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

20, 23, 31, 34], в которых были получены первые результаты, касающиеся поиска с противодействием.

Важной формализацией проблемы гарантированного поиска на топологических графах является задача, впервые поставленная Н. Н. Петровым в [26]. От задачи е-поиска её отличает поточечная поимка и введение ограничений на скорости игроков.

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

Преследователи): х{ = щ, ||м,|| <1, /6 1 ,п, (Убегающий): у = и о, ||ио11 ^ где ||. .|| — евклидова норма в К.3, а допустимые управления, как прежде, — кусочно постоянные вектор-функции, заданные на произвольных промежутках [0,т].

Ставится задача о нахождении наименьшей численности команды преследователей, обладающей выигрывающей программой. Искомая величина называется ¡1-поисковым числом графа С и обозначается

В работе [26] доказано, что если граф С имеет, по крайней мере, одну вершину степени большей 2, то > 2 для всех /л > 0, причём если ц достаточно мало, то = 2. Иначе говоря, на любом графе С двое преследователей всегда имеют выигрывающую программу, если их преимущество в скорости (т. е. число ¿Г1) достаточно велико.

В работах [26, 39, 69] исследуются ¿/-поисковые числа для одномерных остовов правильных многогранников и полных графов. Указанные классы графов часто становятся объектами исследования в задачах поиска, так как облегчают нахождение поискоых чисел наличием симметрии, однородностью и другими упрощающими моментами. В общей ситуации поисковые числа графов удаётся найти лишь в исключительных случаях.

Один из методов исследования //-поискового числа разработан Ф. В. Фоминым ([39, 40]) с использованием так называемых дискретных программ.

Программа П команды преследователей, заданная для / е [0, г], т — натуральное число, называется дискретной, если для любого к е (1,2,., т} на промежутке времени [к - 1 ,к] каждый из преследователей либо стоит в вершине графа, либо переходит из вершины в смежную вершину с максимальной скоростью.

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

Головачом в [13] доказано равенство ¿/-поискового и рёберно-поискового чисел для больших //: если // > 4 Ь-Г1, где / — длина кратчайшего ребра графа С,аЬ — сумма длин всех его рёбер, то ^(С) = е8(С).

Совпадение рёберно- и /¿-поисковых чисел отмечается Ф. В. Фоминым в [37] на деревьях: для всех // > 1 и произвольного дерева Т выполнено ^(Г) = е$(Г). Исследование //-поискового числа проводится также в [17, 38].

Непосредственное отношение задача е-поиска имеет к проблемам типа «увидел-поймал», общая постановка которых может быть записана следующим образом.

Пусть множество М, на котором ставится задача поиска, снабжено структурой топологического пространства, й — некоторая метрика на нём (вообще говоря, никак не связанная с этой структурой), е — неотрицательное число, характеризующее «радиус поимки». Путь у на М, т. е. непрерывное отображение [0,1] —» М, интерпретируется как «траектория» одного из участников поиска. Совокупность путей x¡,i = 1,.,«} называется выигрывающей программой для группы п преследователей, если для любого пути у («траектории убегающего») найдётся такой момент т е [0,1], что d(Xi(T),y(r)) < s для некоторого i € 1 ,п.

В работах [30, 36] предполагалось, что M является замкнутым полигонально связным подмножеством евклидова пространства Е3 с топологией, ин-дуцированнои из Е3, а траектории преследователей и убегающего суть непрерывные функции времени со значениями в М.

Введём на M следующую метрику do. Пусть а и b — две различные точки M и L(a, b) — множество всех ломаных, лежащих в M и соединяющих точки а и Ь. Для каждой такой ломаной / через g(J) обозначим число её звеньев. Положим do(a, b) = min {g(l) : l e L(a, b)} и do(a, a) = 0.

В работе [30] получен следующий результат: если в множестве M существует «равносторонний» треугольник, сторона которого (в метрике do) не меньше 6 (т. е. множество M содержит три точки, попарно соединяемые ломаными с не менее чем шестью звеньями), то ß{M) > 2. Для множества М, являющегося деревом особого вида, это достаточное условие является также и необходимым. Некоторые достаточные условия равенства ß(M) = 1 получены Сузуки и Ямашито в [79].

Если M является решёткой (см., например, [41] с. 227), то, как показано в работах [77, 78], сформулированная выше задача связана с проблемами координации движений роботов.

В цикле работ [15, 16] вводится другое обобщение задачи о поисковом числе графа, существенное отличие которого от задачи о нахождении e-поискового числа заключается в ином определении метрики на графе.

Пусть G — топологический граф, введём метрику dа на графе. Положим а-{х,х) = 0 для любого д; 6 б. Если х,у е С, х Ф у, то йо-(х,у) совпадает с минимальным натуральным к, таким, что путь из х в у, полностью лежащий в графе, пересекает к рёбер.

Зафиксируем к е N. Убегающий считается пойманным, если в некоторый момент он сблизится с хотя бы одним из преследователей на расстояние к во введённой метрике с^. Минимальное число преследователей, необходимое для поимки убегающего в описанной задаче, называется к-поисковым числом и обозначается сг^(С). Следует отметить, что при к = 0 ¿-поисковое число совпадает с рёберно-поисковым числом, а при к = 1-е 1-поисковым числом, рассмотренным в работах [32, 33]. Заметим, что ¿-поисковое число является топологическим инвариантом графа. Как показано в [16], задача определения ¿-поискового числа сводится к дискретной задаче, и вследствие этого она может быть эффективно решена для некоторых классов графов.

Так в работе [16] задача нахождения ¿-поискового числа решена для графов интервалов, что позволяет также выписать точные формулы для полных графов, теоремы о ¿-поисковых числах графов правильных многогранников приведены в работах [16, 27].

Завершим обзор задач гарантированного поиска, отметив работу [59], содержащую достаточно полную библиографию по исследуемому вопросу, и перейдём к описанию результатов по теории ^-поиска.

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

Для произвольного графа е-поисковое число, как и рёберно-поисковое число, может быть вычислено с помощью конечной процедуры (см. [12, 13]). Приведём здесь результат [12], позволяющий при исследовании е-поисковых чисел ограничиться рассмотрением программ преследователей специального вида.

Пусть £ > О, я£(С) < п, п € N. Тогда существует выигрывающая программа П команды п преследователей на С такая, что в каждый момент времени из множества задания программы П на любом ребре графа С находятся не более двух преследователей.

Это утверждение можно усилить, если рассматривать достаточно малый радиус поимки.

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

Работа П. А. Головача [12] содержит фундаментальные результаты. В частности, показано, что 5В(С) как функция радиуса поимки — невозраста-ющая кусочно постоянная непрерывная справа функция.

Там же доказано совпадение рёберно- и е-поисковых чисел для радиусов поимки меньших четверти длины кратчайшего ребра, а для всех в, меньших половины длины кратчайшего ребра графа С, имеют место следующие неравенства: ея(С) - 1 < <

Ещё одна оценка ^-поискового числа для радиуса поимки, меньшего длины кратчайшего ребра графа, опубликована в [28], для её описания нам понадобятся некоторые дополнительные определения.

Обозначим через С (у) подграф графа С, порождаемый множеством смежных с v вершин, а через у) — число компонент связности графа С (у) с ровно к вершинами. Определим величины оо и c(G) := min c(G, v). veVG

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

1. se(G) > c(G);

2. если для каждой вершины v е VG все коэффициенты v) с нечётными номерами к равны 0, то se(G) > c(G) + 1.

Приведённые выше утверждения позволили построить функции Головача для одномерных остовов тетраэдра, куба и октаэдра с рёбрами единичной длины (см. [17, 28, 58]). Решение задачи s-поиска для полных графов приводится в [17, 28]. Изучение рёберно-поискового числа для соответствующих графов икосаэдра и додекаэдра проводится в [18].

Перейдём к изложению основных результатов диссертации. Работа состоит из введения и трёх глав. Основные результаты настоящего исследования опубликованы в работах [1,2, 4-6, 44].

1. Абрамовская Т. В. Нетривиальные разрывы функции Головача для деревьев // Вестник СПбГУ. Сер. 1. 2010. № 3. С. 3-12.

2. Абрамовская Т. В. Проблема реализуемости функции со свойствами функции Головача // Вестник СПбГУ. Сер. 1. 2012. № 2. С. 3-10.

3. Абрамовская Т. В., Петров Н. Н. Геометрические проблемы теории поиска // Труды математического центра имени Н.И.Лобачевского: Материалы VIII научной школы-конференции Лобачевские чтения 2009. Казань: Казан. матем. об-во, 2009. Т. 39. С. 1-10.

4. Абрамовская Т. В., Петров Н. Н. О некоторых задачах гарантированного поиска на графах // Вестник СПбГУ. Сер. 1. 2010. № 2. С. 64-70.

5. Абрамовская Т. В., Петров Н. Н. О монотонности поискового числа в задаче Головача. Вестник СПбГУ // Вестник СПбГУ. Сер. 1. 2011. № 4. С. 3-9.

6. Абрамовская Т. В., Петров Н. Н. О сколь угодно больших скачках функции Головача для деревьев // Вестник СПбГУ. Сер. 1. 2011. № 1. С. 84-93.

7. Абрамовская Т. В., Петров Н. Н. Теория гарантированного поиска на графах // Дифференциальные уравнения и процессы управления. 2012. Т. 2. С. 9-65. URL: http://www.math.spbu.ru/diffjournal/RU/numbers/ 2012.2/article.165.html.

8. Айзеке Р. Дифференциальные игры. Москва: Мир, 1967.

9. Ахо А. В., Хопкрофт Д., Ульман Д. Д. Структуры данных и алгоритмы. Москва: Вильяме, 2003.

10. Головач П. А. Об одном топологическом инварианте в задачах преследования // Дифференциальные уравнения. 1989. Т. 25(№6). С. 923-929.

11. Головач П. А. Эквивалентность двух формализаций задачи поиска на графе//Вестник ЛГУ. Сер. 1. 1989. Т. 1(№1). С. 10-14.

12. Головач П. А. Об одной экстремальной задаче поиска на графах // Вестник ЛГУ. Сер. 1. 1990. Т. 15(№3). С. 16-21.

13. Головач П. А. Экстремальные задачи поиска на графах: Кандидатская диссертация/ЛГУ. 1990.

14. Головач П. А. Минимальные деревья с данным поисковым числом // Дискретная математика. 1992. Т. 4(№2). С. 52-60.

15. Головач П. А., Петров Н. Н. Некоторые обобщения задачи о поисковом числе графа//Вестник СПбГУ. Сер. 1. 1995. Т. 15(№3). С. 21-27.

16. Головач П. А., Петров Н. Н. /Г-поисковое число графов правильных многогранников//Вестник СПбГУ Сер. 1. 1995. Т. 22(№4). С. 8-13.

17. Головач П. А., Петров Н. Н., Фомин Ф. В. Поиск на графах // Труды института математики и механики УрО РАН. 2000. Т. 6(№1). С. 39-54.

18. Головач П. А., Фомин Ф. В. Поисковое и вершинно-поисковое число двой-, ственных графов // Вестник СыктГУ. Сер.1. 2001. № 4. С. 125-136.

19. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. Москва: Мир, 1982.

20. Зеленевская А. Б., Петров Н. Н. О некоторых задачах поиска на графах с противодействием // Вестник СПбГУ. Сер. 1. 2004. № 2. С. 23-33.

21. Зеликин М. И. Об одной дифференциальной игре с неполной информацией //Доклады АН СССР. 1972. Т. 202(№5). С. 998-1000.

22. Зыков А. А. Основы теории графов. Москва: Вузовская книга, 2004.

23. Капилевич В. О., Петров Н. Н. Задачи поиска на графах с противодействием // Вестник СПбГУ. Сер. 1. 2003. № 3. С. 31-37.

24. Кнут Д. Э. Искусство программирования, том 1. Основные алгоритмы, 3-е изд. : Пер. с анг. Москва: Вильяме, 2001.

25. Петров Н. Н. Задачи преследования при отсутствии информации об убегающем // Дифференциальные уравнени. 1982. Т. 18(№8). С. 1345-1352.

26. Петров Н. Н. Некоторые экстремальные задачи поиска на графах // Дифференциальные уравнени. 1982. Т. 18(№5). С. 821-827.

27. Петров Н. Н. Задачи поиска на графах правильных многогранников // Дискретная математика. 1996. Т. 8(№2). С. 108-116.

28. Петров Н. Н. Преследование невидимого подвижного объекта // Дифференциальные уравнени. 1996. Т. 32(№8). С. 1563-1565, 1583.

29. Петров Н. Н., Старостина С. А. Минимальные графы с поисковым числом меньшим четырёх // Вестник СПбГУ. Сер. 1. 1989. № 3. С. 105-106.

30. Петров Н. Н., Старостина С. А. О некоторых задачах гарантированного поиска//Вестник СПбГУ. Сер. 1. 1994. № 1. С. 114-116.

31. Петров Н. Н., Тетерятникова М. А. О некоторых задачах поиска на графах с противодействием // Вестник СПбГУ. Сер. 1. 2004. № 3. С. 50-59.

32. Петров Н. Н., Туре И. Об одной задаче преследования на графе // Вестник ЛГУ. Сер. 1. 1990. Т. 4. С. 12-18.

33. Петров H. H., Type И. Определение минимальной численности группы поиска на графе // Вестник ЛГУ. Сер. 1. 1991. Т. 4. С. 66-69.

34. Петров H. Н., Чуманова А. В. О некоторых проблемах поиска на графах с противодействием // Вестник СПбГУ. Сер. 1. 2003. № 4. С. 51-57.

35. Петросян Л. А., Гарнаев А. Ю. Игры поиска. Санкт-Петербург: СПбГУ, 1992.

36. Старостина С. А. Задачи преследования на графах при отсутствии информации об убегающем: Кандидатская диссертация / СПбГУ. 1993.

37. Фомин Ф. В. Задача поиска на деревьях // Вестник СПбГУ. Сер. 1. 1995. Т. 8(№2). С. 36-4\.

38. Фомин Ф. В. Поиск на 3-минимальных деревьях // Вестник СПбГУ. Сер. 1. 1995. Т. 15(№3). С. 67-72.

39. Фомин Ф. В. Задачи преследования и поиска на графах: Кандидатская диссертация / СПбГУ. 1996.

40. Фомин Ф. В., Петров H. Н. Дискретные программы поиска на графах // Вестник СПбГУ. Сер. 1. 1999. Т. 1(№1). С. 29-35.

41. Харари Ф. Теория графов. Москва: Мир, 1973.

42. Abramovskaya T. V., Petrov N. N. Graph searching games with a radius of capture // Game Theory and Management, Collected abstracts, Ed. by L. A. Petrosyan, N. A. Zenkevich. SPb.: Graduate School of Management, 2010. P. 12-13.

43. Abramovskaya T. V., Petrov N. N. Graph searching games with a radius of capture // Contributions to Game Theory and Management, Ed. by L. A. Pet-rosyan, N. A. Zenkevich. SPb.: Graduate School of Management, 2011. Vol. IV. P. 8-18.

44. Alpern S. The search game with mobile hider on the circle // Differential Games and Control Theory, In proceedings of Conference Board of the Mathematical Sciences, Kingston, Rhode Island, June 4-8, 1973. M. Dekker, 1974. P. 181-200.

45. Alpern S., Gal S. The theory of search games and rendezvous. Springer, 2003. Vol. 55 of International Series in Operations Research and Management Science.

46. Bienstock D., Seymour P. Monotonicity in graph searching // J. Algorithms. 1991. Vol. 12. P. 239-245.

47. Bodlaender H. L. A tourist guide through treewidth // Acta Cybernt. 1993. Vol. 11. P. 1-21.

48. Breisch R. An intuitive approach to speleotopology // Southwestern Cavers. 1972. Vol. VI. P. 72-78.

49. Breisch R. L. Lost in a Cave-applying graph theory to cave exploration. Huntsville, Alabama: National Speleological Society, 2012.

50. Chung F. R. K. Labelings of graphs // Selected Topics in Graph Theory. New York: Academic Press, 1988. Vol. III. P. 151-168.

51. Chung F. R. K., Seymour P. D. Graphs with small bandwidth and cutwidth // Discrete Math. 1989. Vol. 75. P. 113-119.

52. Ellis J. A., Sudborough I. H., Turner J. S. Graph separation and search number//Inform. and Comput. 1994. Vol. 113. P. 50-79.

53. Fomin F. V. Helicopter search problems, bandwidth and pathwidth // Discrete Appl. Math. 1998. Vol. 85. P. 59-70.

54. Fomin F. V. Note on a helicopter search problem on graphs // Discrete Appl. Math. 1999. Vol. 95. P. 241-249.

55. Fomin F. V., Golovach P. A., Petrov N. N. Search problems on 1-skeletons of regular polyhedrons // International Journal of Mathematics, Game Theory and Algebra. 1998. Vol. 7. P. 101-111.

56. Fomin F. V., Thilikos D. M. An annotated bibliography on guaranteed graph searching // Theoretical Computer Science. 2008. Vol. 399(№3). P. 236-245.

57. Gal S. Search Games. New York: Academic Press, 1980.

58. Garnaev A. Y. A remark on the Princess and Monster search game // International journal of Game Theory. 1991. Vol. 20. P. 269-276.

59. Hopcroft J., Paul W. J., Valiant L. On time versus space // Journal of the ACM. 1980. Vol. 24. P. 332-337.

60. Kirousis L. M., Papadimitriou C. H. Interval graphs and searching // Discrete Math. 1985. Vol. 55. P. 181-184.

61. Kirousis L. M., Papadimitriou C. H. Searching and pebbling // Theoret. Com-put. Sci. 1986. Vol. 47. P. 205—218.

62. Lai Y. L., Williams K. A survey of solved problems and applications on bandwidth, edgesum, and profile of graphs // Journal of Graph Theory. 1999. Vol. 31(2). P. 75-94.

63. LaPaugh A. Recontamination does not help to the search a graph // Journal of ACM. 1993. Vol. 40. P. 224-245.

64. Lipton R. J., Tarjan R. E. Applications of a planar separator theorem // SIAM J. Comput. 615-627. Vol. 3. P. 1980.

65. Makedon F. S., Papadimitriou C. H., Sudborough I. H. Topological bandwidth // SIAM J. Algebraic Discrete Methods. 1985. Vol. 6. P. 418—444.

66. Makedon F. S., Sudborough I. H. Min Cut is NP-complete for edge weighted trees // Theor. Computer Sci. 1988. Vol. 58. P. 209-229.

67. Megiddo N., Hakimi S. L., Garey M. R. et al. The complexity of searching a graph // J. Assoc. Comput. Mach. 1988. Vol. 35. P. 18-44.

68. Parsons T. D. Pursuit-evasion in a graph // Theory and Applications of Graphs. Y. Alavi and D. R. Lick, eds, Springer-Verlag. 1978. Vol. 642. P. 426^41.

69. Scheffler P. A linear algorithm for the pathwidth of trees // Topics in combinatorics and graph theory, In Collection. Heidelberg: Physica-Verlag, 1990. P. 613—620.

70. Scheffler P. Optimal embedding of a tree into an interval graph in linear time // Fourth Czechoslovakian Symposium on Combinatorics, Graphs and Complexity Ann. Discr. Math., North-Holland. 1992. Vol. 51. P. 287-291.

71. Seymour P. D., Thomas R. Graph searching and a min-max theorem for tree-width //J. of Comb. Theory. Ser. B. 1993. Vol. 58. P. 22-33.

72. Sugihara H., Suzuki I. On pursuit-evasion problem related to motion coordination of mobile robots // System Sciences, In proceedings of 21st International Conference on, Kailua-Kona, Hawaii, 1987 / Ed. by G. M. Glasford, K. Jab-bour. 1988. P. 218-226.

73. Suzuki I., Yamashita M. Searching for a mobile intruder in a polygonal region // SIAM J. Comput. 1992. Vol. 21. P. 863-888.

74. Tosic R. Search number of the cartesian product of graphs // Zbornik Radova Prirodno-matematickog fakulteta Univerziteta u Novom Sadu, Serija za matem-atiku. 1987. Vol. 17(№1). P. 239-243.

75. Yannakakis M. A polyminal algorithm for the min-cut lineal arrangement of trees//J. of ACM. 1985. Vol. 32. P. 950-988.