Математика, которая мне нравится

Кажется, есть некоторое, довольно серьезное, продвижение в задаче об изоморфизме графов. 10 ноября математик Ласло Бабаи (László (Laci) Babai) расскажет о новом алгоритме, который позволяет решить задачу об изоморфизме графов за квазиполиномиальное время. Объявление об этом имеется на сайте Чикагского университета.

Задача об изоморфизме графов является одной из “математических болезней”. Самый быстрый известный алгоритм, позволяющий определить, изоморфны ли два данные графа, принадлежит Бабаи и Лаксу. Этот алгоритм был предложен в 1983 году. Время его работы — . Если верить объявлению, Бабаи уменьшил это время до ( — некоторый полином от ). Таким образом, одна из важнейших задач оказывается чуть-чуть более, чем P.

А теперь немного о самом Ласло Бабаи. Он родился в 1950 году в Будапеште. Работает профессором математики и информатики в Чикагском университете. Главным образом занимается комбинаторикой, теорией сложности вычислений, алгоритмами и конечными группами, особенно интересуется связями между этими областями математики. Наиболее значительные его достижения — это введение интерактивной системы доказательств, введение термина “алгоритм Лас-Вегас” и использование теоретико-групповых методов в проверке графов на изоморфизм.

Бабаи изучал математику в Будапештском университете в 1968-1973 гг., в 1975 г. получил степень Ph.D. Венгерской Академии наук, стал доктором наук Венгерской Академии наук в 1984 г. Был преподавателем Будапештского университета с 1971 г. В 1987 г. стал профессором математики в Будапеште и профессором информатики в Чикагском университете. В 1995 г. стал профессором математики и информатики в Чикаго и оставил преподавание в Будапеште.

В 1993 г. совместно с другими математиками получил премию Гёделя, в нынешнем году ему присудили премию Кнута.

Ну а теперь давайте сформулируем задачу об изоморфизме графов. Сделаем это как можно проще, на доступном языке, так, чтобы было ясно, о чем идет речь. Понять, в чем состоит задача, довольно легко, вы можете убедиться в этом сами. А вот найти быстрый алгоритм, позволяющий проверить, изоморфны ли два данные графа, оказалось крайне сложно.

Сначала вспомним определение графа.

Определение. Графом называется пара , где — множество вершин, — множество пар вершин, или ребер.

Иначе говоря, граф — это набор точек (вершин), которые соединены линиями (ребрами).

Ребра и вершины графов обычно нумеруют.

Определение. Графы и называются равными, если .

Иначе говоря, графы равны, если у них одинаковое число вершин, пронумерованных числами от до , и в есть ребро между вершинами с номерами и тогда и только тогда, когда в есть ребро, соединяющее вершины с номерами и .

А теперь определение изоморфных графов.

Определение. Графы и изоморфны, если после перенумерации вершин становится равным .

Задача об изоморфизме графов. Выяснить, изоморфны ли два данные графа и .

Источники: http://www.scottaaronson.com/blog/
http://en.wikipedia.org/wiki/László_Babai