Распечатать запись Распечатать запись

Об изоморфизме графов (P vs. NP)

László Babai

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

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

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

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

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

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

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

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

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

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

Определение. Графы G_1=<V_1,E_1 > и G_2=<V_2,E_2> называются равными, если V_1=V_2,E_1=E_2.

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

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

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

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

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

Комментариев: 7

  1. 1 Доцент:

    На уроке математики учительница дает задачу:
    - Выяснить, изоморфны ли эти два графа?
    И объявляет:
    - Тому, кто первым пойдёт к доске, ставлю на балл больше.
    Вовочка с задней парты:
    - Иду, Мариванна! Не из графьев – ставьте три!

    [Ответить]

    Елизавета Александровна Калинина Reply:

    Ну да, на медаль согласен :-)

    [Ответить]

    Доцент Reply:

    http://www.spb.aif.ru/society/education/rossiyskie_shkolniki_provalilis_na_mezhdunarodnoy_olimpiade_po_matematike

    …результаты недавно прошедшей ежегодной Международной математической олимпиады. «Российская сборная заняла там 8-е место по баллам, а в общекомандном зачете, по медалям, оказалась на 21-м, – рассказал Сергей Миронов. – Хотя до этого десятилетиями наши школьники занимали на подобных олимпиадах первые места, и последний раз это было в 2007 году. Потом три года подряд мы были вторыми, следующие четыре года – четвертыми, а теперь вот – 8-е место. Эта печальная статистика служит абсолютно объективной оценкой ЕГЭ, который был введен в качестве обязательной формы оценки знаний как раз в 2008 году»

    [Ответить]

    Елизавета Александровна Калинина Reply:

    ЕГЭ, конечно же, зло, но здесь, думаю, не только он виноват…

    [Ответить]

  2. 2 Доцент:

    Возможно, что Вам будет интересно недавнее открытие пятиэтапного золотого сечение отрезка с помощью циркуля и линейки.
    http://forumgeom.fau.edu/FG2003volume3/FG200322index.html
    и еще кое-что об этом
    http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/phi2DGeomTrig.html

    [Ответить]

    Елизавета Александровна Калинина Reply:

    Спасибо, посмотрю. Сейчас времени нет совсем :(

    [Ответить]

  3. 3 Владимир:

    Интересно, что какие только сложнейшие теоремы рассматривает математика. В том числе и доказательство Вайса т-мы Ферма на 200 страницах со ссылкой на японскую теорему. Его доказательство понимают только пару человек. А моего простенького никто не нашёл. Его сейчас наверное во всю изучают студенты в Дрогобычском педуниверситете.

    [Ответить]

Оставьте свой отзыв

Добавить изображение