ВЕРСИЯ ДЛЯ СЛАБОВИДЯЩИХ
Войти
Логин:
Пароль:
Забыли пароль?
научная деятельность
структура институтаобразовательные проектыпериодические изданиясотрудники институтапресс-центрконтакты
русский | english

Дискретная и вычислительная геометрия

16 декабря (вторник), 1345, аудитория 307 ИППИ РАН  
 
Михаил Исаев (МФТИ)
 
Перечисление эйлеровых циклов

Эйлеровым циклом графа называется замкнутый путь по ребрам графа, использующей все ребра ровно один раз. BEST-теорема (названная согласно инициалам авторов*B*ruijn, Aardenne-*E*hhrenfest, *S*mith, *T*utte) позволяет связать число различный эйлеровых циклов с количеством помеченных остовных деревьев. Согласно матричной теореме о деревьях перечисление остовных деревьев сводится к подсчету минора специальной матрицы, ассоциированной с графом. В докладе планируется подробно обсудить этот подход для случаев ориентированного и неориентированного графа, а также доказать вышеупомянутые теоремы (и вариации). Доклад основан на работах [1] и [2].
[1] М.И. Исаев, «Асимптотическое перечисление эйлеровых циклов в графах, обладающих сильными перемешивающим свойствами», Известия РАН. Серия Математическая, Т. 77(6), 2013, 45‐70
[2] B. D. McKay, R. W. Robinson, Asymptotic enumeration of eulerian circuits in the complete graph. Combinatorics, Probability and Computing, 7(4), 1998, 437-449.
14.12.2014 |
 

 

© Федеральное государственное бюджетное учреждение науки
Институт проблем передачи информации им. А.А. Харкевича Российской академии наук, 2024
Об институте  |  Контакты  |  Противодействие коррупции