На рубеже XIX и XX веков математики под руководством Давида Гильберта лелеяли грандиозную мечту: создать абсолютно строгую, полную и непротиворечивую формальную систему, из аксиом которой алгоритмически выводилась бы любая математическая истина. Однако в 1931 году 25-летний Курт Гёдель опубликовал две теоремы о неполноте, которые навсегда разрушили эту мечту, доказав фундаментальные ограничения самой логики и дискретной математики.

Когда мы обсуждали алгоритм Дейкстры для поиска кратчайшего пути, мы упомянули, что он использует приоритетную очередь для извлечения вершины с минимальным расстоянием. Если использовать обычный массив, извлечение минимума займет время O(V). Если использовать классическую Бинарную кучу (Binary Heap), время извлечения и время обновления (уменьшения) ключа составят O(log V). Для разреженных графов это отлично. Но для очень плотных графов, где количество ребер огромно и операция "Уменьшить ключ" (Decrease-Key) вызывается миллионы раз, логарифм начинает тормозить систему. В 1984 году Майкл Фредман и Роберт Тарьян создали Фибоначчиеву кучу, чтобы преодолеть этот барьер.

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