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

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

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

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

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