Один и тот же математический граф можно нарисовать на листе бумаги бесконечным множеством способов. Мы можем расположить вершины кругом, квадратом, в виде звезды или хаотично, распутав и запутав ребра. Визуально это будут совершенно разные картинки, но с точки зрения дискретной математики они могут представлять абсолютно идентичную структуру связей. Задача определения структурного тождества двух графов называется проблемой изоморфизма графов.
Дискретная математика имеет раздел, тесно переплетенный с машинной графикой и пространственным анализом, — вычислительную (или дискретную) геометрию. Одной из центральных структур здесь является Диаграмма Вороного (названная в честь русского математика Георгия Вороного). Если вы когда-нибудь задумывались, как мобильный телефон мгновенно находит ближайшую к вам вышку сотовой связи среди тысяч других, ответ кроется именно в этом математическом объекте.
Когда нам нужно подсчитать количество объектов, обладающих определенными свойствами, мы часто сталкиваемся с проблемой пересечений. Если в классе из 30 человек 20 изучают английский язык, а 15 — немецкий, мы не можем просто сложить 20 и 15 (получится 35, что больше числа учеников). Некоторые ученики изучают оба языка, и при простом сложении мы посчитали их дважды. Для решения таких задач в комбинаторике используется мощнейший инструмент — формула включений-исключений.
Магические квадраты, в которых суммы чисел по строкам и столбцам совпадают, были известны еще в Древнем Китае. Однако в дискретной математике гораздо большее значение имеет родственная структура — Латинский квадрат. Это таблица размером N на N, заполненная N различными символами таким образом, что каждый символ встречается в каждой строке и в каждом столбце ровно один раз. Интуитивно каждый из нас знаком с этой структурой благодаря популярной японской головоломке Судоку.
В 1930 году выдающийся британский математик и философ Фрэнк Пламптон Рамсей опубликовал работу, которая породила совершенно новый раздел комбинаторики. Теория Рамсея изучает условия, при которых в достаточно большой структуре (например, графе или последовательности чисел) с математической неизбежностью возникает определенный порядок, как бы мы ни пытались этот порядок разрушить. Девиз этой теории можно сформулировать так: «Абсолютный хаос невозможен».
Как организовать круговой турнир по теннису, чтобы каждый игрок сыграл с каждым ровно один раз, причем матчи шли параллельно без накладок? Как засеять поля разными экспериментальными удобрениями так, чтобы любые два удобрения встретились на одном участке одинаковое число раз для чистоты статистики? Ответы на эти сугубо практические вопросы дает изящный и глубокий раздел дискретной математики — теория комбинаторных блок-дизайнов (или схем).
Каждый программист хотя бы раз в жизни использовал регулярные выражения (RegEx) для валидации email-адреса, проверки формата номера телефона или массовой замены строк в редакторе кода. Однако мало кто задумывается, что за этими загадочными строками из скобок и звездочек скрывается глубокая алгебраическая теория формальных языков и конечных автоматов, разработанная американским математиком Стивеном Клини.
Когда вы открываете навигатор на смартфоне и просите проложить маршрут от дома до работы в обход пробок, в недрах приложения запускаются алгоритмы дискретной математики по поиску кратчайших путей на взвешенных графах. В отличие от простого поиска в ширину (BFS), который эффективен только для сетей с одинаковой длиной ребер, реальный мир требует работы с графами, где каждое ребро имеет свой "вес" — время, километраж или стоимость проезда.
В 2000 году Математический институт Клэя опубликовал список из семи "Задач тысячелетия", предложив за решение каждой из них награду в один миллион долларов. Одной из них является вопрос, который не дает покоя программистам, криптографам и математикам по всему миру: равны ли классы P и NP (P = NP)? Ответ на этот вопрос в дискретной математике может либо навсегда изменить наш мир, либо подтвердить, что наши текущие ограничения непреодолимы.
Задолго до создания первых электронных компьютеров, в 1936 году, 24-летний британский математик Алан Тьюринг придумал абстрактную вычислительную машину. Эта мысленная конструкция стала абсолютным математическим мерилом того, что в принципе можно вычислить алгоритмическим путем, а что — нельзя. Машина Тьюринга является краеугольным камнем теоретической информатики и дискретной математики.