|
|
Дискретная и вычислительная геометрия
16 декабря 2014 г. 13:45, г. Москва, ИППИ РАН, Большой Каретный переулок, 19, ауд. 307
|
|
|
|
|
|
Перечисление эйлеровых циклов
М. И. Исаев |
Количество просмотров: |
Эта страница: | 143 |
|
Аннотация:
Эйлеровым циклом графа называется замкнутый путь по ребрам графа, использующей все ребра ровно один раз. BEST-теорема (названная согласно инициалам авторов*B*ruijn, Aardenne-*E*hhrenfest, *S*mith, *T*utte) позволяет связать число различный эйлеровых циклов с количеством помеченных остовных деревьев. Согласно матричной теореме о деревьях перечисление остовных деревьев сводится к подсчету минора специальной матрицы, ассоциированной с графом. В докладе планируется подробно обсудить этот подход для случаев ориентированного и неориентированного графа, а также доказать вышеупомянутые теоремы (и вариации). Доклад основан на работах [1] и [2].
|
|