Об изоморфизме графов (P vs. NP)
Кажется, есть некоторое, довольно серьезное, продвижение в задаче об изоморфизме графов. 10 ноября математик Ласло Бабаи (László (Laci) Babai) расскажет о новом алгоритме, который позволяет решить задачу об изоморфизме графов за квазиполиномиальное время. Объявление об этом имеется на сайте Чикагского университета.
Задача об изоморфизме графов является одной из “математических болезней”. Самый быстрый известный алгоритм, позволяющий определить, изоморфны ли два данные графа, принадлежит Бабаи и Лаксу. Этот алгоритм был предложен в 1983 году. Время его работы — . Если верить объявлению, Бабаи уменьшил это время до
(
— некоторый полином от
). Таким образом, одна из важнейших задач оказывается чуть-чуть более, чем P.
А теперь немного о самом Ласло Бабаи. Он родился в 1950 году в Будапеште. Работает профессором математики и информатики в Чикагском университете. Главным образом занимается комбинаторикой, теорией сложности вычислений, алгоритмами и конечными группами, особенно интересуется связями между этими областями математики. Наиболее значительные его достижения — это введение интерактивной системы доказательств, введение термина “алгоритм Лас-Вегас” и использование теоретико-групповых методов в проверке графов на изоморфизм.
Бабаи изучал математику в Будапештском университете в 1968-1973 гг., в 1975 г. получил степень Ph.D. Венгерской Академии наук, стал доктором наук Венгерской Академии наук в 1984 г. Был преподавателем Будапештского университета с 1971 г. В 1987 г. стал профессором математики в Будапеште и профессором информатики в Чикагском университете. В 1995 г. стал профессором математики и информатики в Чикаго и оставил преподавание в Будапеште.
В 1993 г. совместно с другими математиками получил премию Гёделя, в нынешнем году ему присудили премию Кнута.
Ну а теперь давайте сформулируем задачу об изоморфизме графов. Сделаем это как можно проще, на доступном языке, так, чтобы было ясно, о чем идет речь. Понять, в чем состоит задача, довольно легко, вы можете убедиться в этом сами. А вот найти быстрый алгоритм, позволяющий проверить, изоморфны ли два данные графа, оказалось крайне сложно.
Сначала вспомним определение графа.
Определение. Графом называется пара
, где
— множество вершин,
— множество пар вершин, или ребер.
Иначе говоря, граф — это набор точек (вершин), которые соединены линиями (ребрами).
Ребра и вершины графов обычно нумеруют.
Определение. Графы и
называются равными, если
.
Иначе говоря, графы равны, если у них одинаковое число вершин, пронумерованных числами от до
, и в
есть ребро между вершинами с номерами
и
тогда и только тогда, когда в
есть ребро, соединяющее вершины с номерами
и
.
А теперь определение изоморфных графов.
Определение. Графы и
изоморфны, если
после перенумерации вершин становится равным
.
Задача об изоморфизме графов. Выяснить, изоморфны ли два данные графа и
.
Источники: http://www.scottaaronson.com/blog/
https://en.wikipedia.org/wiki/László_Babai
1 Доцент:
На уроке математики учительница дает задачу:
- Выяснить, изоморфны ли эти два графа?
И объявляет:
- Тому, кто первым пойдёт к доске, ставлю на балл больше.
Вовочка с задней парты:
- Иду, Мариванна! Не из графьев – ставьте три!
[Ответить]
Елизавета Александровна Калинина Reply:
Ноябрь 10th, 2015 at 22:22
Ну да, на медаль согласен
[Ответить]
Доцент Reply:
Декабрь 25th, 2015 at 14:08
http://www.spb.aif.ru/society/education/rossiyskie_shkolniki_provalilis_na_mezhdunarodnoy_olimpiade_po_matematike
…результаты недавно прошедшей ежегодной Международной математической олимпиады. «Российская сборная заняла там 8-е место по баллам, а в общекомандном зачете, по медалям, оказалась на 21-м, – рассказал Сергей Миронов. – Хотя до этого десятилетиями наши школьники занимали на подобных олимпиадах первые места, и последний раз это было в 2007 году. Потом три года подряд мы были вторыми, следующие четыре года – четвертыми, а теперь вот – 8-е место. Эта печальная статистика служит абсолютно объективной оценкой ЕГЭ, который был введен в качестве обязательной формы оценки знаний как раз в 2008 году»
[Ответить]
Елизавета Александровна Калинина Reply:
Декабрь 25th, 2015 at 19:36
ЕГЭ, конечно же, зло, но здесь, думаю, не только он виноват…
[Ответить]
2 Доцент:
Возможно, что Вам будет интересно недавнее открытие пятиэтапного золотого сечение отрезка с помощью циркуля и линейки.
http://forumgeom.fau.edu/FG2003volume3/FG200322index.html
и еще кое-что об этом
http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/phi2DGeomTrig.html
[Ответить]
Елизавета Александровна Калинина Reply:
Декабрь 25th, 2015 at 19:34
Спасибо, посмотрю. Сейчас времени нет совсем
[Ответить]
3 Владимир:
Интересно, что какие только сложнейшие теоремы рассматривает математика. В том числе и доказательство Вайса т-мы Ферма на 200 страницах со ссылкой на японскую теорему. Его доказательство понимают только пару человек. А моего простенького никто не нашёл. Его сейчас наверное во всю изучают студенты в Дрогобычском педуниверситете.
[Ответить]
1 Январь 2016, 13:22