Координационный совет по делам молодежи в научной и образовательной сферах Совета при Президенте Российской Федерации по науке и образованию

Лауреат премии Президента РФ в области науки и инноваций для молодых учёных за 2011 год Андрей Райогородский с коллегами уточнил классическую теорию графов

26 сентября 2016 года, 10:56
Андрей Райогородский

Ученые механико-математического факультета МГУ имени М.В.Ломоносова, в том числе лауреат премии Президента РФ в области науки и инноваций для молодых учёных за 2011 год Андрей Райогородский, усовершенствовали классическую теорию для случая дистанционных графов. Результаты работы опубликованы в высокорейтинговом журнале Discrete and Computational Geometry.

«Есть такой важный математический объект — граф. О графах есть масса литературы. Один из классических результатов в теории графов был доказан Тураном в 1941 году. Этот результат в некотором смысле нельзя улучшить. Однако его можно улучшить на отдельных классах графов. Нам удалось это сделать в случае так называемых дистанционных графов», — рассказывает главный автор статьи, профессор механико-математического факультета МГУ, доктор физико-математических наук Андрей Райгородский.

Граф представляет собой множество вершин (узлов), соединённых рёбрами и является способом визуализации связей между определенными объектами. Примерами графов в повседневной жизни являются схема линий метрополитена и генеалогическое древо. Пал Туран в 1941 году сформулировал теорему о максимальном количестве ребер в графах.

Нынешняя работа ученых относится к области дискретной геометрии. Используя методы теории графов и довольно тонкую технику работы с дистанционными графами, ученые доказали новую оценку числа ребер у подграфа дистанционного графа с данным «числом независимости».

«Этот результат можно как уточнять, так и обобщать. Думаю, работ на эту тему появится много», — говорит Андрей Райгородский.

Источник: Сайт Московского государственного университета имени М.В.Ломоносова