Конечная теория гарантированного поиска
Конечная теория гарантированного поиска (КТГП) — раздел теории гарантированного поиска, в котором изучаются свойства дискретного поиска на комбинаторных графах. Причём бывает полено вместо комбинаторного представлять граф топологический.
Большинство утверждений КТГП доказывается методами теории графов. Поиск на графе определяется как совокупность некоторых отображений множеств целых неотрицательных чисел во множество вершин графа . Поиску и целому неотрицательному числу всегда сопоставляется подграф графа , называемый исследованной областью[1].
Понятия теории графов, такие как минор графа, остов графа, путевая ширина, кликовое число, не являются предметом КТГП, но активно ею используются. КТГП включает следующие разделы: вычисление поисковых чисел и оптимального времени поиска, операции над графами и поисками на них, классификация графов относительно их поисковых чисел[источник не указан 711 дней].
Для постановки задачи поиска на графах достаточно было средств времён Эйлера, однако первые содержательные результаты то этой теме появились лишь к концу 1980-х годов. Основополагающие работы принадлежат: Николаю Петрову[2], Торренсу Парсонсу[3], Андреа Лапо[4], Фёдору Фомину[5], Петру Головачу[6].
См. также[править | править код]
Примечания[править | править код]
Литература[править | править код]
- Абрамовская Т. В., Петров Н. Н. Теория гарантированного поиска на графах. — Вестник Санкт-Петербургского университета, 2013. — С. 3—35.
- Головач П. А. Об одном топологическом инварианте в задачах преследования. — Дифференциальные уравнения, 1989. — С. 923–929.
- Петров Н. Н. Задачи преследования при отсутствии информации об убегающем. — Дифференциальные уравнения, 1982. — С. 1345–1352.
- Fomin F. V., Thilikos D. M. An annotated bibliography on annotated graph searching. — Theoretical Computer Science, 2008. — С. 236—245.
- Lapaugh A. Recontamination does not help to search a graph. — Princeton University: Tech. Report 335, Dept. of Elec. Eng. and Comput. Sci., 1993.
- Torrence D. Parsons. Pursuit-evasion in a graph // Theory and Applications of Graphs. — Springer-Verlag, 1976. — С. 426–441.