Будапешт: дисциплина получает имя

Теорема о паросочетаниях

Задача, с которой всё начинается, формулируется бытовым языком.

Есть работники и вакансии; каждый работник подходит на некоторые из вакансий. Требуется распределить как можно больше людей по местам, чтобы никто не занимал две должности и на одном месте не сидели двое.

На языке графов: двудольный граф (вершины двух сортов, рёбра только между сортами), и надо найти наибольшее паросочетание — набор рёбер без общих вершин.

Как понять, что найденное паросочетание уже наибольшее? Нужен признак, который можно предъявить и проверить.

Теорема Кёнига (1931). В двудольном графе наибольшее число рёбер в паросочетании равно наименьшему числу вершин, покрывающих все рёбра (наименьшему вершинному покрытию).

Одно неравенство очевидно: чтобы покрыть $k$ независимых рёбер, нужно не меньше $k$ вершин, значит покрытие не меньше паросочетания. Содержательно другое — что они равны, и, значит, минимальное покрытие служит сертификатом оптимальности.

Это первый на нашей линии пример теоремы двойственности: задача на максимум и задача на минимум имеют один и тот же ответ. Тот же сюжет повторится у Канторовича в линейном программировании, а в теории потоков превратится в теорему о максимальном потоке и минимальном разрезе (Форд и Фалкерсон, 1956).

Родственная формулировка — теорема Холла о свадьбах (1935): полное паросочетание существует тогда и только тогда, когда всякая группа из $k$ работников в сумме подходит не менее чем на $k$ вакансий. Условие проверяемо и наглядно; теоремы Кёнига и Холла выводятся друг из друга.

Практическое продолжение. В 1955 году Гарольд Кун построил на этих идеях алгоритм для задачи о назначениях и назвал его венгерским методом — в честь Кёнига и Эгервари. Ирония: в 2006 году выяснилось, что тот же метод содержится в посмертно изданной латинской рукописи ЯкобиКарл Густав Якобинемецкий математик · 1804–1851Соперничал с Абелем в теории эллиптических функций и придумал вместе с Бесселем вещь, изменившую науку сильнее любой теоремы, — исследовательский семинар. 1840-х годов. Приоритетные сюрпризы на этой линии не кончаются.

Первый учебник

В 1936 году Дьёнеш Кёниг (1884–1944) издаёт «Theorie der endlichen und unendlichen Graphen» — «Теорию конечных и бесконечных графов». Это первая в истории монография по теории графов.

Значение книги — не в новых теоремах, а в том, что она превратила коллекцию задач в предмет. До неё существовали: мосты Эйлера, раскраска Гатри, цикл Гамильтона, деревья КэлиАртур Кэлианглийский математик и юрист · 1821–1895Четырнадцать лет работал адвокатом и между делами написал двести пятьдесят математических работ, а заодно придумал слово «матрица» и абстрактное определение группы., алгоритм Борувки — разрозненные сюжеты, не связанные ни общей терминологией, ни общим методом. Кёниг ввёл единый язык, собрал результаты, показал связи и обозначил задачи.

Само слово «граф» в нынешнем смысле восходит к Сильвестру (1878), но в оборот его ввела именно эта книга.

Отдельно стоит лемма Кёнига: бесконечное дерево, у каждой вершины которого конечное число потомков, содержит бесконечный путь. Утверждение выглядит очевидным, а на деле это принцип, эквивалентный слабой форме аксиомы выбора, и он постоянно используется в логике — в частности, в доказательствах теоремы компактности.

Венгерский феномен

Почему именно Будапешт? Это отдельный и поучительный сюжет.

С конца XIX века в Венгрии сложилась система, которую потом копировал весь мир:

• Соревнование имени Этвёша (с 1894 года) — старейшая в мире математическая олимпиада;
• KöMaL (с 1894 года) — ежемесячный журнал задач для школьников, где публиковались решения с именами авторов и печатались их фотографии;
• сеть учителей, работавших с одарёнными детьми как с будущими исследователями.

Из этой системы вышли Эрдёш, Туран, Секереш, Кляйн, фон НейманДжон фон Нейманвенгеро-американский математик · 1903–1957Аксиоматизировал квантовую механику, основал теорию игр, придумал архитектуру компьютера и метод Монте-Карло — и всё это, по мнению современников, не напрягаясь., Пойа, Сегё, Радо, Ласло Ловас — плотность математиков первого ряда на душу населения, не имеющая аналогов.

Отец Кёнига, Дьюла Кёниг, тоже был крупным математиком (известен работами по теории множеств), и школа была отчасти семейной.

Октябрь 1944 года

15 октября 1944 года в Венгрии произошёл переворот: к власти пришла партия «Скрещённые стрелы», и начались массовые депортации будапештских евреев, до того относительно уцелевших.

Дьёнеш Кёниг покончил с собой 19 октября 1944 года.

Он до последнего занимался помощью коллегам-евреям, которых преследовали. На нашей карте это уже третья такая смерть в одном ряду: Хаусдорф в Бонне в 1942-м, Ден в бегстве через полмира, Кёниг в Будапеште.

Задача. В двудольном графе слева вершины $a,b,c$, справа $1,2,3$; рёбра: $a\!-\!1$, $a\!-\!2$, $b\!-\!1$, $c\!-\!1$. Найдите наибольшее паросочетание и наименьшее вершинное покрытие и проверьте теорему Кёнига.
(Ответ: паросочетание $\{a\!-\!2,\ b\!-\!1\}$ размера 2; больше нельзя, потому что $c$ соединена только с 1. Покрытие $\{a,1\}$ размера 2 покрывает все четыре ребра. Равенство выполнено. Заметьте, что условие Холла нарушено: группа $\{b,c\}$ подходит только на одну вакансию, поэтому полного паросочетания нет.)

Следующая точка: Кембридж — где определят, что вообще значит «вычислить», и обнаружат вопросы без ответа.