01
А
Астрономия
02
Б
Биология
03
Г
Гуманитарные науки
04
М
Математика и CS
05
Мд
Медицина
06
Нз
Науки о Земле
07
С
Сельское хозяйство
08
Т
Технические науки
09
Ф
Физика
10
Х
Химия и науки о материалах
Математика и Computer Science
22 сентября 2016
Теория графов: на пути к совершенству

Ученые МГУ уточнили классическую теорию графов

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

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

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

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

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

Комментарии

Все комментарии
САМОЕ ЧИТАЕМОЕ
Обсуждаемое