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

Содержание
Введение
Глава 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. Проблема реализуемости функции, обладающей свойствами функции Головача .
Литература