В конце этого материала вы найдёте задачу по теории графов. Сможете решить? Теория графов зародилась в XVIII веке, но долгое время служила лишь источником игровых задач и головоломок. Сегодня учёные, используя графы, моделируют множество различных ситуаций. Практически в каждой области знания можно применить графовые модели.
Доцент кафедры компьютерной безопасности и прикладной алгебры математического факультета ЧелГУ Леонид Шалагинов защитил в Институте математики и механики им. Н. Н. Красовского Уральского отделения Российской академии наук докторскую диссертацию на тему «Спектральные свойства, алгебраические конструкции и характеризации графов Деза».
Леонид Викторович получил несколько новых конструкций графов с заданными условиями алгебраической или комбинаторной симметрии. Математик поделился своими мыслями о перспективах теоретических исследований в математике.
- Теория графов – один из самых интенсивно развивающихся разделов современной математики. С чем, по вашему мнению, это связано?
В основном это связано с бурным прогрессом в сфере вычислительной техники. С одной стороны, это вызвано тем, что графы могут служить хорошей моделью для изучения компьютерных сетей или организации памяти в компьютере. С другой, многие задачи внутри теории графов являются вычислительно сложными и без применения компьютеров их невозможно эффективно решать.
Граф устроен очень просто: есть объекты и связи между ними. Например, в виде графа можно представить кристаллическую решётку или учётные записи в социальной сети с установленной «дружбой».
Теория графов зародилась ещё в XVIII веке, но долгое время служила лишь источником игровых задач, головоломок. Сегодня же, используя графы, можно моделировать множество различных ситуаций. Практически в каждой области знания можно применить графовые модели.
- Какие именно графы входят в область ваших научных интересов?
Я занимаюсь алгебраической теорией графов, поэтому применяю графы внутри алгебры и алгебру внутри теории графов. В этой области есть свои ситуации, когда графы помогают что-то смоделировать. В алгебре одним из основных объектов изучения являются группы симметрий объектов. Большое количество таких симметрий является некоторым критерием «красоты» объекта. В алгебраической теории графов изучаются графы с заданными условиями симметрии.
- В составе какой научной группы вы работаете?
Я занимаюсь теорией графов с момента поступления в аспирантуру под руководством профессора Института математики и механики Уральского отделения РАН Владислава Владимировича Кабанова. Работаю в составе научной группы математиков со схожими интересами из Екатеринбурга, Челябинска, Новосибирска, других городов.
- Есть ли в теории графов задачи, которые пока не смог решить ни один математик в мире?
Конечно. В области теории графов существует немало задач, над которыми ломают голову лучшие математические умы мира. Интересно, что одна из них в упрощённом виде есть даже в ЕГЭ по информатике. Школьникам предлагают два графа, один в виде таблицы, другой в виде картинки, и просят построить соответствие между одним и другим графом. Эта задача называется проблемой проверки изоморфизма графов. Она может быть решена методом простого подбора, который годится только для малого объёма данных. Однако эффективного алгоритма решения в общем случае пока не найдено.
- Ваше исследование носит теоретический характер. Но допускаете ли вы, что в будущем полученные результаты будут использованы для решения прикладных задач?
Это не исключено, хотя прогнозировать такую ситуацию крайне сложно. Понимаете, в теоретической науке главным критерием интереса со стороны учёных является не возможность использования результатов исследований на практике, а красота этих результатов. С древности людей всегда интересовало всё красивое, например правильные многогранники, совершенные числа. Графы, обладающие большим числом симметрий, также можно считать красивыми. В прикладной науке на первом месте стоит задача, которую нужно решить. Затем для этого выбираются средства в арсенале математики и других фундаментальных наук. А теоретики, наоборот, выбирают красивую задачу, которая интересна и красива сама по себе. Конечно, в этом выборе присутствует субъективная составляющая. Теоретическая математика ближе к искусству, чем к решению практических вопросов.
Когда пишут картину или музыку, не думают, в каких областях народного хозяйства они могут пригодиться. В фундаментальной математике точно так же. Многие вещи в математике удалось применить только через столетия после открытия.
Задача от Леонида Шалагинова.
Город имеет схему, как на картинке. Точками обозначены достопримечательности. Туристу нужно попасть из точки A в точку B, по пути пройдя все достопримечательности хотя бы по одному разу.
Какой наименьший путь ему нужно пройти, если длина каждого отрезка улицы – 100м. Нарисуйте этот путь и объясните, почему нельзя пройти меньше.
Пишите в комментариях, удалось ли вам решить. Ответ мы опубликуем в одном из следующих наших материалов.
Автор материала Наталья Чанова