Мы уже обсуждали задачу о минимальном разрезе (Min-Cut), которая изящно решается через алгоритмы максимального потока (или рандомизированный алгоритм Каргера). Кажется логичным, что если изменить слово "минимальный" на "максимальный", задача останется такой же легкой. Но в дискретной математике интуиция часто обманчива. Задача о Максимальном разрезе (Max-Cut) является одной из самых сложных NP-полных проблем, лежащей в основе статистической физики (модели спиновых стекол) и проектирования VLSI-чипов.

Как доказать, что определенный математический объект существует, если вы не можете его построить или привести ни одного конкретного примера? Венгерский математик Пал Эрдёш, один из самых плодовитых ученых XX века, совершил революцию в комбинаторике, создав "Вероятностный метод". Он показал, что случайность можно использовать не только в алгоритмах, но и для получения строгих, абсолютно детерминированных математических доказательств.

Традиционная теория графов моделирует мир в виде парных отношений: дружба между двумя людьми, кабель между двумя серверами, дорога между двумя городами. Но что, если отношение связывает сразу три, четыре или сотню объектов одновременно? Например, несколько соавторов одной научной статьи или группа актеров в одном фильме. Для описания таких многомерных связей дискретная математика использует расширение классической теории — Гиперграфы.