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 | |