В НГТУ НЭТИ проводятся исследования по алгебраической комбинаторике и проблеме изоморфизма графов
Новости
Доцент кафедры экономической информатики факультета бизнеса Новосибирского государственного технического университета НЭТИ Григорий Рябов получил грантовую поддержку Российского научного фонда по проекту «Кольца Шура и проблема изоморфизма графов Кэли: теория и алгоритмы». Проект нацелен на получение новых результатов о графах Кэли и связанных с ними алгебраических структурах кольцах Шура.
Справка: граф – фундаментальное понятие в математике, которое широко используется в различных областях науки и техники: машинном обучении, обработке информации, хемоинформатике и математической химии, математической лингвистике, теоретической физике, проектировании электронных схем и тд. С помощью графов моделируются искусственные нейронные сети, молекулярные структуры в химии и биологии, сетевые структуры программных систем и баз данных, транспортные системы. Важнейшей задачей теории графов является эффективная проверка их структурного сходства, т.е. проверка изоморфизма графов.
«Изоморфизм двух графов — это взаимно-однозначное соответствие между вершинами графов, сохраняющее смежность вершин. Свойство быть изоморфными говорит о том, одинакова ли структура графов. Важнейшей задачей теории графов является задача эффективной проверки графов на изоморфизм. Эта задача возникает в качестве подзадачи во множестве областей, например, в оптимизации, криптографии. Крайне важной задача проверки изоморфизма графов является в хемоинформатике и математической химии, где графами моделируются решетки атомов в молекулах. Проблема изоморфизма графов, состоящая в поиске наиболее быстрого и эффективного алгоритма проверки графов на изоморфизм, является фундаментальной проблемой математики и computer science. Стоит отметить, что эта проблема тесно связана с одной из проблем тысячелетия — равенства классов P и NP. До сих пор неизвестно, существует ли достаточно быстрый (полиномиальный) алгоритм для решения этой проблемы или его заведомо не существует (задача является NP-полной). Наиболее эффективный на сегодняшний день алгоритм, предложенный в 2016 году выдающимся математиком Л. Бабаи, имеет квазиполиномиальную сложность», – рассказывает Григорий Рябов.
По его словам, проблема изоморфизма графов является одной из самых известных и широко изучаемых на протяжении более чем полувека проблем в комбинаторике и теории вычислительной сложности.
Справка: граф – фундаментальное понятие в математике, которое широко используется в различных областях науки и техники: машинном обучении, обработке информации, хемоинформатике и математической химии, математической лингвистике, теоретической физике, проектировании электронных схем и тд. С помощью графов моделируются искусственные нейронные сети, молекулярные структуры в химии и биологии, сетевые структуры программных систем и баз данных, транспортные системы. Важнейшей задачей теории графов является эффективная проверка их структурного сходства, т.е. проверка изоморфизма графов.
«Изоморфизм двух графов — это взаимно-однозначное соответствие между вершинами графов, сохраняющее смежность вершин. Свойство быть изоморфными говорит о том, одинакова ли структура графов. Важнейшей задачей теории графов является задача эффективной проверки графов на изоморфизм. Эта задача возникает в качестве подзадачи во множестве областей, например, в оптимизации, криптографии. Крайне важной задача проверки изоморфизма графов является в хемоинформатике и математической химии, где графами моделируются решетки атомов в молекулах. Проблема изоморфизма графов, состоящая в поиске наиболее быстрого и эффективного алгоритма проверки графов на изоморфизм, является фундаментальной проблемой математики и computer science. Стоит отметить, что эта проблема тесно связана с одной из проблем тысячелетия — равенства классов P и NP. До сих пор неизвестно, существует ли достаточно быстрый (полиномиальный) алгоритм для решения этой проблемы или его заведомо не существует (задача является NP-полной). Наиболее эффективный на сегодняшний день алгоритм, предложенный в 2016 году выдающимся математиком Л. Бабаи, имеет квазиполиномиальную сложность», – рассказывает Григорий Рябов.
По его словам, проблема изоморфизма графов является одной из самых известных и широко изучаемых на протяжении более чем полувека проблем в комбинаторике и теории вычислительной сложности.