Математик ЧелГУ моделирует компьютерные сети с помощью теории графов

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

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

«Теорию графов легко проиллюстрировать на наглядных примерах. Возьмём, к примеру, некую компьютерную сеть, где компьютеры соединены между собой проводами. Если графы – это точки, соединённые линиями, то в нашем примере точки – это компьютеры, а линии – это провода, их соединяющие. Если принять эту аналогию, то можно сформулировать такую задачу: «Сколько компьютеров должно выйти из строя, чтобы хотя бы один компьютер не мог связаться с остальными?». Если предельно упростить, то ответу на этот вопрос, по большому счёту, и посвящено моё исследование, – поясняет Дмитрий Панасенко. – Одна из целей моего исследования – ответить, сколько условных компьютеров в особого вида сетях должно сломаться, чтобы образовались компьютеры, которые не могут связаться друг с другом. Результаты работы можно будет применить к проблеме построения качественной разветвлённой компьютерной сети, но не только».  

Теорией графов автор исследования заинтересовался ещё будучи студентом математического факультета ЧелГУ, пять лет назад. Молодой учёный признаётся, что в своё время довольно часто задавал преподавателям вопросы, касающиеся этого раздела математики. Это не осталось незамеченным, и однажды ему предложили написать курсовую работу, связанную именно с теорией графов. Сейчас на подходе кандидатская диссертация по теории графов, которую Дмитрий Панасенко пишет в аспирантуре под руководством профессора института математики и механики УрО РАН имени Н. Н. Красовского Владислава Кабанова.

«Подавая заявку на грант ФПМУ, я описал свой проект, посвящённый вершинным свойствам графов, а также запланировал публикацию двух научных статей и защиту кандидатской диссертации, – говорит Дмитрий Панасенко. – Надеюсь, что мои планы осуществятся в намеченный срок. Пока всё идёт так, как и было задумано. Что касается конкретных научных результатов, один из них будет касаться вершинной связности графов разделяемых дизайнов. Второй же сугубо вычислительный: мы с коллегой, доцентом кафедры компьютерной безопасности и прикладной алгебры математического факультета ЧелГУ Леонидом Шалагиновым нашли графы разделяемых дизайнов с числом вершин до 39, а ещё обнаружили новые конструкции таких графов». 

Направление, в рамках которого находится исследование математиков ЧелГУ, востребовано в мировом научном сообществе.

«Графы разделяемых дизайнов, которые входят в область моих научных интересов – это подкласс так называемых графов Деза, – разъясняет Дмитрий Панасенко. – Графы Деза последние два года – довольно популярная тема. В частности, группы математиков из Ирана, Китая, а в нашей стране – из Новосибирска – активно работают над проблемами, связанными с графами Деза. За последние годы вышло большое количество статей на эту тему. Направление имеет обширное поле для получения результатов при поиске новых конструкций». 

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

«Интересен вопрос построения случайных графов разделяемых дизайнов с заданными свойствами, – отмечает Дмитрий Панасенко. – С одной стороны, данные графы имеют очень строгую структуру, с другой – эта строгая структура значительно упрощает перебор. На основе случайных графов разделяемых дизайнов, на мой взгляд, вряд ли возможно построить хорошую модель интернета, но найти интересные модели каких-то небольших частей сети – вполне можно. Например, социальные графы коллективов или друзей в соцсетях. Но пока я серьёзно не задумывался над этим вопросом». 

Источник: www.csu.ru

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