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

На правах рукописи ТУРЕ Ибрай^а

НЕКОТОРЫЕ ЗАДАЧИ ПРЕСЛЕДОВАНИЯ НА ГРАШ 01.01.09 - Математическая кибернетика

Автореферат

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

- ^ '

. 1 .

САНКТ-ЕЕГЕРБУРГСКШ ГОСЭДАРСГЕЕНШЙ УНИВЕРСИТЕТ

евваггаасзаэяавзаазвакааявавазаа&вапееявавмаа

САКС1-1ЕГЕРБУРГ 1992

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

Научный руководитель: доктор физико-математических наук, профессор ПЕТРОВ H.H.

Официальные оппоненты; доктор физикс-мате.мt..и48схих наук,

профессор МАЛАШЕВ С.А.; кандидат физико-математических наук, доцеи.!' ТКА.ЧЕШ0 Г.Г.

Ведущая организация - Московский государственный

университет им.И.В.Ломоносова

Защита диссертации состоится в I, Ц~ час. на заседании специализированного совета Н 063.57.49 по присуждению ученой степени кандидата физико-математических наук в Санкт-Петербургском государственном университете по адресу: 198904, Санкт-Петербург, Старый Петергоф, Библиотечная пл.,

С диссертацией можно ознакомиться в библиотеке Сонкт-Яетер^ргского государств-лного университета.

Ученый секретарь специализированного

совета, кандидат фнз.-мат. наук ШЕПЕЛЯВЫЙ А.И.

ОЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ Актуальность теми. Срзди задач, которые стоят перед со-

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

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

В некоторых из этих задач предполагается, что поиск осуществляется группой преследователей, причем в этих задачах возможность■поимки очевидна, если численность этой группы достаточно велика. Поэтому осяовноК целью исследования является определение минимального числа преследователей, необходимого для успешного заверпения пояска. Игры подобного рода, относящиеся к проблемам "Принцесса и Чудовище" и "Полицейские и Грабитель", в настоящее время хорошо известны, некоторые из них были рассмотрены Р.Аизексом в его известной монографик. Одна из них - проблема "Принцесса и Чудовице" на окружности в случае одинаковых максимальных скоростей участников - решена М.И.Зеликиньм в работе * . Некоторые результаты в задачах поиска на двумерных множествах бкли получены Галом, Згицжераль-дом, А.Ю.Гарнаевым и другими. Проблема "Полицейские и Грабитель" на графах была рассмотрена в ряде работ Айгнера и Фромма, Андрее, И.М.Асельдеровой и другими.

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

Задачу, рассматриваемые в данной работе, отяичаотся от вышеупомянутых задач тем, '-¡то поиск на графе считается завершенным успепно, если один из преследователей и убегаяций оказываются, та замдаашм одного ребра, и тем, что стадится задача гарантированного поиска. Считается, что убегающий располагает полкой информацией о всех действиях преследователей во время поиска до начала самого поиска. Основной цзлыо является определение мккгсладького числа преследователей, необходимого • для успешного завершения поиска. Задачи такого типа изучены з работах К.К.Петрова, Парсонса, Гери, Дконсона и Пап. ,имкт-риу, Македона и Садборо, Кироузиса, П.А.Головача и др. (см., напрел ер, .

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

о

Яетроэ Н.Н. Экстремальные задачи пояска на графах !/ Дкфф. уравнения. - 1982. - Т.18, 1». - С.621-827.

J Петр 1 Н.Н. Задачи преследования прк отсутствии информации об убегающем // Дифф. уравнения. - 1982. - Т.18, ¥3. - С.1245-1357

* Рагзозз Б.Т. Pursuit-evaaioa in a e*nph // Lecture

ITotes in. Eatiu - 1978. - V.642. - P.4Z6-441. 5

ilegiddo ¡1., Ilakiui S.I., Carey 1!.R,, Johaeon. 3.S., rar?adlcitriou O.K. The complexity of cearehiag а graph /.' ¿.оt the Assoc. ior Computing l^ohinery. - 19Q8. - V.35,

HI. - P.10-44.

£

¿akedoa jF.S., Sajudiniiriou C.H., Sudti or ougb. Т.Н. Topological Ъ .«-width // SIAK J. in Alg. Dice. Math. -19S5. - V.6, КЗ. - P.413-i + 3.

7

rrouolB L.II., ?anadimi triou C.B. Ir'eriral graphs ood sieerobite // Di.eo. Math. - 1585. - V.55, »2. - P.131-10/,.

Q

Голозач П.А. Экстремальные задачи поиска на графах: Дис. ... канд. физ.-мат. наук /ЛГУ. - Л., 1990.

б.

