Семинар МЛ ТИ «Гамильтоновы множества полигональных путей в простых сборных графах»
Приглашаем вас на онлайн-семинар лаборатории теоретической информатики, который пройдет в четверг, 30 мая, в 18:10.
Название доклада: «Гамильтоновы множества полигональных путей в простых сборных графах»
Докладчик: Наталья Остроухова
Аннотация:
Простые сборные графы – графы специального вида, с заданным циклическим порядком ребер в каждой вершине. Они интересны тем, что характеризуют процессы рекомбинации ДНК простейших. Данные графы могут быть представлены с помощью 2-слов, что позволяет применять широкий спектр комбинаторных методов для их изучения. В докладе будут рассмотрены такие характеристики простых сборных графов, как сборное число и количество различных гамильтоновых множеств полигональных путей.
В 2013 году была сформулирована гипотеза о строении простого сборного графа, имеющего максимальное число гамильтоновых множеств полигональных путей. В докладе мы рассмотрим полученное недавно доказательство этой гипотезы и дальнейшие пути развития данной теории.