WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!


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

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

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

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

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

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата физико–математических наук

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

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

Научный консультант: доктор физико–математических наук, профессор Петров Николай Николаевич

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

Ведущая организация: Санкт–Петербургский экономико–математический институт РАН

Защита состоится « » 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. Доказано существование скачков сколь угодно большой высоты функции Головача для деревьев, а также возможность двух неединичных скачков функции Головача.

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

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

Апробация работы. Основные результаты диссертации докладывались на VIII молодёжной конференции «Лобачевские чтения–2009», КГУ, Казань, ноябрь 1–6, 2009 [2]; XLI международной научной конференции аспирантов и студентов «Процессы управления и устойчивость», ПМ-ПУ СПбГУ, Санкт–Петербург, апрель, 2010; IV международной конференции «Game Theory and Management», GTM2010, ВШМ СПбГУ, Санкт–Петербург, июнь 28–30, 2010 [3, 4]; семинаре кафедры исследования операций математико–механического факультета СПбГУ, апрель 2011 г.; Санкт–Петербургском городском топологическом семинаре под руководством проф. Н. Ю. Нецветаева, май 20г.; международной конференции «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] -– тезисы совместных докладов на международных конференциях на общую тему, где представлены как результаты автора, так и её научного руководителя.

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

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

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

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

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

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

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

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

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

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

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

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

Будем говорить, что функция Головача графа G имеет в точке = k(G) единичный скачок, если k(G) < k+1(G), скачок высоты l, если k(G) < k+l(G), а для всех 1 i < l выполняется равенство k(G) = k+i(G).

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

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

Будем говорить, что преследователь P –неблизок к точке a дерева T в некоторый момент t, если (a, x(t)) > .

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

Лемма 1.4.1. Пусть на дереве T существует вершина a, от которой отходят три ветви B1, B2, B3, для каждой из которых выполнено следующее:

в любой программе i команды P, выигрывающей в задаче –поиска на Bi, найдется момент времени, в который каждый из преследователей –неблизок к a, i = 1, 2, 3. Тогда команда P не может успешно завершить –поиск на T.

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

Рассмотрим дерево T, пусть Z = (a1, a2..., an) — произвольная цепь наибольшей длины в T. Поддеревья A1, A2,..., Am — ветви, отходящие от вершин цепи Z, содержащие только одну вершину цепи Z. Через lj обозначим длину наибольшей цепи в Aj, начинающейся в вершине цепи Z, j = 1, 2,..., m.

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

1(T) = max li.

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

Теорема 1.5.2. Если s0(T) > 1, то 2(T) < 1(T).

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

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

Теорема 1.6.1. Пусть T T (), и пусть k преследователей ловят убегающего с радиусом поимки на T. Тогда группа из k + 1 преследователей осуществляет –поимку на T при некотором < .

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

Рассмотрим произвольное дерево T, сопоставим ему набор (l1, l2,..., ln) (0, )n в соответствии с введённой нумерацией рёбер комбинаторной схемы дерева T, где li — длина i–го ребра дерева T. Пусть на множестве (0, )n введена стандартная топология произведения. Обозначим T (0, )n множество всех таких наборов (l1, l2,..., ln), что дерево с фиксированной комбинаторной схемой и соответствующими длинами рёбер имеет невырожденную функцию Головача.

Тогда имеет место следующая Теорема 1.7.2. Множество T открыто и плотно в (0, )n.

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

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

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

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

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

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

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

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

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

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

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

Будем называть –поисковое число монотонным для связного подграфа H графа G, если выполнено неравенство s(H) s(G).

В условии поточечной поимки ( = 0), указанное неравенство, очевидно, выполняется для каждого подграфа произвольного графа. Монотонность –поискового числа на деревьях при любом неотрицательном следует из доказанных в диссертации утверждений. Доказывается монотонность –поискового числа для малых радиусов поимки, а именно, верна следующая Теорема 3.1.2. Пусть G — граф, l — длина наименьшего ребра G, H — l произвольный связный подграф G. Тогда для всех 0 < выполнено неравенство:

sG() sH().

Результат последней Теоремы может быть улучшен для некоторых графов, содержащих полный подграф, так что имеет место следующая Теорема 3.2.1. Пусть граф G с рёбрами единичной длины содержит в качестве подграфа полный граф Kn, G не имеет кратных рёбер. Тогда для 0 < 1 выполнено неравенство:

s(G) s(Kn).

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

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

Теорема 3.2.2. Для n 5, функция Головача графа Kn совпадает с функцией Головача графа Kn-1.

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

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

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

Теорема 3.3.2. Функция f3 реализуема в классе M тогда и только тогда, когда 1 32.

Публикации автора по теме диссертации 1. Абрамовская Т. В., Петров Н. Н. Теория гарантированного поиска на графах // Дифференциальные уравнения и процессы управления. 2012. Т. 2.

С. 9–65. URL: http://www.math.spbu.ru/diffjournal/RU/numbers/ 2012.2/article.165.html.

2. Абрамовская Т. В., Петров Н. Н. Геометрические проблемы теории поиска // Труды математического центра имени Н.И.Лобачевского: Материалы 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. Petrosyan, 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. Petrosyan, 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 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–441.

13. Петров Н. Н. Задачи преследования при отсутствии информации об убегающем // Дифференциальные уравнени. 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.







© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.