Конечная теория гарантированного поиска

Конечная теория гарантированного поиска (КТГП) — раздел теории гарантированного поиска, в котором изучаются свойства дискретного поиска на комбинаторных графах. Причём бывает полезно вместо комбинаторного представлять граф топологический.

Большинство утверждений КТГП доказывается методами теории графов. Поиск на графе ${\displaystyle G}$ определяется как совокупность некоторых отображений множеств целых неотрицательных чисел во множество вершин графа ${\displaystyle G}$. Поиску и целому неотрицательному числу всегда сопоставляется подграф графа ${\displaystyle G}$, называемый исследованной областью^[1].

Понятия теории графов, такие как минор графа, остов графа, путевая ширина, кликовое число, не являются предметом КТГП, но активно ею используются. КТГП включает следующие разделы: вычисление поисковых чисел и оптимального времени поиска, операции над графами и поисками на них, классификация графов относительно их поисковых чисел^{[источник не указан 1247 дней]}.

Для постановки задачи поиска на графах достаточно было средств времён Эйлера, однако первые содержательные результаты то этой теме появились лишь к концу 1980-х годов. Основополагающие работы принадлежат: Николаю Петрову^[2], Торренсу Парсонсу^[3], Андреа Лапо^[4], Фёдору Фомину^[5], Петру Головачу^[6].

См. также

• Задача об Ангеле и Дьяволе