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

Как математически доказать серверу, что вы знаете пароль от своего аккаунта, не пересылая по сети сам пароль (и даже его хеш)? Как доказать налоговой, что ваша зарплата превышает нужный порог, не раскрывая точную сумму? В дискретной математике и криптографии этот кажущийся неразрешимым парадокс элегантно решается с помощью протоколов Доказательства с нулевым разглашением (Zero-Knowledge Proof, ZKP), созданных в 1985 году.

Задача поиска кратчайших путей между всеми парами вершин графа (All-Pairs Shortest Path, APSP) жизненно необходима для картографических сервисов и маршрутизации. Классический алгоритм Флойда-Уоршелла решает ее блестяще, но требует времени O(V^3). Для плотных графов это нормально, но для огромных разреженных графов (где ребер мало, как в сети реальных дорог) O(V^3) — это катастрофически долго. Алгоритм Джонсона (1977 год) предложил изящный математический трюк, снижающий сложность до O(V^2 log V + VE).