Введение к работе
ітаїіий І Актуальность теми. Срзди задач, которые стоят перед со-—временной теорией дифференциальных игр, особое место занимают задачи преследования и поиска. Среди них важное место занимают задачи, связанные с преследованием (поиском) группой преследователей (возможно, состоящей из одного преследователя) одного убегающего, на различных' множествах, при различных правилах поведения игроков (преследователей и убегающего) и при различных условиях завершения поиска.
Круг этих задач весьма широк. Сюда, например, относятся разнообразные дифференциальные игры, дискретные задачи преследования (поиска) и кногие другие задачи. Среди задач преследования и поиска группой преследователей одного убегающего длт нас представляют особый интерес различные задачи на графах.
В некоторых из этих задач предполагается, что поиск осуществляется группой преследователей, причем в этих задачах возможностьпоимки очевидна, если численность этой группы достаточно велика. Поэтому осяовноК целью исследования является определение минимального числа преследователей, необходимого для успешного заверпения пояска. Игры подобного рода, относящиеся к проблемам "Принцесса и ^довище" и "Полицейские и Грабитель", в настоящее время хорошо известны, некоторые из них были рассмотрены Р.Аизексом в его известной монографик. Одна из них - проблема "Принцесса и Чудовитце" па окружности в случае одинаковых максимальных скоростей участников - решена Й.И.Зеликиньм в работе * . Некоторые результаты в задачах поиска на двумерных множествах бьии получены Галом, Фицкераль-дом, А.Ю.Гарнаевым и другими. Проблема "Полицейские и Грабитель" на графах была рассмотрена в ряде работ Айгнера и Фромма, Андрее, И.М.Асельдеровой и другими.
1 Зеликин И.М. Об одной дифференциальной игре с неполной информацией // Докл. АН СССР. - 1972. - Т.202, №3. -С.998-1000.
4.
Задачу, рассматриваемые в данной работе, отяичаотся от вышеупомянутых задач тем, vm поиск на графе считается завершенным успепно, если один из преследователей и убегающий оказываются на заі-ижашм одного ребра, и тем, что ставится задача гарантированного поиска. Считается, что убегающий располагает полкой информацией о всех дойстзиях преследователей во время поиска до начала саг/ого пояска. Основной цзлыо является определение мкнкодльнога числа преследователей, необходимого для успешного завершения поиска. Задачи такого типа изучены з работах Н.Н.Петрава, Парсонса, Гери, Дконсона и Пап., ,имкт-риу, Македона и Садборо, Кироузиса, П.А.Головача и др. (см., например, ~ .
Цельо диссертационной работы является изучение зедач поиска на графах, а также вычисление связанных с ними инвариантов в различных частные случаях (для деревьев, одномерных остовов правильных многогранников и т.д.).
Яетроэ Н.Н. Экстремальные задачи пояска на графах // Дифф..уравнения. - 1982. - Т.18, »5. - С.621-827.
й Петр -\ Н.Н. Задачи преследования при отсутствии информации об убегадацем // Дифф. уравнения. - 1982. - Т.13, VS. - C.I245-I357
Рагаоаз В.Т. Pursuit-evaaioa in a e*npb // Lecture
Kotes in. Eatti. - 1978. - V.642. - P.42S-441. 5
ilegiddo N., Hakiul S.I., Carey U.K., Johaeou 3.S.,
Papadici-triou 0.51. The complexity of cearahi&g a graph /,'
J. ot the Assoc, tor Computing J^ohinery. - 19Q8. - V.35,
HI. - P.10-44.
A-'akedoa JF.S., Sajuainiiriou O.H., Sudborougb. I.H. Topological Ъ .«-width I/ SIA1J J. mi Alg. Dice. Math. -19S5. - V.6, N3. _ P.413-4 + 3.
T rouulB b.H., Panadimitriou C.B. Ir'eriral graphs ood s«cerohia« // Dleo. Math. - 1585. - V.55, K2. - P.131-104.
Ґолозач П.А. Экстремальные задачи поиска на графах: Дис. ... канд. физ.-мат. наук /ЛГУ. -Д., 1990.
б.
Научная нозизна. В диссертации вводится и изучается новый комбинаторный инзариант графа ( -Е - поисковое число), имеющий простуй теоретико-игровую интерпретацию. Указан способ определения этого инварианта для произвольного графа. Найдены величины -Ї -поискового числа для деревьев к одномерных остовов правильных многогранников. Все основные результаты диссертации, представленной к защите, являются новыми.
Методы исследования. При исследовании использованы топологические и геометрические методы, методы дискретной математики, в частности теории графов, и теории управления.
Практическая ценность. Результаты работы, в основном, гасят теоретический характер и могут быть применены для дальнейшего изучения задач конфликтного управления и поиска.
Апробация работы и публикации. Основные результаты диссертации докладывались на семинарах кафедры исследования операций мятематико-механического факультета Санкт-Петербургского университета и опубликованы в работах 1,2 , приведенных в конце автореферата.
Структура и объем работы. Диссертация состоит из введения, четырех глав, списка литература и 35 рисунков. Объем работы составляет 89 страниц машинописного текста. Библиография содержит 88 наименований.