Научная коаизна. В диссертации вводится и изучается новый комбинаторный инзариан? графа ( <£ - поисковое число), имеющий простую теоретико-игровую интерпретацию. Указан способ определения этого инварианта для произвольного графа. Найдены величины -I -поискового числа для деревьев и одномерных остовов правильных многогранников. Все основные результаты диссертации, представленной к защите, являются новыми.

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

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

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

Структура и объем работы. Диссертация состоит из введения, четырех глав, списка литература и 35 рисунков. Объем работы составляет 89 страниц машинописного текста. Библиография содержит 88 наименований.

СОДЕРЖАНИЕ ДИССЕРТАЦИИ

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

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

В разделе 1.1 излагается принятая в данной работе формализация задачи поиска. Пусть Г - конечный связный граф, который нам удобно предполагать вложенным в некоторое евклидово пространство. Будем считать также, что ребра Г представляют собой ломаные линии. На множестве Г рассматривается следувцая

задача преследования. Преследователи , i е 1(П. к убегающий S обладают простыми двинекикки

(Ш: Хг-а; , Iе í~r\. ; (Е) : V?

(ограничения на скорости отсутствуют). Допустимыми управлениями участников являэтся кусочно-аффинные вектор-функции, заданные ка произвольных компактных промежутках [0,Т] и поро?ш,аюш!г траектории со значениями в Г. Под программой будем понимать совокупность траекторий преследователей

П = £xitt), ie [o,Tj ]■ . Эту программу назовем

выигриЕ&оцей, если для всякой траектории убегабщего y.(t) ,

te [0,1] . найдутся момент £е[Ъ,Т] , ребро ЕГ и номер i,П. такие, что Q (черта означает

замыкание). Б случае, если выигркзазсщая программа существует, будем говорить, что группа преследователей может осуществить -6 -поимку, Б противном случае будем говорить, что возможно уклонение от встречи. Наименьшее число преследователей, необходимое для осуществления -поимки на графе Г, казызается J¿ -поисковым числом графа. Г и обозначается через .

3 разделе 1.2 доказываются зажные свойства деревьев ПХ -й степени -i -ветвления. Будем говорить, что связный граф Г0 является подграфом графа Г (и обозначать íjhc Г ), если все верлины ío являются вершинами Г и все ребра Г0 являются ребрами Г. Пусть Г - дерево. Дерево L называется стволом дерева Г, если Lee Г и L гомесморфно отрезку или точке. Ветвью ствола L дерева Г казьиается подграф дерева Г, совпадающий с замыканием некоторой связной компоненты множества Г\ L • Звездой с центром в вершине OCq в дереве Г называемся его подграф, состоящий из вершины Х0 , всех смежных с ней верши Х| , , ... , Xt ( К > 2) и всех ребер (Хс,ЗС|),(Хо,Ха), (Хо.Хк) .Дерево R называется Z -стволом дереьа Г, если существует ствол LccR такоГ, что каждая его ветвь в R является либо авездой, либо замыканием ребра. Пусть Ree Г - £-ствол дерева Г. Тогда -Í -зетвь» t -ствола R в Г называется подграф дерева Г, со-впадаоций с замыкание« некоторой связной компоненты множест-

ва ТЛЯ . Для всех деревьев индуктивно определим некоторую характеристику, хотору» мы называем степенью <1 -ветвления (и обозначаем через^$ (Г) )• Все. ¿-стволы и только их мы будем называть деревьями первой степени £ ^-ветвления. Будем говорить, что дерево Г имеет степень ¿-ветвления » если в нем существует -ствол ,

все £ -ветви которого лыеют степени -ветвления < т . Пусть Фт - мнокество всех деревьев степени £ -ветвления 4,ЦТ- • Будем говорить, что дере^ Г имеет степень & -ветвления Д(Г) = пг , если Те ФпЛЯйч-

Лемма 1.2.1. Пусть 'П, и Г - деревья и Т^ссГ . Тогда

Пусть Г - дерево и =» Ш. • Ветвь Б вершины ЗСоеУГ '

называется хорошей, если существует £ -ствол Ясс В , являющийся звездой такой, что I) Хо является концевоЧ вершиной Я ; 2) существует такая -ветвь У £ -ствола Я ,

что )цф>т-1. И • "

Теорема 1.5.2. Пусть Г - дерево, _/Ц(Г) = т . Тогда , существует одноточечный ствол (ворсина), имеющий по крайней пере три хорошие зетви.

3 разделе 1.3 изучается величина для деревьев. -

