Классическая задача коммивояжера (TSP) требует объехать заданный набор точек (вершин графа). Однако существует гигантский класс логистических проблем, где целью является обслуживание не узлов, а самих дорог (ребер графа). Сбор мусора, уборка снега, заливка битума, патрулирование улиц полицией и инспекция железнодорожных путей требуют, чтобы техника прошла по каждой улице города как минимум один раз. Этот класс задач в исследовании операций называется Маршрутизацией по дугам (Arc Routing Problem). Самой известной базовой моделью этого семейства является Задача китайского почтальона, впервые сформулированная математиком Мэй-Ко Кваном в 1962 году.

Концепция равновесия Нэша стала философским и математическим фундаментом современной теории игр, доказав, что в любой конечной игре всегда существует хотя бы одна стабильная точка в смешанных стратегиях. Однако теорема Джона Нэша (опирающаяся на теорему Какутани о неподвижной точке) носила исключительно экзистенциальный характер — она доказывала существование равновесия, но не давала алгоритма для его нахождения. Только в 1964 году математики Карлтон Лемке и Джозеф Хаусон разработали элегантный комбинаторный метод, который позволил компьютерам алгоритмически вычислять точные равновесия Нэша для игр двух лиц с ненулевой суммой (биматричных игр).

В 1852 году английский математик Фрэнсис Гутри сформулировал знаменитую Проблему четырех красок: можно ли раскрасить любую географическую карту так, чтобы никакие две соседние страны не имели одинакового цвета, используя не более четырех карандашей? Эта абстрактная топологическая загадка, решенная лишь век спустя с помощью суперкомпьютеров, заложила основы колоссального раздела исследования операций — Задачи раскраски графов (Graph Coloring Problem, GCP). Сегодня математический аппарат хроматических полиномов управляет распределением радиочастот в мобильных сетях, составляет расписания экзаменов в университетах и оптимизирует выделение регистров внутри микропроцессоров Intel и AMD.