Задача коммивояжёра — одна из самых известных задач комбинаторной оптимизации, заключающаяся в поиске самого выгодного маршрута, проходящего через указанные города хотя бы по одному разу с последующим возвратом в исходный город. В условиях задачи указываются критерий выгодности маршрута и соответствующие матрицы расстояний, стоимости и тому подобного. Как правило, указывается, что маршрут должен проходить через каждый город только один раз — в таком случае выбор осуществляется среди гамильтоновых циклов. Существует несколько частных случаев общей постановки задачи, в частности, геометрическая задача коммивояжёра, метрическая задача коммивояжёра, симметричная и асимметричная задачи коммивояжёра. Также существует обобщение задачи, так называемая обобщённая задача коммивояжёра.
Линейное программирование — математическая дисциплина, посвящённая теории и методам решения экстремальных задач на множествах 
-мерного векторного пространства, задаваемых системами линейных уравнений и неравенств.
Кре́стики-но́лики — логическая игра между двумя противниками на квадратном поле 3 на 3 клетки или бо́льшего размера. Один из игроков играет «крестиками», второй — «ноликами». В традиционной китайской игре Гомоку используются чёрные и белые камни.
Игрово́й движо́к — базовое программное обеспечение компьютерной игры. Разделение игры и игрового движка часто расплывчато, и не всегда студии проводят чёткую границу между ними. Но в общем случае термин «игровой движок» применяется для того программного обеспечения, которое пригодно для повторного использования и расширения, и тем самым может быть рассмотрено как основание для разработки множества различных игр без существенных изменений.
Игра в 15, пятнашки, такен — популярная головоломка, придуманная в 1878 году Ноем Чепмэном. Представляет собой набор одинаковых квадратных костяшек с нанесёнными числами, заключённых в квадратную коробку. Длина стороны коробки в четыре раза больше длины стороны костяшек для набора из 15 элементов, соответственно в коробке остаётся незаполненным одно квадратное поле. Цель игры — перемещая костяшки по коробке, добиться упорядочивания их по номерам, желательно сделав как можно меньше перемещений.
Tool-assisted speedrun — скоростное прохождение игры с использованием встроенных инструментов эмулятора, таких как сохранение и перезапись, замедление и покадровый ввод, просмотр содержимого памяти и анализ исполняемого кода. Идея TAS заключается в том, чтобы превзойти ограничения человеческой реакции и способностей игрока ради достижения теоретических пределов игры, то есть границ реальных возможностей игрового движка. Главной целью работы над TAS является создание развлекательных видеороликов, демонстрирующих полное прохождение выбранной игры.
Лео́н Агане́сович Петрося́н — советский и российский математик, профессор Санкт-Петербургского государственного университета. Иностранный член Национальной академии наук Республики Армения.
Владимир Викторович Маза́лов — российский учёный-математик, профессор, доктор физико-математических наук, Заслуженный деятель науки Российской Федерации, Почётный профессор Новгородского Государственного Университета им. Ярослава Мудрого (2019).
Алгори́тм Бо́га — понятие, возникшее в ходе обсуждения способов решения кубика Рубика. Термин может также быть использован в отношении других перестановочных головоломок. Под алгоритмом Бога головоломки подразумевается любой алгоритм, который позволяет получить решение головоломки, содержащее минимально возможное число ходов, начиная с любой заданной конфигурации.
В теории графов древесная ширина неориентированного графа — это число, ассоциированное с графом. Древесную ширину можно определить несколькими эквивалентными путями: как размер наибольшего множества вершин в древесном разложении, как размер наибольшей клики в хордальном дополнении графа, как максимальный порядок убежища при описании стратегии игры преследования на графе или как максимальный порядок ежевики, набора связных подграфов, которые касаются друг друга. Древесная ширина часто используется в качестве параметра в анализе параметрической сложности алгоритмов на графах. Графы с шириной дерева, не превосходящей k, называются частичными k-деревьями. Многие другие хорошо изученные семейства графов также имеют ограниченную ширину дерева.
В теории игр задача о водителе-убийце — это математическая задача преследования, в которой гипотетический убегающий, который может двигаться медленно, но маневренно, пытается уйти от водителя, ведущего машину куда быстрее, но существенно ограниченного в маневре. Предполагается, что оба, убегающий и водитель, никогда не устают. Вопрос ставится так: при каких обстоятельствах и используя какую стратегию водителю удастся догнать убегающего или убегающий сможет избегать встречи бесконечно долго?
В теории игр Принцесса и Чудовище — это игра преследования, в которой два игрока играют в некоторой области. Разработана Руфусом Айзексом и опубликована в его книге Дифференциальные игры (1965) в следующем виде: «Монстр ищет принцессу, потраченное на поиск время является ценой игры. Оба находятся в совершенно тёмном помещении, но оба знают его границы. Найти принцессу означает, что расстояние между принцессой и монстром оказывается в пределах радиуса захвата, который должен быть относительно мал по отношению к размерам помещения. Монстр достаточно разумен и движется с известной скоростью. Принцессе разрешается полная свобода движения».
Максимальный разрез графа — это разрез, размер которого не меньше размера любого другого разреза. Задача определения максимального разреза для графа известна как задача о максимальном разрезе.
Дерево Тремо неориентированного графа G — это остовное дерево графа G с выделенным корнем со свойством, что любые две смежные вершины в графе G связаны друг с другом отношением предок/потомок. Все деревья поиска в глубину и все гамильтоновы пути являются деревьями Тремо. Деревья Тремо названы именем Шарля Пьера Тремо, французского автора 19-го века, который использовал вариант поиска в глубину как стратегию выхода из лабиринта. Деревья Тремо также называют нормальными остовными деревьями, особенно в контексте бесконечных графов.
Гипотеза об экспоненциальном времени — это недоказанное допущение о вычислительной сложности, которое сформулировали Импальяццо и Патури. Гипотеза утверждает, что 3-SAT не может быть решена за субэкспоненциальное время в худшем случае. Из верности гипотезы об экспоненциальном времени, если она верна, следовало бы, что P ≠ NP, но гипотеза является более сильным утверждением. Из утверждения гипотезы можно показать, что многие вычислительные задачи эквиваленты по сложности в том смысле, что если одна из них имеет алгоритм экспоненциального времени, то все они имеют алгоритмы такой же сложности.
Преследование-уклонение — семейство задач в математике и информатике, в которых одна группа пытается поймать членов другой группы в определённой среде. Ранние работы по проблемам такого вида моделировали среду геометрически. В 1976 году Торренс Парсонс ввёл формулировку, в которой движения ограничены графом. Геометрическая формулировка задачи иногда называется непрерывным преследованием-уклонением, а формулировка на графе дискретным преследованием-уклонением. Текущие исследования обычно ограничены одной из этих двух формулировок.
Цена стабильности для игры — отношение оптимального значения целевой функции в одном из её равновесных состояний и оптимального исхода. Цена стабильности имеет смысл для игр, которые имеют некую высшую силу или условия игры, которые каким-либо образом влияют на положение игроков и могут помочь им сойтись к равновесию Нэша. При измерении эффективности равновесия Нэша в какой-либо игре имеет смысл рассматривать и цену анархии.
Теория гарантированного поиска — раздел математики, посвящённый изучению свойств поиска, не зависящих от скорости движения преследователей и наличия информации об убегающем.
Примене́ние тео́рии гра́фов — использование теории графов как математического орудия в различных дисциплинах.
