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

• Автор: Абрамовская, Татьяна Викторовна
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2012
• Место защиты: Санкт-Петербург
• Количество страниц: 114 с. : ил.

Содержание
Введение

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

L(a,) и не содержащее L(a), i = 1
Обходом дерева Т с корнем в фиксированной вершине в прямом порядке называется нумерация L вершин дерева Т, организованная в соответствии со следующим рекурсивным алгоритмом: а) нумеруется корень; Ь) последовательно обходятся в прямом порядке все максимальные поддеревья с корнями в вершинах, смежных с корнем рассматриваемого дерева ([24] с. 381).
Таким образом, для дерева Т и его произвольной вершины а 6 VT может быть построена нумерация L его вершин в соответствии с обходом его комбинаторной схемы Т с корнем в вершине L(a) в прямом порядке, где L(a)
Простой пример приведён на рис. 1.1— рассматривается дерево с корнем в вершине а.

Рис. 1.1. Комбинаторное дерево с корнем в вершине а и введённой на нём нумерацией вершин в соответствии с обходом этого дерева в прямом порядке
Важным для дальнейшего изложения является следующее свойство описанного алгоритма построения нумерации вершин дерева в прямом порядке: листья одного родителя получают последовательные номера.
Далее в работе не будет указываться нумерация дерева Т, с помощью которой строится его комбинаторная схема Т, она будет полагаться произвольной, а корень для комбинаторной схемы будет определяться указанием вершины а е УТ самого дерева Т, имея в виду её номер в соответствующей нумерации.