Теория графов: на пути к совершенству

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

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

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

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

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