Конечная теория гарантированного поиска
Конечная теория гарантированного поиска (КТГП) — раздел теории гарантированного поиска, в котором изучаются свойства дискретного поиска на комбинаторных графах. Причём бывает полезно вместо комбинаторного представлять граф топологический.
Большинство утверждений КТГП доказывается методами теории графов. Поиск на графе определяется как совокупность некоторых отображений множеств целых неотрицательных чисел во множество вершин графа . Поиску и целому неотрицательному числу всегда сопоставляется подграф графа , называемый исследованной областьюШаблон:Sfn.
Понятия теории графов, такие как минор графа, остов графа, путевая ширина, кликовое число, не являются предметом КТГП, но активно ею используются. КТГП включает следующие разделы: вычисление поисковых чисел и оптимального времени поиска, операции над графами и поисками на них, классификация графов относительно их поисковых чиселШаблон:Нет АИ.
Для постановки задачи поиска на графах достаточно было средств времён Эйлера, однако первые содержательные результаты то этой теме появились лишь к концу 1980-х годов. Основополагающие работы принадлежат: Николаю ПетровуШаблон:Sfn, Торренсу ПарсонсуШаблон:Sfn, Андреа ЛапоШаблон:Sfn, Фёдору ФоминуШаблон:Sfn, Петру ГоловачуШаблон:Sfn.