Конечная теория гарантированного поиска (Tkuycugx mykjnx igjgumnjkfguukik hknvtg)

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

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

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

Для постановки задачи поиска на графах достаточно было средств времён Эйлера, однако первые содержательные результаты то этой теме появились лишь к концу 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.

[_617045e9ddc34a6d-1] Абрамовская, Петров, 2013.

[_3ccac10ef4a27aad-2] Петров, 1982.

[_8f20698d2571b024-3] Parsons, 1976.

[_708b2327b83ea375-4] Lapaugh, 1993.

[_303baedc7cc32a5b-5] Fomin, Thilikos, 2008.

[_c9572ae9058cf930-6] Головач, 1989.

[1]

[2]

[3]

[4]

[5]

[6]