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

László Babai

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

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

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

Это продолжение темы о графах, начало смотрите здесь.

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

Задача 1. В некоторой компании любые два знакомых не имеют общих знакомых, а любые два незнакомых имеют ровно двух общих знакомых. Докажите, что в этой компании все имеют одинаковое число знакомых.

Показать решение

Задача 2. В лагере отдыхают

школьников. Известно, что среди любых школьников найдется по крайней мере один, знакомый с тремя остальными. Докажите, что найдется школьник, знакомый со всеми остальными школьниками. Читать полностью ‘Регулярные графы’ »

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

Итак, что же такое граф?

Определение. Пусть задано некоторое непустое множество

и множество

пар различных элементов из

. Элементы множества

называются вершинами графа, элементы множества

называются ребрами графа, а пара

, т.е. множество вершин и множество ребер, называется графом.

Обычно в качестве множества

берут множество первых

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

и ребрами

Если две вершины графа соединены ребром, то они называются смежными, иначе — несмежными. Число ребер, выходящих из данной вершины, называется степенью этой вершины. Читать полностью ‘Немного о графах’ »

Джон Робинсон Пирс

В начале 70-х годов прошлого века Джон Пирс предложил коммуникационную сеть, состоящую из соединенных между сосбой в различных точках направленных циклов. Чтобы сообщение попало из исходной точки одного цикла в точку назначения на другом цикле, необходимо было понять, в каких точках нужно переходить на следующие циклы.

Рональд Грэм и Генри Поллак предложили считать каждый цикл вершиной графа, которую отмечали последовательностью символов из алфавита

таким образом, чтобы расстояние Хэмминга между строками соответствовало расстояниям в графе. Тогда переходить на другой цикл следовало, когда адрес нового цикла имел меньшее расстояние Хэмминга до точки назначения. Читать полностью ‘Теория графов и коммуникация’ »