Основные результаты этого раздела - теоремы 1.3.3 и 1.3.4. Теорема 1.3.3. Для всякого дерева Г Х{(Г) " (Г) . Пусть 5т - мнокество всех деревьев, имеющих не более щ ребер, и пусть & т. - каименьиее число преследователей, необходимое для осуществления Ь -поимки на л»боа дереве из 5т . Тогда справедлива следующая

Теорема 1.3.4. СЗСт равно числу цифр в троичной записи числа , т.е. целой части числа ^^

В гласа П под графом понижается одномерный С\"/ -комплекс. Требуется найти минимальное натуральное число П. . для которого существует совокупность непрерывных отображений: Хи: [рТ] —* Г) I е , О < Т<, обладающая следующим свойством: для всякого непрерывного отображения у.: £о,Т]~>Г существуют 1е[о,Т] , и ребро €<зЕГ. такие, что

точки ОС^Ш и иШ оказывается на замыкании в ребра 6 .

Это число мы называем ь -поисковым числом графа Г. Целью это?? глазы является описание конечного алгоритма вычисления этой величины.

В гл.1 бала использована другая формализация, которая отличается от данной там, что траектории преследователей и убегающего являются нуе.очно-аффиннымн отображениями. В разделе 2.1 показано, что обе зтк формализации эквивалентны. Наиболее важные утверждения в разд.2.1 - этс леммы 2.1.2 и 2.1.3. Пусть Г - граф в предположении главы I.

Др-\ма 2.1.2. Если на Г существует непрерывная выкрывающая программа, то на Г суцеснует выигрывающая программа, состоящая из кусочно-аффинных отображений с тем же числом преследователей.

Лемма 2.1.3. Если существует непрерывная траектория убе-гаацего, уклоняющаяся от программы Г1 , то существует кусочно-аффинная траектория, уклоняющаяся от программы П •

Б разделе .2.2 доказывается теорема существования простейшей выигрывающей программы. Важный результат сформулирован в следующем утверждении. /

Лемма 2.2.1. Пусть грар Г получается из графа Г следующим образом: каждая петля Р заменяется висячим ребром и все ребра, соединяющие какие-либо двз смежные вершины, заменяются одним ребром. 1'огда <К$,(Г) «= .

Пусть Г - топологический граф, ребра которого суть ко-нечнозвенныа ломаные. Программа П П преследователей на Г называется прос:е8оей, если она задана на промежутке £о, тЗ , где т.е.Л' , в моменты 0,1,2, ... ,ГП все преследователи находятся в вершинах Г, а га интервалах ( к-1, к ) при

ке 17т ровно один преследователь переходит из вершины в верши.^ по соединяющему их ребру с постоянной скоростью, в то же время остальные преследователи стоят в вершинах. Имеет место следующая теорема.

Теорема 2.2.1. Если на графе Г 1г преследователей имеют выигрывающую программу, то существует и простейшая выигрывающая программа с тем же числом преследователей.

В разделе 2.3 дается алгоритм вычисления величины ЗЦ(Г),

где Г - произвольный граф.

В глазе £1 найдены величины Г), где Г .- одномерный остов некоторого правильного мкогограчника. Эта глаза содержит три раздела. 3 разд. 3.1 определяются величины ,Ж£,(Г) для тетраэдра, куба и октаэдра. Здесь показано, что для тетраэдра, куба а октаэдра -поисковое число равняется 2. 3 разд.3.2 доказано, что -поисковое число для икосаэдра равно 3. В разд.3.3 показано, что для додекаэдра -поисковое число равно 4.

В глазе 1У рассматривается задача поиска "увидел - поймал". Пусть множество М е К"1 • На М находятся преследователи и убегающий. Траектории преследователей и убегающего считаются непрерывными функциями, заданными на [0,Т] со значениями в множестве АЛ : ЭС»,: [о,Т]—М и у.: [0,Т]-*» -> М . Убегающий считается пойманным преследователем {3 в момент "1е(р,Т] , если отрезок [Хг(1)>у(!)Дс М . Цель» является определение кинжального числа, необходимого для поимки убегающего вне зависимости от его действий. Эта величина для множества М обозначается через &(М).

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

Глава 1У состоит из двух разделов. В разд.4.1 дается формальная постановка задачи. В разд.4.2 рассматривается задача "увидел - поймал" доя случая дзумерных остозов правильных многогранников. Здесь показано, что величина СС(М) для тетраэдра, куба и октаэдра равна 2, а для икосаэдра и додекаэдра достаточно трех преследователей.

Основные сезультати диссертации, представленные к защите:

1. Доказательство существования конечного алгоритма вычисления I -поискового числа для произвольного графа.

2. Вычисление 4 -поискового числа для деревьев.

3. Нахождение -поискового числа для одномерных остовов правильных многогранников.

10.

4. Вычисление некоторых инвариантов в играх поиска на произвольных множествах.

Основные результаты диссертации опубликованы в работах:

1. Петров H.H., Т|уре И. Об одной задаче преследования на графе // Вести. ЛГ*. Cep.I. - 1990. - Еып.4, W22. -

Ц.12-18.

2, Петров H.H., itype И. Определение минимальной численности группы поиска ка графе // Вестн. ЛГУ. Cep.I. - 199I. -Вып.2, Кб. - C.ff^-ijß.